[HN Gopher] Traversing nested data-structures in various languages
___________________________________________________________________
Traversing nested data-structures in various languages
Author : self
Score : 124 points
Date : 2021-04-12 07:21 UTC (15 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| 11235813213455 wrote:
| 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...,
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| ghufran_syed wrote:
| 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
| [deleted]
| lilactown wrote:
| The Clojure reduce solution is pretty low quality. Here's my 15
| line proposal: https://github.com/josevalim/nested-data-
| structure-traversal...
| Nihilartikel wrote:
| 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
| raspasov wrote:
| 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.
| fermigier wrote:
| 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).
| yakubin wrote:
| The Scheme example is shorter than any of the Python ones.
| _old_dude_ wrote:
| I'm not sure the problem reflect anything, while updating a
| data structure like this is fairly standard, the lesson counter
| is reset globally, which is not a common operation.
|
| For me the problem is too artificial to be meaningful.
| nickjj wrote:
| > For me the problem is too artificial to be meaningful.
|
| The problem came from implementing a real feature into a
| course platform.
|
| The data structure contains a list of sections and lessons to
| build a table of contents. The position stores the order they
| are being displayed in.
|
| In the course viewing page lessons are annotated with a "#N"
| where N is the position and it goes from 1 all the way until
| the last lesson's count. This way folks could be watching the
| course and be like "Hey, I'm on lesson #56 and have a
| question".
|
| But on the course description page the table of contents was
| displayed in such a way where the position / lesson count was
| reset for each section.
|
| Although in the real life implementation this code is wrapped
| into a function and the reset_lesson_position is being
| supplied by a boolean function argument which controls
| whether or not the lesson's position gets reset for every
| section. We added it as an attribute to the section directly
| for the sake of this example to keep the problem more scoped
| to the core idea of the problem.
| _old_dude_ wrote:
| It makes a lot of more sense.
|
| `resetLessonPosition` is not a member of the data structure
| but a parameter of the function that generates the
| positions and it has an effect on all sections.
| OskarS wrote:
| 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 wrote:
| _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.
| zelphirkalt wrote:
| 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.
| lukashrb wrote:
| The author is aware of the fact that mutability makes this kind
| of problem easier [0]
|
| [0]
| https://twitter.com/josevalim/status/1379771275627921409?s=1...
| buro9 wrote:
| 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.
| mands wrote:
| 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.
| lmm wrote:
| 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 wrote:
| 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_ wrote:
| 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__ wrote:
| > 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
|
| Also see: https://news.ycombinator.com/item?id=24710565
| josevalim wrote:
| Thanks for sharing! Solutions to this problem in the vein
| of jq and optics were precisely why I started the repo
| above.
| bradrn wrote:
| > 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.
| alehander42 wrote:
| thanks! i think i now understood the idea
| iudqnolq wrote:
| This sounds essentially impossible without some kind of
| garbage collection. Am I missing something?
| saagarjha wrote:
| Swift has some of this with keypaths.
| alehander42 wrote:
| however: why those instead of iterators or functions? how
| is a `lens` not a function in general (or a yielding
| iterator) which return some kind of views?
| [deleted]
| Twisol wrote:
| In the face of mutation and dynamic typing, yes, an
| iterator providing mutable references to the focused
| piece of the subject would give you something basically
| like a traversal (a generalization of a lens over list-
| like things). However, consider the case of a struct with
| five fields, each of a different type -- you can't just
| for-each over those. And you don't quite have the black-
| box composability benefits of lenses, since you need a
| value to iterate over.
|
| A lens is a (1) functional (2) bi-directional (3) first-
| class and (4) composable generalization of (5) struct
| field names in most traditional languages.
|
| 1) "Functional" meaning we eschew mutation and implicit
| context. Mutation is a very powerful feature of a
| language, and much can be encoded using it. When we
| remove mutation as an option, many of the things we would
| have just used mutation for separate into distinct and
| rich solution spaces.
|
| 2) "Bi-directional" meaning we can use the same widget
| for both accessing a sub-part of a whole, and for
| replacing that sub-part within a whole. I personally call
| these operations "extract" and "replace", since "get" and
| "set" feel like they raise the specter of mutability.
|
| 3) "First-class" means that the lenses themselves are
| manipulable constructs within the language. In a language
| like C or Java, I can have "obj.a.b.c", but I cannot have
| ".a.b.c" itself on its own. Even if you consider method
| references (like "Obj::a" in Java), you've only obtained
| the ability to _extract_ the "a" field from an Obj --
| any particular method or function is only going to go in
| one direction.
|
| 4) "Composable" means that you can take two lenses and
| fit them together to get a new lens. Conceptually, I
| think this is understood -- we intuitively understand how
| to navigate an object graph when writing down an
| expression like "obj.a.b.c" -- but having a _composable_
| first-class abstraction lets us do the same thing
| programmatically. (It need not even be at "runtime" --
| imagine a compile-time macro system that programmatically
| generates nested accesses from some base rules you
| define. I think you've got the rudiments of a dependency
| injection system here.)
|
| 5) "Struct field" means that for the given type, the
| field is always accessible. "List element" (or "tree
| leaf", ...) would give you traversals instead of lenses,
| and "tagged union variant" / "subclass" would give you
| prisms.
|
| As for potential applications of the approach, there's
| the approach dependency injection graphs outlined above.
| I've also used ideas from lenses/prisms in
| serialization/deserialization and web service middleware.
| (Middleware compose really well as functional optics!)
|
| With profunctor optics, you can even construct self-
| describing operations. For instance, imagine a JSON
| parser that can be directly interrogated to obtain the
| schema it accepts, or a middleware stack that can be
| interrogated to determine which headers it looks at, and
| which routes it accepts. Personally, this is the area I'm
| most excited about with functional optics.
| gugagore wrote:
| > 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
|
| From the looks of it, this is to access the first and
| second element specifically of a 2-tuple. I suppose if
| you had to generalize it, you would actually get a
| traversal or a prism or something, because those elements
| might not exist.
| quotemstr wrote:
| 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.
| rwmj wrote:
| 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...
|
| https://github.com/libguestfs/virt-v2v/blob/master/v2v/parse...
| giobox wrote:
| 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
| kstrauser wrote:
| JMESPath is similar: https://jmespath.org
| lifthrasiir wrote:
| 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 wrote:
| 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
| lifthrasiir wrote:
| 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 wrote:
| Very good point. Sexprs for all!
| arethuza wrote:
| 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.
| taeric wrote:
| The common lisp solutions should include at least one LOOP
| example. Since that would almost certainly be directly comparable
| to the python example.
| marvel_boy wrote:
| Simplicity wins. Zig wins again. One more time.
| dastx wrote:
| 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 wrote:
| _> 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.
| raspasov wrote:
| Non-idiomatic ClojureScript, 10 lines:
|
| https://gist.github.com/raspasov/0521706c3f963a9209152bfb2be...
|
| IMO The problem is poorly defined. Data structures should avoid
| control flow instructions like "reset_lesson_position"
| js8 wrote:
| 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 wrote:
| 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.
| [deleted]
| Hurtak wrote:
| 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 wrote:
| Hence, a revealing and useful challenge.
| leontrolski wrote:
| In python/javascript, I'm a big fan of using yield -
| https://leontrolski.github.io/recursing-with-yield.html
|
| It just _feels_ nice to me.
| dsego wrote:
| What are the benefits over the classic way?
| seanhunter wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| The Rust and Haskell versions are complicated to understand for
| such a simple task.
| jkelleyrtp wrote:
| That seems to be a choice of the author, a new approach has
| been uploaded that uses the exact same logic as the python
| approach and is similarly as succinct.
|
| https://github.com/josevalim/nested-data-structure-traversal...
| Chris_Newton wrote:
| 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...
| momentoftop wrote:
| I've always liked `mapAccumL`, and nowadays, it amuses that
| it is implemented by mapping with a state monad (and thus it
| works over arbitrary Traversables).
|
| With that precedent, I'm happy to implement the given problem
| using State and traverse, so it's structured much the same as
| the obvious imperative version: incr ::
| (MonadState s m, Num s) => m s incr = get <* modify
| (+1) annotate :: [Section x] -> [Section Int]
| annotate ss = flip evalState 1 . forM (zip [1..] ss) $
| \(i,Section title reset lessons _) -> do when
| reset (put 1) lessons <- (traverse . traverse)
| (const incr) lessons pure $ Section title
| reset lessons i
| alpaca128 wrote:
| 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.
___________________________________________________________________
(page generated 2021-04-12 23:02 UTC)