Take a map: it takes some traversable structure, executes a function on each element, and returns a new traversable structure with the values obtained by applying the function to the elements of that structure.
Define a function that returns a pair (value, partial continuation) where the partial continuation represents the path taken to reach a particular value. This is a zipper on the given value.
It doesn’t particularly matter which control operators you use to get that partial continuation. shift/reset’s convenient because I’ve already implemented it, but Chung-chieh Shan showed that they’re all equally expressible.
Finally, give the map over the suspensible walk a function that composes the partial continuation with a “decider” function. This function takes some value and either returns that value, or the value of the node associated with the zipper.
This gives you a zipper on the first node. When you feed a value into the zipper, it returns you a new zipper, on the next node in your structure. When you’ve reached the end of your traversal, return a zipper that indicates that you’ve finished the traversal.
Hey presto, you have a zipper, derived from the traversal of an arbitrary structure.
So what’s that look like in Smalltalk?
The map function is called #collect: in Smalltalk. So
#(1 2 3) collect: #printString returns (something equal in value to)
#('1' '2' '3'). We already have shift/reset.
The zipper itself is a very simple structure. Note that I leave out uninteresting things like accessors and initialising methods:
instanceVariableNames: 'term continuation'.
Zipper subclass: #ZipDone.
^ [continuation value: Maybe nothing] reset.
^ [continuation value: anObject] reset.
(The reason we wrap
#zipUp in a
#reset will become apparent later.)
Incidental to our discussion, we have some helper classes:
Maybe subclass: #Just
Maybe subclass: #Nothing.
Just>>maybe: aBlock default: anObject
^ aBlock value: value.
Nothing>>maybe: aBlock default: anObject
^ Nothing new.
Lastly, we extend
PartialContinuation to allow it to compose with other things – continuations, blocks, selectors pretending to be blocks. This lets us compose behaviour without evaluating anything.
^ [:x | self value: (aUnaryBlock value: x)].
All the magic happens here:
"Turn an enumeration inside out: return a zipper on a traversal such that
the continuation associated with the traversal takes a Maybe. If the
value given to the continuation is Nothing, leave the value associated
with the zipper unchanged; otherwise, replace it with the Just value."
| f |
"Return a new Zipper for each element in aCollection. As a termination
marker, return a final zipper, a ZipDone, containing the new collection
of resultant zippers."
f := [:a |
[:k | Zipper
with: (k compose: [:x | x maybe: #yourself default: a])] shift].
^ [ZipDone on: (aCollection collect: [:each | f value: each]) ] reset.
Here we see that when
#zipOver: returns the reset marker will pop off the stack. This is why we need to replace the marker when we send
Zipper pairing the first element of the Collection with a partial continuation of the map of the collection all the way to the first element. Each time we send
#next: we resume the map, and
f then cuts off the partial continuation representing the now-extended map. Each time we resume the map, we either resume with the value
Maybe nothing – indicating we wish to leave that value unchanged – or we replace the existing value with
Just value: myNewValue. When the map completes, we return a ZipDone zipper, indicating that we’re finished, and the term of the zipper is the collection of all those (existing-value, how-we-got-here-and-maybe-replaced-a-value continuation) pairs.
One of the reasons to use a zipper is so that the new version of your structure shares part of the original version’s structure, saving space. How much is shared is (entirely) determined by the mapping function you use.
What’s so nice about this form of zipper is that the zipper knows nothing about the traversal strategy the map uses (it only cares that it can send
#collect: to the structure), and the
#collect: method knows nothing at all about the zipper! One can just as easily apply the same zipper to trees or any other kind of structure.
If you’d like to play with the zipper, here’s the script for loading it:
Warning: this will work fine on the old interpreter VM, but if you’re using Cog, make sure you’re using the latest version: a bug in copying
ContextParts will cause errors like “Computation terminated”.