[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)