Zippers continue to fascinate me. Let’s recap a bit: a zipper is a data structure representing the navigation and mutation of an otherwise immutable structure. We’ve looked at several different implementations here on the LShift blog, in several different languages.
Today, we’re going to see what else we can do with zippers.
When we implement a Huet-style zipper (in other words, we use a recursive structure based on one-hole contexts instead of directly using partial continuations), we implement a bunch of primitive behaviours – left, right, replace, insert child, and so on. Let’s assume we have all that.
The first obvious thing to do is to define a traversal. We need two essential elements for a traversal – a means of knowing when we’re done, and a means of moving to the next element. Now there’s a teeny hitch. Given a zipper over some hierarchical structure, it seems most natural to describe our traversal in terms of recursion – after all, we’re working with a recursive structure. Ruby doesn’t require proper tail call elimination (even though, apparently, some implementations support it). We don’t want stack overflows from too-deep recursion, so we’ll reach into our toolbox and haul out a trampoline:
A trampoline will take some block, and invoke it with the given initial value. If the block yields a
Proc (what the Lispers would call a thunk – a parameterless
Proc that delays the evaluation of some chunk of code), it will invoke the block with this
Proc, and repeat that process until the block yields something that’s not a
Proc. Finally, it will return that non-
Proc value. With tool in hand, we can now write a recursive pre-order traversal, confident that we won’t blow our stack even on large structures. Note that this particular zipper uses “safe” navigation, wrapping up results in the Either monad.
It’s easy to wrap up
next inside some object, and simply invoke the entire traversal with
each is defined thusly:
We could just mix in
Enumerable and get
map and a whole lot more For Free… but
Enumerable#map returns an
Array, and I want
map to return something of whatever type it was fed.
Of course there’s nothing stopping us from implementing other traversals – post-order, in-order (for binary trees), or even breadth-first. What’s nice is that none of these traversal strategies have any knowledge about the structure over which they move! They just know about the zipper… and the zipper knows nothing about the structure, except
With a traversal in hand, we’re free to jump into the land of higher order functions – map, fold, and the like. Now of course, as we just saw, these traversals know nothing about the underlying structure. That means that while we can implement a fold -
- we will obviously have to tell the fold what to do. Actually, this is no different from your usual fold in Common Lisp or Smalltalk or Haskell. So given some kind of tagged tree with
Leaf elements, we could have
So here we see how to apply all manner of transformations – mapping a tree to another tree of the same shape, folding a tree, insert our fondest desire – with the core mechanisms remaining firmly decoupled from our types.