Theseus and the Zipper | Hacker News Reader

Theseus and the Zipper

en.wikibooks.org

42 pointssrik12 comments

You can do those in Erlang as well. Fred Hebert has a nice article on it https://ferd.ca/yet-another-article-on-zippers.html

> Today's children are no longer interested in the ancient myths, they prefer modern heroes like Spiderman or Sponge Bob.

While I can understand why children would consider Spiderman a hero (teaches kids that special talents and roles imply more responsibilities; G-d bless Stan Lee)... I don't think any kid sees SpongeBob as a hero.

Erm, I think that sentence was in jest.

Unless you're making a follow-up joke and I'm just missing that.

I found this a very fun read a while back. Haven't been in a place where this would actually pay dividends versus using a mutable implementation, sadly.

In particular, if performance is a concern, I found it almost inevitable that I would reach for mutable options.

Would love to hear examples in the wild of this.

I don't know this for certain, but if you have immutable data structures then zippers are kind of a requirement. Many immutable data structures also have a hashing system built into them that generates a hash based on their content. So, if you have a data structure with a hash, one thing you can do that is convenient is compare just the hashes of two data structures to determine if they are equal. This is much faster than having to parse the entire data structure recursively.

Might be useful for things that are often compared, like for instance the React virtual DOM.

That tracks my understanding, regarding this being a bit required with immutable structures.

The hash idea works even in mutable land. There are obvious caveats to not mutating data in race related scenarios. But often snapshots and other "freeze" based ideas are just as workable as moving entirely to alternatives.

> The hash idea works even in mutable land

Uh, how? Other than removing it from the dictionary, mutating it then adding it back.

So long as you don't store things in such a way that you can't tell derived and stale data from new, the idea works exactly the same?

I fully grant that immutable structures take away the concerns over data being coherent together. Such that it's easy to do without worrying about someone changing the data under you.

Oddly, it can sometimes make it even harder to know that data is stale. Since updating a small part can devolve into a chore. Still fully agreed that that is the best default position.

My favorite paper on zippers (and one of my favorite papers in general) is Norman Ramsey’s and Joao Dias’s „An Applicative Control-Flow Graph Based on Huet’s Zipper“

https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf

In section 5 they say their zipper turned out to be a little bit faster than the imperative version (they use Ocaml). And the resulting code is simpler and less buggy than the imperative one (section 6.3).

Thanks for the link! Added to my reading list. :)

I confess I'm always wary of reimplementations and claims of improvement. Still, this is exactly what I asked for, thanks! I'm looking forward to finding where I'm wrong.

Come to think of it, Deutsch, Schorr and Waite’s algorithm for traversing a data structure by reversing pointers within it can also be viewed as a form of a zipper. Except that DSW’s algorithm predates the zipper.

DSW’s algorithm is used in the mark phase of garbage collection. It traverses and marks all reachable data in constant space.

https://inst.eecs.berkeley.edu/~cs61bl/r//cur/graphs/garbage...

This feels like the other end of a debate. Moving from immutable structures to hyper optimized traversal of mutable data. :)

Does remind me of threaded trees. Stackless traversal is a fun topic.

Reply on news.ycombinator.com