[HN Gopher] Zippers: Making Functional "Updates" Efficient (2010)
___________________________________________________________________
Zippers: Making Functional "Updates" Efficient (2010)
Author : tinyspacewizard
Score : 57 points
Date : 2025-10-09 11:07 UTC (11 hours ago)
(HTM) web link (www.goodmath.org)
(TXT) w3m dump (www.goodmath.org)
| sevensor wrote:
| I can see how this is useful if you're repeatedly updating the
| same part of a tree. I can't quite see how to use this approach
| for random edits. Seems like you're back at recreating all the
| nodes back up to the root every time?
| agentultra wrote:
| You're right! For random access and edits you'll need a
| different solution. Maybe some monads to encapsulate the
| mutations.
| macmac wrote:
| Zippers are part of Clojure API (clojure.zip). They take a bit of
| work to get used to, but once you get it they are an amazing way
| of making "transactional" "changes" to immutable data structures.
| thom wrote:
| I've built quite a lot of functionality on top of Clojure's
| version of this. For deeply nested stuff it's great, necessary
| even. But for shallow sequences where you're mostly doing complex
| logic looking back and forth, I genuinely think you're better off
| building some sort of parser combinator solution where you can
| more naturally match multiple conditions over long ranges, and
| alter the output as you send it out, transducer-style. You're
| also much more likely to end up with good performance compared to
| the constant recursive navigation you do with zippers.
| xdavidliu wrote:
| i was messing around on hackerrank a few years ago and one of the
| problems involved implementing Huet's zipper tree, which I did in
| haskell. it was quite fun
|
| https://github.com/xdavidliu/fun-problems/blob/main/zipper-t...
| contificate wrote:
| There's a neat paper where they implement basic blocks (in a
| control flow graph) as zippers
| (https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf). The neat part is
| that - due to how the host language works (mutation having the
| cost of invoking the write barrier) - their measurements show
| that the zipper version is more performant than the mutable
| version.
| clarkmoody wrote:
| I've used the zipper concept with lists for making impossible
| states impossible [0] in the context of Rust programs. The rich
| enum type in Rust creates opportunities to avoid bugs by baking
| small state machines into the code everywhere, like loading data
| in the linked example.
|
| A concrete example is for managing the active item in a list.
| Instead of storing the active item as an index into the vector
| like this: struct List<T> { items:
| Vec<T>, active: usize, }
|
| ...which two the glaring impossible states. The vector can be
| empty, or the index can be outside the vector. Each time the
| active item is desired, we must check the index against the
| current state of the list.
|
| Instead, we can use the zipper concept so we always have a
| concrete active item: struct List<T> {
| prev: Vec<T>, active: T, next: Vec<T>, }
|
| Switching to a different active item requires some logic internal
| to the data structure, but accessing the active item always
| results in a concrete instance with no additional checks
| required.
|
| [0]: https://sporto.github.io/elm-patterns/basic/impossible-
| state...
| hombre_fatal wrote:
| What does the second List impl offer over the first one?
|
| It's the API that makes something impossible to misuse, and
| they could offer the same API like List.create(x: T, xs: T[]),
| but the first one is simpler.
| clarkmoody wrote:
| In one version I've seen, the active element is of a
| different type, offering enhanced functionality over the
| vectors of next and prev items: struct
| List<T, A> { prev: Vec<T>, active: A,
| next: Vec<T>, }
|
| This could be used for some active type that has ephemeral
| cache information or state associated with it (view state in
| a GUI app, for instance). The inactive type may be hydrated
| and converted to active, and the active type can be archived
| into an inactive type.
| johnfn wrote:
| I tend to like the idea of making impossible states impossible,
| but your particular example seems to have a number of negative
| tradeoffs. For one, it's more complex than the original data
| structure - a simple call like .map() is now a fairly chunky
| operation, and if you want to filter after that, you really
| have a mess on your hands. Additionally, you seem to have
| traded off one set of "state we shouldn't allow to be
| represented" for another. For instance, you could have
| mistakenly included `active` in `prev` or `next`. That is
| something you couldn't have done in the initial version.
| clarkmoody wrote:
| The iterator can be implemented fairly simply:
| self.prev.iter() .chain(iter::once(self.active))
| .chain(self.next)
|
| I'm not sure what you mean by including active in another
| position, but see my sibling comment that makes the active
| element of a different type, for another wrinkle on this
| thing.
| gatane wrote:
| Zippers are the derivative of lists. You can go beyond lists,
| too.
|
| https://journals.sagepub.com/doi/abs/10.3233/FUN-2005-651-20...
| geospeck wrote:
| Here[1] is a nice breakdown of Zippers in Clojure. I am not the
| author of the post but I found it very helpful when I wanted to
| learn more about Zippers in Clojure. There are some nice
| illustrations as well.
|
| - https://grishaev.me/en/clojure-zippers/
| eikenberry wrote:
| Archived version with the images still there...
|
| https://web.archive.org/web/20160328032556/http://www.goodma...
___________________________________________________________________
(page generated 2025-10-09 23:01 UTC)