Zipper

Zipper is a:

• persistent data structure
• means of “navigation” through another data structure with ability to “change” it on the go (without changing the original structure), similar to functional optics.

Zipper was proposed (invented?) by G’erard Huet in 1997. You can read his original paper - Functional Pearl. The Zipper, 1997.

Almost every programmer has faced the problem of representing a tree together with a subtree that is the focus of attention, where that focus may move left, right, up or down the tree. The Zipper is Huet’s nifty name for a nifty data structure which fulfills this need. I wish I had known of it when I faced this task, because the solution I came up with was not quite so efficient or elegant as the Zipper.

Initially Huet proposed Zipper as the way to work with trees (specifically in the context of functional programming, where instead of mutations you need to use persistent data structures).

Later Conor McBride realized that idea of the Zipper can be generalized and used other data structures (not just trees). You can read his original paper - The Derivative of a Regular Type is its Type of One-Hole Contexts, 2009.

And even more he proposed that derivative of type for data structure gives type of the one hole context for the given data structure (e.g. zipper without focus).

Linked list

• is a simple data structure which allows to prepend and pop element (LIFO, stack)
• it can be used as immutable (persistent) data structure
• it allows to navigate only in one direction (from head to tail)

Example

Linked list of lenght 10. 1 is a head of a linked list. 10 is a tail of a linked list

Zipper for a linked list

Let’s start with the Zipper for linked list. Linked list is simpler data structure than tree. Here is a type for linked list:

List(T) = T * List(T) + 1

Here I use algebraic data type notation:

• List(T) - parametrised type, in terms of TypeScript it would be List<T>
• A * B - product type, in terms of TypeScript it could be tupple [A, B] or object {first: A, second: B}
• A + B - sum type, in terms of TypeScript A | B
• 1 is a type with one value, in many language this is type which contains single value null. In Lisp they use empty tuple for null ()

Final type of List in TypeScript:

type List<T> = {
  value: T;
  next: List<T>;
} | null;

Derivative of List(T) is List(T) * List(T). Which would correspond to left and right context e.g. values before focus and values after focus (or “hole”). So Zipper for linked list would be:

ListZipper(T) = List(T) * T * List(T)

Or in terms of TypeScript:

type ListZipper<T> = {
  left: List<T>;
  focus: T;
  right: List<T>;
};

We can define two direction for navigation: left and right.

const left = <T>(zipper: ListZipper<T>): ListZipper<T> => {
  return {
    left: zipper.left.next,
    focus: zipper.left.value,
    right: cons(zipper.focus, zipper.right),
  };
};

const right = <T>(zipper: ListZipper<T>): ListZipper<T> => {
  return {
    left: cons(zipper.focus, zipper.left),
    focus: zipper.right.value,
    right: zipper.right.next,
  };
};

Vizualisation of a zipper

• Red and gray nodes represent items from original list
• There are no references to gray items from Zipper, which means if there are no references from the outside they could be removed by garbage collector
• When zipper is created it doesn’t need to traverse structure upfront. We put first element in the focus and the rest of the list in the right context (suffix)
• Blue and green nodes represent new list which zipper builds upon navigation
• We can change value in focus and continue navigation. This won’t change value in original list
• If we would navigate to the end to the list, Zipper will be fully “detached” from the original list
• Pink “zone” represnts Zipper itself - left context (prefix), focus, right context (suffix)

Tree

• ”DAG” vizualization - is how we typically imagine tree data structure. Actually this vizualization more appropriate for Directed Acyclic Graph. In DAG children may be unordered.
• ”LCRS tree” vizualization - this is how typically Left-child right-sibling tree vizualized. It shows that children in tree are ordered.

Zipper for a tree

• Pink “zone” represnts Zipper itself - left context, focus, right context, top context
• Zipper vizualization “makes more sense” in “LCRS tree” mode

”Cycled tree”

I call it “cycled tree”, because it is the same data structure as tree, but cycle is created using mutation (or letrec). It is actually graph.

Zipper for a “cycled tree”

Cycled structure serves as pattern to generate infinite structure in Zipper.