technology from back to front

The Other Kind of Zipper

“A zipper is a[n editable] suspended walk.”[1]

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:

Object subclass: #Zipper
    instanceVariableNames: 'term continuation'.

Zipper subclass: #ZipDone.

and behaviour

Zipper>>zipUp
    ^ [continuation value: Maybe nothing] reset.
ZipDone>>zipUp
    ^ term.

Zipper>>atEnd
    ^ false.

ZipDone>>atEnd
    ^ true.

Zipper>>next: anObject
    ^ [continuation value: anObject] reset.

(The reason we wrap #next: and #zipUp in a #reset will become apparent later.)

Incidental to our discussion, we have some helper classes:

Object subclass: #Maybe.

Maybe subclass: #Just
    instanceVariableNames: 'value'.

Maybe subclass: #Nothing.

Just>>maybe: aBlock default: anObject
    ^ aBlock value: value.

Nothing>>maybe: aBlock default: anObject
    ^ anObject.

Maybe class>>nothing
    ^ 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.

compose: aUnaryBlock
    ^ [:x | self value: (aUnaryBlock value: x)].

All the magic happens here:

Zipper>>zipOver: aCollection
    "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
            on: a
            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 #next: or #zipUp.

#zipOver:

returns a 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:

Installer ss
    project: 'Nutcracker';
    install: 'Maybe-fbs.4'.

Installer ss
    project: 'Control';
    install: 'Control-fbs.10'.

Installer ss
    project: 'Zippers';
    install: 'ZipperControl-fbs.5'.

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”.

[1] I found Oleg’s Zipper in Scheme a clearer picture of the core concept, even though the Haskell version has a nicer update interface.

by
Frank Shearar
on
30/06/11
 
 


7 + = eleven

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us