[HN Gopher] Theseus and the Zipper ___________________________________________________________________ Theseus and the Zipper Author : srik Score : 33 points Date : 2022-12-04 16:45 UTC (6 hours ago) (HTM) web link (en.wikibooks.org) (TXT) w3m dump (en.wikibooks.org) | taeric wrote: | 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. | stephen_cagle wrote: | 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. | taeric wrote: | 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. | zasdffaa wrote: | > The hash idea works even in mutable land | | Uh, how? Other than removing it from the dictionary, | mutating it then adding it back. | taeric wrote: | 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. | i_don_t_know wrote: | 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). | taeric wrote: | 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. | i_don_t_know wrote: | 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... | taeric wrote: | 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. | rdtsc wrote: | 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 ___________________________________________________________________ (page generated 2022-12-04 23:00 UTC)