Zippers

(Not updated very recently)

Programming in a purely functional languages means no mutation. So, “updating” a data structure means creating a copy with the desired changes.

insertAt :: Int -> a -> [a] -> [a]
insertAt 0 x ys             = x : ys
insertAt i x (y:ys) | i > 0 = y : insertAt (pred i) x ys 

> "12345" |> insertAt 3 'A' |> insertAt 4 'B' |> insertAt 5 'C'

As you may learn in subsequent courses on data structures, or compilers, for functional languages, a good compiler will generate code that does use pointers to reuse memory when parts of one data structured is shared with another.

In the above example, the linked list with the numbers 4 and 5 will be shared by all four lists (the original one and the result of each call to insertAt). But there will be four separate linked lists for the first three numbers 1 and 3. Three separate A nodes (hence, two duplicates) will be created and two separate B nodes (hence, one duplicate) will be created.

At the end of the today, some of this re-allocation is unavoidable. But, in cases where multiple updates occur at a similar place in the data structure, it would be nice to avoid the extra, unnecessary copies — as well as the time to repeatedly traverse to the same location — making a batch of changes before “moving” to another part of the data structure. That is, want to maintain a “focus” or “cursor” or “context” within the data structure, to allow fast traversal and changes around it, and then “rewind” or “zip up” the data structure to its usual representation later on.

The key to the zipper pattern is to maintain links from a cursor back to the root, thus inverting the typical flow of “pointers” in the data structure. All pointers should point out from the cursor.

Lists

data ListZipper a
  = Z { revFront :: [a]    -- "cursor" (index) == length revFront
      , back     :: [a]
      }
  deriving (Show)

Create zipper:

fromList :: [a] -> ListZipper a
fromList xs = Z [] xs

Navigate left and right:

goLeft, goRight :: ListZipper a -> ListZipper a
goLeft  (Z (x:revFront) back) = Z revFront (x:back)
goRight (Z revFront (x:back)) = Z (x:revFront) back

Insertion at cursor:

insertAtCursor x (Z revFront back) = Z (x:revFront) back

Zip up into usual representation:

toList :: ListZipper a -> [a]
toList (Z revFront back) = reverse revFront ++ back

For example:

> :{
"12345"
  |> fromList
  |> goRight |> goRight |> goRight
  |> insertAtCursor 'A'
  |> insertAtCursor 'B'
  |> insertAtCursor 'C'
  |> toList
:}
"123ABC45"

Binary Trees

data BinaryTree a
  = Node a (BinaryTree a) (BinaryTree a)
  | Empty
  deriving (Show)

data BinaryTreeZipper a = Z (BinaryTree a, Path a)
  deriving (Show)

type PathStep a =
  ( a                                     -- parent node value
  , Either (BinaryTree a) (BinaryTree a)  -- left or right child
  )

type Path a = [PathStep a]

A PathStep that holds a Left left child is a “right” step. A PathStep that holds a Right right child is a “left” step.

Create zipper:

fromTree :: BinaryTree a -> BinaryTreeZipper a
fromTree t = Z (t, [])

Navigate:

goDownLeft, goDownRight, goUp, goLeft, goRight :: BinaryTreeZipper a -> BinaryTreeZipper a

goDownLeft (Z (Node x left right, up)) = Z (left, (x, Right right) : up)
goDownRight (Z (Node x left right, up)) = Z (right, (x, Left left) : up)

goUp (Z (t, (x, Left left) : up)) = Z (Node x left t, up)
goUp (Z (t, (x, Right right) : up)) = Z (Node x t right, up)

goLeft (Z (t, (x, Left left) : up)) = Z (left, (x, Right t) : up)
goRight (Z (t, (x, Right right) : up)) = Z (right, (x, Left t) : up)

Zip up into usual representation:

toTree :: BinaryTreeZipper a -> BinaryTree a
toTree (Z (t, [])) = t
toTree (Z (t, (x, Right right) : up)) = toTree (Z (Node x t right, up))
toTree (Z (t, (x, Left left) : up)) = toTree (Z (Node x left t, up))

Multi Trees

Generalize binary trees to ones with arbitrary number of children:

data MultiTree a
  = Node a [MultiTree a] -- children intended to be non-empty
  | Empty
  deriving (Show)

data MultiTreeZipper a = Z (MultiTree a, Path a)
  deriving (Show)

type PathStep a =
  ( a               -- parent node value
  , [MultiTree a]   -- left sibings, in reverse order
  , [MultiTree a]   -- right siblings
  )

type Path a = [PathStep a]

Navigation; notice that goUp is the expensive case, requiring a call to reverse in order to zip the entire list of children back up:

goLeft, goRight, goUp, goDownFirst :: MultiTreeZipper a -> MultiTreeZipper a

goLeft (Z (t, (x, l:left, right) : up)) = Z (l, (x, left, t:right) : up)
goRight (Z (t, (x, left, r:right) : up)) = Z (r, (x, t:left, right) : up)
goUp (Z (t, (x, left, right) : up)) = Z (Node x (reverse left ++ [t] ++ right), up)
goDownFirst (Z (Node x (t:children), up)) = Z (t, (x, [], children) : up)

Reading / Source Files