Zippers in Haskell and Javascript (Part 1)

Sometimes we want to manipulate a location inside the data structure, rather than the data itself.

Suppose we have a data structure, a tree:

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

And a sample tree:

Branch (Branch (Leaf 1)
               (Leaf 2))
       (Branch (Leaf 3)
               (Leaf 4))

In this case let’s manipulate the location of the subtree, Leaf 2.

To know its location, we need to know its surroundings (context) and the place (focus)

tree = Branch (Branch (Leaf 1)
                      (Leaf 2)) -- Location of `Leaf 2`
              (Branch (Leaf 3)
                      (Leaf 4))
               
-- Context surrounding `Leaf 2`
context = Branch (Branch (Leaf 1)
                         _
                 (Branch (Leaf 3)
                         (Leaf 4))

-- Focus of `Leaf 2`
focus = Leaf 2

As such we can define the location as a product of context and the focus:

type Loc a = (Tree a, Cxt a)

Context is in turn defined relative to the hole, where Context a refers to the context of the parent, Tree a refers to the other child of the parent.

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

We can then define functions to manipulate locations in the tree:

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

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

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

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

upmost :: Loc a -> Loc a
upmost l@(t, Top) = l
upmost l = upmost (up l)

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

Zippers in Haskell and Javascript (Part 2)