Zipper

Manipulating locations in a data structure.

Sometimes you want to manipulate a location inside a data structure, rather than the data itself. For example, consider a simple binary tree type:

data Tree a = Fork (Tree a) (Tree a) | Leaf a

and a sample tree t:

t = Fork (Fork (Leaf 1)
               (Leaf 2))
         (Fork (Leaf 3)
               (Leaf 4))

Each subtree of this tree occupies a certain location in the tree taken as a whole. The location consists of the subtree, along with the rest of the tree, which we think of the context of that subtree. For example, the context of

Leaf 2

in the above tree is

Fork (Fork (Leaf 1) @)
     (Fork (Leaf 3) (Leaf 4))

where @ marks the spot that the subtree appears in. One way of expressing this context is as a path from the root of the tree to the required subtree. To reach our subtree, we needed to go down the left branch, and then down the right one.

Thus we can represent a context as follows:

data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a)

Using this datatype, we can rewrite the sample context above in proper Haskell:

R (Leaf 1) (L Top (Fork (Leaf 3) (Leaf 4)))

Note that the context is actually written by giving the path from the subtree to the root (rather than the other way round).

Now we can define a tree location:

type Loc a = (Tree a, Cxt a)

and some useful functions for manipulating locations in a tree:

left :: Loc a -> Loc a
left (Fork l r, c) = (l, L c r)

right :: Loc a -> Loc a
right (Fork l r, c) = (r, R l c)

up :: Loc a -> Loc a
up (t, L c r) = (Fork t r, c)
up (t, R l c) = (Fork l t, c)

top :: Tree a -> Loc a
top t = (t, Top)

modify :: Loc a -> (Tree a -> Tree a) -> Loc a
modify (t, c) f = (f t, c)

It is instructive to look at an example of how a location gets transformed as we move from root to leaf. Recall our sample tree t. Let's name some of the relevant subtrees for brevity:

t = let tl = Fork (Leaf 1) (Leaf 2)
        tr = Fork (Leaf 3) (Leaf 4)
    in Fork tl tr

Then:

(left . right . top) t
= (left . right) (t, Top)
= left (tr, R tl Top)
= (Leaf 3, L (R tl Top) (Leaf 4))

This technique is due to GerardHuet (although he acknowledges it is probably folklore), who used it to implement a structural editor for first-order languages. See the article "The Zipper" in the JournalOfFunctionalProgramming.

The Web extends this pattern.

There's a principled way to get the necessary types for contexts and the context filling functions, namely by differentiating the data structure. The following site has some relevant papers: http://www.cs.nott.ac.uk/~ctm/ .

For an actual implementation in GenericHaskell, see the paper "Type-indexed data types" by Ralf Hinze, Johan Jeuring and Andres Löh, http://www.cs.uu.nl/~johanj/publications/tidata.pdf.

Some code: ["/Zipper"] ["/ZipperG"]

CategoryIdiom

Zipper

Navigation menu

Search