3 ms·
Zippers and Type Magic
- ubertaco 11y agoThis blog is really helpful for understanding FP. I dove into the other big post on there about Haskell and pure functions and monads and it actually made a bit of category theory finally make sense. Just enough brain-stretching to learn, and just barely enough not to make me tune out.
- wheaties 11y agoLove it. That was an excellent and intuitive way to talk about the derivative of a type. I couldn't even come close to explaining it that well.
- cousin_it 11y agoZippers clicked for me when I realized that they are a way to traverse immutable data structures by allocating like crazy. For example, you can have a pair of lists, "left" and "right". To "move left", you create a new pair of lists: the left list minus one element, and the right list plus one element. The same idea also works for traversing other data structures, like trees.
- tel 11y agoAnother way of looking at it that's nice is that they "rewire the pointers". If a LL looks a bit like this [1] -> [2] -> [3] -> [4] -> [] where the [n] location actually represents a data pointer then stepping into the zipper rearranges some of these... [1] <- [2] -> [3] -> [4] -> [] [1] <- [2] <- [3] -> [4] -> [] To be a bit more explicit we should talk about where "we" are * -> [1] -> [2] -> [3] -> [4] -> [] [1] <- * -> [2] -> [3] -> [4] -> [] [1] <- [2] <- * -> [3] -> [4] -> [] etc etc.
- cousin_it 11y agoTo explain stuff to imperative programmers, you need to adopt the operational perspective. Spell out what's actually in memory at any given time, what gets executed after what, where the allocations happen, what's left for the GC to pick up, etc. If you tell them that zippers "rewire the pointers", they will get rightly confused, because rewiring existing pointers is impossible in pure code. Zippers allocate new pointers instead. That's what you should say.
- tel 11y agoIf you're interested in this idea where derivatives form one-hole contexts then you might also be interested in derivative parsers: http://matt.might.net/papers/might2011derivatives.pdf http://matt.might.net/papers/might2011derivatives.pdf