9 ms·

Traversing nested data-structures in various languages

136 points by self 5y ago

buro9 5y ago
Why do I see things like this and still think that XML and XSLT made a lot of this stuff very simple and portable and that we lost a good bit of progress by choosing JSON, YAML, etc after we already had great validation of schemas, translation, streaming and DOM parsing, etc.
- lmm 5y ago
  I'm guessing it's because you haven't tried to write an XSLT recently. Yes, it's a way to declarative express transformations which has a lot of elegant theoretical properties. But that doesn't matter when it's so, so painfully tedious to actually write.
  - saurik 5y ago
    XSL/T just kept getting better; like, I agree with exactly what you said for 1.0--which sadly is all libxslt (and thereby browsers that relied on it) ever supported--but XSL/T 2.0 was pretty epic, and there is now even a 3.0 as of a few years ago.
    - emmanueloga_ 5y ago
      Agreed, XSLT 3.0 is amazing... and XQuery provides a more palatable syntax, with similar semantics. Kinda ironic that given the problem definition no solution has been provided on XQuery or XSLT yet, the widely used domain specific languages that better suit the problem :-). I believe there's a lot of inspiration to be had from the X-family of languages. The "secret sauce" is XPath. We need a new language drawing inspiration from the tree processing of X* languages but with more modern syntax and less with a less byzantine type system (read: anything but XML Schema :-). Less angle brackets would help too! --- Bonus points: add tuples and prolog like queries to such language (thinking of SPARQL) ... now that would be something really powerful.
      - bmn__ 5y ago
        > We need a new language drawing inspiration This exists (optics/lenses), but most programmers don't know about it. I expect this to hit mainstream programming languages a few years later. I don't know of a simple, jargon-free explanation of the concepts. WP is useless, sadly. http://enwp.org/Bidirectional_transformation http://enwp.org/Bidirectional_transformation Also see: https://news.ycombinator.com/item?id=24710565 https://news.ycombinator.com/item?id=24710565
        josevalim 5y ago
        Thanks for sharing! Solutions to this problem in the vein of jq and optics were precisely why I started the repo above.
        bradrn 5y ago
        > This exists (optics/lenses), but most programmers don't know about it. … I don't know of a simple, jargon-free explanation of the concepts. Let me have a go! I’d explain optics/lenses as giving field access as a data structure. That is, a lens is an object which describes how to access an element from a ‘larger’ value. For example, you can define _1 and _2 as lenses for accessing the first and second element respectively of a tuple: _1 :: Lens' (a,b) a _2 :: Lens' (a,b) b (Using Haskell syntax here as that’s what I know best, though I’ve simplified the types slightly.) The great advantage of having these as first-class values is that you can now manipulate them. Of course, the main things you’ll want to do with these are get and set things: > (1,2) ^. _1 1 > (1,2) & _1 .~ 3 (3,2) More interestingly, you can also use a function to modify the value to which a lens is pointing: > (1,2) & _1 %~ negate (-1,2) Most usefully, you can also compose lenses. For instance, to get the second element of the first element of a nested tuple, you can compose _2 and _1 using dot notation: _1._2 :: Lens' ((a,b),c) b Or, for a more realistic example, here’s a lens which accesses the ‘numSeen’ field of the value corresponding to key "keyToIncrement": (ix "keyToIncrement")._numSeen :: Lens' (Map String MyStructure) Int (Well, strictly speaking, this is actually a traversal or a prism or something, because "keyToIncrement" might not exist, but let’s ignore that for this really simple example…) And now that you have it, you can use this new lens to do anything you want with this value: you can get it, set it, increment it, decrement it, print it, etc. Additionally, you don’t have to restrict yourself to just lenses. For example, ‘traversals’ are a generalisation of lenses which allow you to access 0, 1 or more elements, rather than restricting access to just one element at a time. For instance, you can use ‘both’ to transform, well, both elements of a tuple: > (1,2) & both 5~ negate (-1,-2) Or you can use ‘traversed’ to access each element of, say, a list: > [1,2,3,4,5] & traversed .~ 0 [0,0,0,0,0] Of course, there are other ways of doing each of these. If you happen to be working with mutable values, you can sometimes use dot notation to access deeply nested fields. Some usecases of ‘traversed’ can be replaced by a map. However, there really is no comparable substitute for lenses when working with deeply nested immutable structures, especially ones of unknown shape.
- arethuza 5y ago
  I did a lot of work back in the day with XML, XML Schemas, XSLT etc. I much prefer JSON, JSON Schema even JSON Path (although not used the latter quite as much as the first two). Edit: XSLT could be kind of neat in some contexts if used with a degree of restraint, but it usually wasn't.
- rwmj 5y ago
  XPath is the real killer feature for parsing XML. I don't think it's possible to use it in this particular example, but in the more generally useful cases where you want to pull (eg) all subnodes with key matching a particular string, XPath is great. Here's it being used in real code (search for "xpath_"): https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse_ovf_from_ova.ml https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse... https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse_libvirt_xml.ml https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse...
  - giobox 5y ago
    JSONPath confers pretty much the same concept onto JSON too with much the same syntax. There are JPath implementations for most languages now. > https://github.com/json-path/JsonPath https://github.com/json-path/JsonPath
    - kstrauser 5y ago
      JMESPath is similar: https://jmespath.org https://jmespath.org
- mands 5y ago
  Couldn't agree more, using the XML toolchain (via lxml in python) for a recent project and it couldn't have gone better - you can get really far quickly with XPath, XSLT, and Relax-NG schemas to ensure correctness. Writing XSLT extensions in python in participate is really powerful.
- lifthrasiir 5y ago
  I find the very idea of XSLT simply pointless. It is fundamentally structured around templates and doesn't accept anything beyond XML (even in XSLT 3.0, where you can have an initial template but can't get rid of it), making it cumbersome for general programming. It is also very verbose so it is not suitable for scripting as well. For XSLT to be useful you need a complex enough transformation (so you actually want templates) and nothing else (so you can avoid general programming); that use case would be pretty rare.
  - nerdponx 5y ago
    Sounds like declarative pattern matching which sounds just great to me [0]. I won't deny that XML sucks to write. But I'm not yet ready to throw the baby out with the bathwater. Maybe we keep using XML as a machine-readable serialization format (and XSLT as serialization of pattern-matching data transformations!) and people use native data structures in their own programming languages. Or we all switch to S-expressions. 0: https://github.com/noprompt/meander https://github.com/noprompt/meander
    - lifthrasiir 5y ago
      Pattern matching is great, but probably not if everything is pattern matching. Also I'm okay with XML as long as it doesn't power an urge to make everything XML and everything connected via the semantic web (lol). XSLT is a remnant of that urge and should have been a non-XML-based language. (The same criticism applies to, e.g. RDF vs. Notation3.)
      - nerdponx 5y ago
        Very good point. Sexprs for all!
- quotemstr 5y ago
  It's interesting to me how weighty and important technical decisions get made on the basis of the most superficial aesthetic considerations. XML's data model is beautiful, but on a syntactic level, it's kind of ugly, and I think it's mostly for this reason that a certain segment of the industry eschews it even today. Honestly, if XML had kept SGML-style implicit closing tags, we might have never seen the rise of alternative data markup systems. That is, instead of <foo>some_value</foo> you should be able to write (as you can write in SGML) <foo>some_value</> There. Now in exchange for a slight increase in parser complexity, you address a big syntactic wart (the repetition) the drives people away from XML. Seems like a win to me.
marvel_boy 5y ago
Simplicity wins. Zig wins again. One more time.
- dastx 5y ago
  I don't know about you but having to prefix every line of what I'm assuming is something similar to heredoc with `\\` doesn't seem simple to me. It's as bad as having to suffix each line with `\` to escape new lines. That's an odd design choice and horrible UX. > section.Object.get("reset_lesson_position").?.Bool Also requiring the provide the type every time you retrieve an element from a JSON string again seems odd. JSON already has the data type, why do I need to provide the type every time I retrieve the data?
  - yakubin 5y ago
    > Also requiring the provide the type every time you retrieve an element from a JSON string again seems odd. JSON already has the data type, why do I need to provide the type every time I retrieve the data? Because JSON is a serialization format, so as such it is external to your code. One day an element in the JSON you receive is a boolean, but another day it's a string, because another system had a bug and started producing junk data. Now in your code it's good to 1. document what type you expect, 2. trigger an error if the types don't match. It also has the benefit that all types can be checked statically, without providing any surrogate input. A schema integrated somehow with the language could be a more optimal solution though. But no schema, and no type annotations in the code is a no-no from me. UPDATE: Now that I'm thinking about it, I'm wondering why JSON was used in the Zig example at all, instead of using builtin data types. Seems like a really odd choice.
deleted 5y ago
[deleted]
11235813213455 5y ago
Just wanting to say that all JS solutions are quite 'bad', except the simple for-of, because they're combining pure array methods (.map, .reduce) and side-effects (external variable to that method), not even talking about modifying Array protoype https://github.com/josevalim/nested-data-structure-traversal/blob/master/javascript/map_with_state.js#L3 https://github.com/josevalim/nested-data-structure-traversal..., never do this, don't touch to objects you don't own, and that others would access and not expect to be modified! I'll make a PR to try to contribute, instead of just complaining like that, hehe Btw I'm surprised the structure isn't deeply nested (requiring recursion to process it), it'd be more interesting
- saiojd 5y ago
  For the sake of argument, there's really nothing wrong with combining map/reduce with side-effects, especially for things like counters were the alternative of threading the variables everywhere can end up being much more complex very quickly.
  - zdragnar 5y ago
    For the sake of argument, use `forEach` if you want to introduce side effects. `map` and `reduce` are names with meaning, and passing impure functions to them is more confusing than passing some procedural function to `forEach` or using `for of`. It is something of a nit-picky argument to be sure, but it is a good mental habit to have. Edit: I think being strict with the semantic building blocks is a good mental habit, not necessarily making nit-picky arguments.
    - the-smug-one 5y ago
      Being disciplined is part of good engineering. To have clearly defined idioms is important, so I want to reinforce that this is not nit-picky. You can argue that anything is nit-picky, under the guise of subverting good engineering in exchange for getting to be lazy.
fermigier 5y ago
What are the OP's conclusion from this experiment ? I was expecting the FP languages solutions to be exceptionally short and elegant, but after a quick glance it seems to me that the Python and Python-like languages (e.g. Nim, Zig, etc.) are "winning" (YMMV of course).
- OskarS 5y ago
  The lesson for me is that this particular problem is exceptionally well suited for imperative code, and makes functional code look terrible in comparison. It's not just the "Python-likes" that do well: both the C and C++ code (C++ in particular) are very straightforward, simple and very readable, but any functional language solution that uses reduce or whatever looks terrible in comparison. The striking example is the JavaScript one: the simple imperative solution (for_of.js) is perfectly fine and lovely, but the other ones (map_with_state.js in particular) are total nightmares. Most of them are (almost certainly) significantly less performant than the simple imperative ones. Not all problems are like this, of course, there are many examples where functional style code shines. But certainly there are many problems like this one, where imperative code is just the superior paradigm.
  - Scarbutt 5y ago
    The lesson for me is that this particular problem is exceptionally well suited for imperative code, and makes functional code look terrible in comparison. This is the case for 80% of real world code in IME.
    - higerordermap 5y ago
      As long as there aren't too many variables keeping state, imperative should be fine.
- zelphirkalt 5y ago
  I think this is perhaps only a repository for keeping things or approaches, which has surfaced here, because of the fame of the author. The results and code might be rather individual preferences or ad-hoc solutions to typical problems. The data in the example does not require a lot of recursion to be elegantly processed. It is too simple an example for that. The second aspect is, that the example code might have different priorities than the viewer. If I want to process a tree concurrently on multiple cores, then perhaps I should not be using much mutable state. However, if my priority is not concurrency and multi-core, then perhaps I can write it in very little code in Python and similar languages. When my priorities shift to concurrency and multi-core and lets say I got a deeply nested tree, I might have to adapt all these examples and suddenly the FP languages shine.
ghufran_syed 5y ago
Interesting how different some of the approaches are in the same language, never mind different languages. In clojure, the “atom” version is 5 lines (not including data or tests), while the “zipper” version is 47 lines and the “reduce” version is 31 lines
- raspasov 5y ago
  Yes, the atom is a hack and discouraged but when you're stuck with a poorly defined data structure, it can be an escape hatch.
- Nihilartikel 5y ago
  Clojure also has some third party libraries like Specter [1] that make nested traversal and mutation very succinct and performant. The author of Specter goes so far as to label traversal/update of deep immutable structures as "Clojure's Missing Piece". [1] https://github.com/redplanetlabs/specter https://github.com/redplanetlabs/specter
- deleted 5y ago
  [deleted]
- lilactown 5y ago
  The Clojure reduce solution is pretty low quality. Here's my 15 line proposal: https://github.com/josevalim/nested-data-structure-traversal/pull/147 https://github.com/josevalim/nested-data-structure-traversal...
raspasov 5y ago
Non-idiomatic ClojureScript, 10 lines: https://gist.github.com/raspasov/0521706c3f963a9209152bfb2becd91c https://gist.github.com/raspasov/0521706c3f963a9209152bfb2be... IMO The problem is poorly defined. Data structures should avoid control flow instructions like "reset_lesson_position"
- js8 5y ago
  What if we rephrased it as having the lists sorted by additional field "category", and you are supposed to reset the counter in a new category?
  - josevalim 5y ago
    Correct. In the real-life example this came from, a separate parameter would control how to reset the lesson counter but it was moved into a boolean property to keep the problem focused. Your "category" idea would be a nice addition to the problem though. The logic of when to reset would still be fairly simple and folks would have to explore how to represent the initial category value before traversal starts. I assume most would solve it with nil and maybe/option types.
leontrolski 5y ago
In python/javascript, I'm a big fan of using yield - https://leontrolski.github.io/recursing-with-yield.html https://leontrolski.github.io/recursing-with-yield.html It just feels nice to me.
- dsego 5y ago
  What are the benefits over the classic way?
  - seanhunter 5y ago
    It can be a very elegant way to encapsulate annoying complexity in an interface that is easy for callers to use correctly. Typical example: say you need to connect to an api that has pagination. You call it and you get a chunk which has a number of things and a counter of remaining chunks. Normally this king of thing requires the caller to keep a lot of messy state. with yield you can make an interface that the caller can just iterate over and it will give them one thing at a time and fetch the next chunk if the current one is exhausted and there are chunks remaining. The state of the "current chunk", "chunks remaining", index etc can all be enclosed so the caller doesn't need to know anything about them.
    - gugagore 5y ago
      You could require the caller to keep an opaque handle, and have all the state encapsulated on that handle. The caller won't know if this state is messy or not, and I think this does a good job of encapsulating annoying complexity. But it doesn't prevent the caller from passing the handle to another function, or copying the handle, which could mess things up, and I suppose `yield` helps with that. But most of all, I'd say it makes it easier to write the callee code, not the caller code, since the callee does not need to "reify" the state of "current chunk" and "chunks remaining" into an object, nor (more crucially) the state of loops and other control flow.
      - iudqnolq 5y ago
        Absolutely. It's like how async can be replaced with a struct and a giant switch statement, but that's a PITA to write manually.
jedisct1 5y ago
The Rust and Haskell versions are complicated to understand for such a simple task.
- alpaca128 5y ago
  The map-mutable variant in Rust doesn't seem all too complicated to me; but I have the advantage of being used to the iterator+closure syntax which admittedly can look unnecessarily confusing sometimes. I personally often avoid long chained iterator operations, especially if they involve `for_each()`. Usually they're barely shorter than a for loop but seem to be harder to figure out for the type & ownership checker, leading to annoying issues with less helpful error messages. And just like with pipes in Bash I often run into situations where I wish I had multiple "channels" through which I can pass data, and a loop doesn't have any limitation like that. Luckily there are multiple neat ways to solve problems in the language.
- Chris_Newton 5y ago
  IMHO, the Haskell version using mapAccumL[1] is actually quite a nice demonstration of the power of having lots of computational patterns available immediately from the standard library. The biggest problem in Haskell that a language like JS doesn’t have is the types: you’re converting both the outer type for sections and the inner type for lessons into something else, so in any language with explicit static types you’re going to have the overhead of specifying those, or you have to hack around it a bit as we see here. However, if you ignore the type boilerplate and the definition of the input data, the substance of the algorithm here would be around the same length as the imperative JS for-of version, particularly with less verbose names for the local variables as idiomatic Haskell tends to use. With all four types explicitly defined and using another map-accumulate instead of the zipWith so updating the lessons with their positions was done similarly to updating the sections, I think it could be quite readable as well, even with Haskell’s limited support for record types. [Edit: Having actually tried this now, even with DuplicateRecordFields, my Haskell code still seems unnecessarily verbose because of the record manipulations, but I still quite like the use of mapAccumL for making the pattern of computation explicit.] [1] https://github.com/josevalim/nested-data-structure-traversal/blob/master/haskell/AccumL.hs https://github.com/josevalim/nested-data-structure-traversal...
Hurtak 5y ago
The whole problem seems to be bizarrely defined when it comes to data structures. Basically the input is `data+config` merged into one object and the return value is `data+config+tranversal_properties` merged into one object with lots of solutions mutating the original input data.
- argvargc 5y ago
  Hence, a revealing and useful challenge.
taeric 5y ago
The common lisp solutions should include at least one LOOP example. Since that would almost certainly be directly comparable to the python example.
- taeric 5y ago
  Amusingly, I think I will lose this if I don't link it here. https://github.com/josevalim/nested-data-structure-traversal/pull/151 https://github.com/josevalim/nested-data-structure-traversal... is my attempt at getting a LOOP solution in. As noted in the message, I originally did this in elisp, which felt a bit more natural, for some reason.
citrin_ru 5y ago
TIL about postfix dereference in Perl: https://perldoc.perl.org/perlref#Postfix-Dereference-Syntax https://perldoc.perl.org/perlref#Postfix-Dereference-Syntax One of advantages of Perl to me stable syntax - usually I can open code written by someone nowadays after not using Perl and not encounter any unknown language features. Turned out even in Perl there are new features you need to learn first before you can read the code, though compare to other languages it still easy to keep up with all new features.

136 points by self 5y ago

Why do I see things like this and still think that XML and XSLT made a lot of this stuff very simple and portable and that we lost a good bit of progress by choosing JSON, YAML, etc after we already had great validation of schemas, translation, streaming and DOM parsing, etc.

lmm 5y ago
I'm guessing it's because you haven't tried to write an XSLT recently. Yes, it's a way to declarative express transformations which has a lot of elegant theoretical properties. But that doesn't matter when it's so, so painfully tedious to actually write.
- saurik 5y ago
  XSL/T just kept getting better; like, I agree with exactly what you said for 1.0--which sadly is all libxslt (and thereby browsers that relied on it) ever supported--but XSL/T 2.0 was pretty epic, and there is now even a 3.0 as of a few years ago.
  - emmanueloga_ 5y ago
    Agreed, XSLT 3.0 is amazing... and XQuery provides a more palatable syntax, with similar semantics. Kinda ironic that given the problem definition no solution has been provided on XQuery or XSLT yet, the widely used domain specific languages that better suit the problem :-). I believe there's a lot of inspiration to be had from the X-family of languages. The "secret sauce" is XPath. We need a new language drawing inspiration from the tree processing of X* languages but with more modern syntax and less with a less byzantine type system (read: anything but XML Schema :-). Less angle brackets would help too! --- Bonus points: add tuples and prolog like queries to such language (thinking of SPARQL) ... now that would be something really powerful.
    - bmn__ 5y ago
      > We need a new language drawing inspiration This exists (optics/lenses), but most programmers don't know about it. I expect this to hit mainstream programming languages a few years later. I don't know of a simple, jargon-free explanation of the concepts. WP is useless, sadly. http://enwp.org/Bidirectional_transformation http://enwp.org/Bidirectional_transformation Also see: https://news.ycombinator.com/item?id=24710565 https://news.ycombinator.com/item?id=24710565
      - josevalim 5y ago
        Thanks for sharing! Solutions to this problem in the vein of jq and optics were precisely why I started the repo above.
      - bradrn 5y ago
        > This exists (optics/lenses), but most programmers don't know about it. … I don't know of a simple, jargon-free explanation of the concepts. Let me have a go! I’d explain optics/lenses as giving field access as a data structure. That is, a lens is an object which describes how to access an element from a ‘larger’ value. For example, you can define _1 and _2 as lenses for accessing the first and second element respectively of a tuple: _1 :: Lens' (a,b) a _2 :: Lens' (a,b) b (Using Haskell syntax here as that’s what I know best, though I’ve simplified the types slightly.) The great advantage of having these as first-class values is that you can now manipulate them. Of course, the main things you’ll want to do with these are get and set things: > (1,2) ^. _1 1 > (1,2) & _1 .~ 3 (3,2) More interestingly, you can also use a function to modify the value to which a lens is pointing: > (1,2) & _1 %~ negate (-1,2) Most usefully, you can also compose lenses. For instance, to get the second element of the first element of a nested tuple, you can compose _2 and _1 using dot notation: _1._2 :: Lens' ((a,b),c) b Or, for a more realistic example, here’s a lens which accesses the ‘numSeen’ field of the value corresponding to key "keyToIncrement": (ix "keyToIncrement")._numSeen :: Lens' (Map String MyStructure) Int (Well, strictly speaking, this is actually a traversal or a prism or something, because "keyToIncrement" might not exist, but let’s ignore that for this really simple example…) And now that you have it, you can use this new lens to do anything you want with this value: you can get it, set it, increment it, decrement it, print it, etc. Additionally, you don’t have to restrict yourself to just lenses. For example, ‘traversals’ are a generalisation of lenses which allow you to access 0, 1 or more elements, rather than restricting access to just one element at a time. For instance, you can use ‘both’ to transform, well, both elements of a tuple: > (1,2) & both 5~ negate (-1,-2) Or you can use ‘traversed’ to access each element of, say, a list: > [1,2,3,4,5] & traversed .~ 0 [0,0,0,0,0] Of course, there are other ways of doing each of these. If you happen to be working with mutable values, you can sometimes use dot notation to access deeply nested fields. Some usecases of ‘traversed’ can be replaced by a map. However, there really is no comparable substitute for lenses when working with deeply nested immutable structures, especially ones of unknown shape.
arethuza 5y ago
I did a lot of work back in the day with XML, XML Schemas, XSLT etc. I much prefer JSON, JSON Schema even JSON Path (although not used the latter quite as much as the first two). Edit: XSLT could be kind of neat in some contexts if used with a degree of restraint, but it usually wasn't.
rwmj 5y ago
XPath is the real killer feature for parsing XML. I don't think it's possible to use it in this particular example, but in the more generally useful cases where you want to pull (eg) all subnodes with key matching a particular string, XPath is great. Here's it being used in real code (search for "xpath_"): https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse_ovf_from_ova.ml https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse... https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse_libvirt_xml.ml https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse...
- giobox 5y ago
  JSONPath confers pretty much the same concept onto JSON too with much the same syntax. There are JPath implementations for most languages now. > https://github.com/json-path/JsonPath https://github.com/json-path/JsonPath
  - kstrauser 5y ago
    JMESPath is similar: https://jmespath.org https://jmespath.org
mands 5y ago
Couldn't agree more, using the XML toolchain (via lxml in python) for a recent project and it couldn't have gone better - you can get really far quickly with XPath, XSLT, and Relax-NG schemas to ensure correctness. Writing XSLT extensions in python in participate is really powerful.
lifthrasiir 5y ago
I find the very idea of XSLT simply pointless. It is fundamentally structured around templates and doesn't accept anything beyond XML (even in XSLT 3.0, where you can have an initial template but can't get rid of it), making it cumbersome for general programming. It is also very verbose so it is not suitable for scripting as well. For XSLT to be useful you need a complex enough transformation (so you actually want templates) and nothing else (so you can avoid general programming); that use case would be pretty rare.
- nerdponx 5y ago
  Sounds like declarative pattern matching which sounds just great to me [0]. I won't deny that XML sucks to write. But I'm not yet ready to throw the baby out with the bathwater. Maybe we keep using XML as a machine-readable serialization format (and XSLT as serialization of pattern-matching data transformations!) and people use native data structures in their own programming languages. Or we all switch to S-expressions. 0: https://github.com/noprompt/meander https://github.com/noprompt/meander
  - lifthrasiir 5y ago
    Pattern matching is great, but probably not if everything is pattern matching. Also I'm okay with XML as long as it doesn't power an urge to make everything XML and everything connected via the semantic web (lol). XSLT is a remnant of that urge and should have been a non-XML-based language. (The same criticism applies to, e.g. RDF vs. Notation3.)
    - nerdponx 5y ago
      Very good point. Sexprs for all!
quotemstr 5y ago
It's interesting to me how weighty and important technical decisions get made on the basis of the most superficial aesthetic considerations. XML's data model is beautiful, but on a syntactic level, it's kind of ugly, and I think it's mostly for this reason that a certain segment of the industry eschews it even today. Honestly, if XML had kept SGML-style implicit closing tags, we might have never seen the rise of alternative data markup systems. That is, instead of <foo>some_value</foo> you should be able to write (as you can write in SGML) <foo>some_value</> There. Now in exchange for a slight increase in parser complexity, you address a big syntactic wart (the repetition) the drives people away from XML. Seems like a win to me.

marvel_boy 5y ago

Simplicity wins. Zig wins again. One more time.

dastx 5y ago
I don't know about you but having to prefix every line of what I'm assuming is something similar to heredoc with `\\` doesn't seem simple to me. It's as bad as having to suffix each line with `\` to escape new lines. That's an odd design choice and horrible UX. > section.Object.get("reset_lesson_position").?.Bool Also requiring the provide the type every time you retrieve an element from a JSON string again seems odd. JSON already has the data type, why do I need to provide the type every time I retrieve the data?
- yakubin 5y ago
  > Also requiring the provide the type every time you retrieve an element from a JSON string again seems odd. JSON already has the data type, why do I need to provide the type every time I retrieve the data? Because JSON is a serialization format, so as such it is external to your code. One day an element in the JSON you receive is a boolean, but another day it's a string, because another system had a bug and started producing junk data. Now in your code it's good to 1. document what type you expect, 2. trigger an error if the types don't match. It also has the benefit that all types can be checked statically, without providing any surrogate input. A schema integrated somehow with the language could be a more optimal solution though. But no schema, and no type annotations in the code is a no-no from me. UPDATE: Now that I'm thinking about it, I'm wondering why JSON was used in the Zig example at all, instead of using builtin data types. Seems like a really odd choice.

deleted 5y ago

[deleted]

11235813213455 5y ago

Just wanting to say that all JS solutions are quite 'bad', except the simple for-of, because they're combining pure array methods (.map, .reduce) and side-effects (external variable to that method), not even talking about modifying Array protoype https://github.com/josevalim/nested-data-structure-traversal/blob/master/javascript/map_with_state.js#L3 https://github.com/josevalim/nested-data-structure-traversal..., never do this, don't touch to objects you don't own, and that others would access and not expect to be modified! I'll make a PR to try to contribute, instead of just complaining like that, hehe Btw I'm surprised the structure isn't deeply nested (requiring recursion to process it), it'd be more interesting

saiojd 5y ago
For the sake of argument, there's really nothing wrong with combining map/reduce with side-effects, especially for things like counters were the alternative of threading the variables everywhere can end up being much more complex very quickly.
- zdragnar 5y ago
  For the sake of argument, use `forEach` if you want to introduce side effects. `map` and `reduce` are names with meaning, and passing impure functions to them is more confusing than passing some procedural function to `forEach` or using `for of`. It is something of a nit-picky argument to be sure, but it is a good mental habit to have. Edit: I think being strict with the semantic building blocks is a good mental habit, not necessarily making nit-picky arguments.
  - the-smug-one 5y ago
    Being disciplined is part of good engineering. To have clearly defined idioms is important, so I want to reinforce that this is not nit-picky. You can argue that anything is nit-picky, under the guise of subverting good engineering in exchange for getting to be lazy.

fermigier 5y ago

What are the OP's conclusion from this experiment ? I was expecting the FP languages solutions to be exceptionally short and elegant, but after a quick glance it seems to me that the Python and Python-like languages (e.g. Nim, Zig, etc.) are "winning" (YMMV of course).

OskarS 5y ago
The lesson for me is that this particular problem is exceptionally well suited for imperative code, and makes functional code look terrible in comparison. It's not just the "Python-likes" that do well: both the C and C++ code (C++ in particular) are very straightforward, simple and very readable, but any functional language solution that uses reduce or whatever looks terrible in comparison. The striking example is the JavaScript one: the simple imperative solution (for_of.js) is perfectly fine and lovely, but the other ones (map_with_state.js in particular) are total nightmares. Most of them are (almost certainly) significantly less performant than the simple imperative ones. Not all problems are like this, of course, there are many examples where functional style code shines. But certainly there are many problems like this one, where imperative code is just the superior paradigm.
- Scarbutt 5y ago
  The lesson for me is that this particular problem is exceptionally well suited for imperative code, and makes functional code look terrible in comparison. This is the case for 80% of real world code in IME.
  - higerordermap 5y ago
    As long as there aren't too many variables keeping state, imperative should be fine.
zelphirkalt 5y ago
I think this is perhaps only a repository for keeping things or approaches, which has surfaced here, because of the fame of the author. The results and code might be rather individual preferences or ad-hoc solutions to typical problems. The data in the example does not require a lot of recursion to be elegantly processed. It is too simple an example for that. The second aspect is, that the example code might have different priorities than the viewer. If I want to process a tree concurrently on multiple cores, then perhaps I should not be using much mutable state. However, if my priority is not concurrency and multi-core, then perhaps I can write it in very little code in Python and similar languages. When my priorities shift to concurrency and multi-core and lets say I got a deeply nested tree, I might have to adapt all these examples and suddenly the FP languages shine.

ghufran_syed 5y ago

Interesting how different some of the approaches are in the same language, never mind different languages. In clojure, the “atom” version is 5 lines (not including data or tests), while the “zipper” version is 47 lines and the “reduce” version is 31 lines

raspasov 5y ago
Yes, the atom is a hack and discouraged but when you're stuck with a poorly defined data structure, it can be an escape hatch.
Nihilartikel 5y ago
Clojure also has some third party libraries like Specter [1] that make nested traversal and mutation very succinct and performant. The author of Specter goes so far as to label traversal/update of deep immutable structures as "Clojure's Missing Piece". [1] https://github.com/redplanetlabs/specter https://github.com/redplanetlabs/specter
deleted 5y ago
[deleted]
lilactown 5y ago
The Clojure reduce solution is pretty low quality. Here's my 15 line proposal: https://github.com/josevalim/nested-data-structure-traversal/pull/147 https://github.com/josevalim/nested-data-structure-traversal...

raspasov 5y ago

Non-idiomatic ClojureScript, 10 lines: https://gist.github.com/raspasov/0521706c3f963a9209152bfb2becd91c https://gist.github.com/raspasov/0521706c3f963a9209152bfb2be... IMO The problem is poorly defined. Data structures should avoid control flow instructions like "reset_lesson_position"

js8 5y ago
What if we rephrased it as having the lists sorted by additional field "category", and you are supposed to reset the counter in a new category?
- josevalim 5y ago
  Correct. In the real-life example this came from, a separate parameter would control how to reset the lesson counter but it was moved into a boolean property to keep the problem focused. Your "category" idea would be a nice addition to the problem though. The logic of when to reset would still be fairly simple and folks would have to explore how to represent the initial category value before traversal starts. I assume most would solve it with nil and maybe/option types.

leontrolski 5y ago

In python/javascript, I'm a big fan of using yield - https://leontrolski.github.io/recursing-with-yield.html https://leontrolski.github.io/recursing-with-yield.html It just feels nice to me.

dsego 5y ago
What are the benefits over the classic way?
- seanhunter 5y ago
  It can be a very elegant way to encapsulate annoying complexity in an interface that is easy for callers to use correctly. Typical example: say you need to connect to an api that has pagination. You call it and you get a chunk which has a number of things and a counter of remaining chunks. Normally this king of thing requires the caller to keep a lot of messy state. with yield you can make an interface that the caller can just iterate over and it will give them one thing at a time and fetch the next chunk if the current one is exhausted and there are chunks remaining. The state of the "current chunk", "chunks remaining", index etc can all be enclosed so the caller doesn't need to know anything about them.
  - gugagore 5y ago
    You could require the caller to keep an opaque handle, and have all the state encapsulated on that handle. The caller won't know if this state is messy or not, and I think this does a good job of encapsulating annoying complexity. But it doesn't prevent the caller from passing the handle to another function, or copying the handle, which could mess things up, and I suppose `yield` helps with that. But most of all, I'd say it makes it easier to write the callee code, not the caller code, since the callee does not need to "reify" the state of "current chunk" and "chunks remaining" into an object, nor (more crucially) the state of loops and other control flow.
    - iudqnolq 5y ago
      Absolutely. It's like how async can be replaced with a struct and a giant switch statement, but that's a PITA to write manually.

jedisct1 5y ago

The Rust and Haskell versions are complicated to understand for such a simple task.

alpaca128 5y ago
The map-mutable variant in Rust doesn't seem all too complicated to me; but I have the advantage of being used to the iterator+closure syntax which admittedly can look unnecessarily confusing sometimes. I personally often avoid long chained iterator operations, especially if they involve `for_each()`. Usually they're barely shorter than a for loop but seem to be harder to figure out for the type & ownership checker, leading to annoying issues with less helpful error messages. And just like with pipes in Bash I often run into situations where I wish I had multiple "channels" through which I can pass data, and a loop doesn't have any limitation like that. Luckily there are multiple neat ways to solve problems in the language.
Chris_Newton 5y ago
IMHO, the Haskell version using mapAccumL[1] is actually quite a nice demonstration of the power of having lots of computational patterns available immediately from the standard library. The biggest problem in Haskell that a language like JS doesn’t have is the types: you’re converting both the outer type for sections and the inner type for lessons into something else, so in any language with explicit static types you’re going to have the overhead of specifying those, or you have to hack around it a bit as we see here. However, if you ignore the type boilerplate and the definition of the input data, the substance of the algorithm here would be around the same length as the imperative JS for-of version, particularly with less verbose names for the local variables as idiomatic Haskell tends to use. With all four types explicitly defined and using another map-accumulate instead of the zipWith so updating the lessons with their positions was done similarly to updating the sections, I think it could be quite readable as well, even with Haskell’s limited support for record types. [Edit: Having actually tried this now, even with DuplicateRecordFields, my Haskell code still seems unnecessarily verbose because of the record manipulations, but I still quite like the use of mapAccumL for making the pattern of computation explicit.] [1] https://github.com/josevalim/nested-data-structure-traversal/blob/master/haskell/AccumL.hs https://github.com/josevalim/nested-data-structure-traversal...

Hurtak 5y ago

The whole problem seems to be bizarrely defined when it comes to data structures. Basically the input is `data+config` merged into one object and the return value is `data+config+tranversal_properties` merged into one object with lots of solutions mutating the original input data.

argvargc 5y ago
Hence, a revealing and useful challenge.

taeric 5y ago

The common lisp solutions should include at least one LOOP example. Since that would almost certainly be directly comparable to the python example.

taeric 5y ago
Amusingly, I think I will lose this if I don't link it here. https://github.com/josevalim/nested-data-structure-traversal/pull/151 https://github.com/josevalim/nested-data-structure-traversal... is my attempt at getting a LOOP solution in. As noted in the message, I originally did this in elisp, which felt a bit more natural, for some reason.

citrin_ru 5y ago

TIL about postfix dereference in Perl: https://perldoc.perl.org/perlref#Postfix-Dereference-Syntax https://perldoc.perl.org/perlref#Postfix-Dereference-Syntax One of advantages of Perl to me stable syntax - usually I can open code written by someone nowadays after not using Perl and not encounter any unknown language features. Turned out even in Perl there are new features you need to learn first before you can read the code, though compare to other languages it still easy to keep up with all new features.