Zippers: Making Functional "Updates" Efficient (2010)(goodmath.org)

63 pointsby tinyspacewizardvor 9 Monaten15 comments

Zippers: Making Functional "Updates" Efficient (2010)

http://www.goodmath.org/blog/2010/01/13/zippers-making-functional-updates-efficient/

15 comments

thomvor 9 Monaten

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.

contificatevor 9 Monaten

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.

clarkmoodyvor 9 Monaten

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...

johnfnvor 9 Monaten

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.

clarkmoodyvor 9 Monaten

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.

hombre_fatalvor 9 Monaten

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.

clarkmoodyvor 9 Monaten

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.

rkangelvor 9 Monaten

How do you represent an empty list with this approach?

gatanevor 9 Monaten

Zippers are the derivative of lists. You can go beyond lists, too.

https://journals.sagepub.com/doi/abs/10.3233/FUN-2005-651-20...

xdavidliuvor 9 Monaten

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...

geospeckvor 9 Monaten

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/

sevensorvor 9 Monaten

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?

agentultravor 9 Monaten

You’re right! For random access and edits you’ll need a different solution. Maybe some monads to encapsulate the mutations.

eikenberryvor 9 Monaten

Archived version with the images still there...

https://web.archive.org/web/20160328032556/http://www.goodma...

macmacvor 9 Monaten

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.