Implement Zippers

[niklasdewally]

I have a plan for this, but its difficult to explain until I do it.

[niklasdewally]

Here’s my current thoughts on generic zippers, and how to implement them. I would appreciate any comments, questions, and corrections :)

TOC:

• Background
  • Zippers
  • Zippers as holes in types
  • Zippers as a suspended walk
• Outline to my approach

---

Background

This section briefly (badly) introduces the various concepts I am using to create the Zipper implementation. It is largely inspired by ^{1 2}.

Zippers

A Zipper is a data structure that stores a focus and a context.

For the sake of example, consider a binary tree:

In this case, the focus of the zipper is the current node and its children and the context is the rest of the tree, represented as an upward path from the root of the tree to the focus.

In code, this looks like this:

type Zipper a = (Node a, Context a)

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

data Context a = Top
               | Left  (Context a) (Tree a)
               | Right (Tree a)    (Context a)

The context Left (Context a) (Tree a) represents that we are currently on a leftmost node of the tree. It stores the way up the tree through the parent context, and the rest of the tree.

The context and node combined contains all that is needed to reconstruct the tree. For example, this function goes up a level:

up :: (Node a, Context a) -> Maybe (Node a, Context a)
up (node, Top) = Nothing
up (node, (Left parentCtx sibling)) = Just ((Branch node sibling), (parentCtx))
up (node, (Right sibling parentCtx)) = Just ((Branch sibling node), (parentCtx))

-- see https://wiki.haskell.org/Zipper for down, left, right

Usual operations are left, right, up,down.

The advantages of this approach is that replacing the focus and traversal to siblings is constant time.

For details, see the original paper by Huet, ³ or the many good tutorial style explanations online. ^{4 5 6}

Zippers as holes in types

Another, equivalent, view of the Zipper’s context is that it represents a one element hole in a data-structure. n general, the type of “one holed contexts” is the derivative (in the Leibnitz sense) of the type of the data structure itself. This allows for the mechanical derivation of Zippers on arbitrary types.

The disadvantage of this is that the type theory is too confusing for me, and I am not sure we can do this in the Rust type system.

Zippers as a suspended walk

Kiselyov Zippers ^{7 8} view Zippers as pausing a traversal over the entire data structure. In other words, Zippers can be viewed as a next function (continuation) and a current node.

There is lots of cool and complicated stuff about this on his website ⁹ and in this blog series ¹⁰ - including concurrent zippers which allow multiple cursors to navigate a data structure at once.

Outline to my approach

My priorities are:

1. no scary types
2. reusing existing uniplate functions

Contexts in the standard Zipper implementation are good, but each enum variant requires manual implementation for each function.

However, uniplate gives us a function context that can reconstruct an expression given some new children, and children, which returns all children as a list. Both of these already ignore non nested types and are only parameterised over the As in A (the Bs in A are stored inside the context function as a closure). This simplifies things massively - all arbitrary enum types, regardless of whatever other types they contain, are now represented as trees with an arbitrary number of homogeneous children.

Using lists and the reconstruction function, we can make the context for tree shaped data:

type Zipper<A: Uniplate> = (Context<A>,A);
struct Context<A: Uniplate> {
  predecessors: Vec<A>,
  sucesssors: Vec<A>,
  parent: Box<Option<Context>>,
  reconstruct_fn: Box<Fn<A,Vec<A>,A>>
}

This gives all information needed to reconstruct the tree and move up, down, left and right.

An alternative approach would be storing and moving in terms of one hole context functions, where we store the children as part of the reconstruction function.

EDIT: The simplifications i made makes stuff like finding an A inside a B inside an A when traversing over A's hard, but Biplates might fix that, and we probably won't need that anyways.

Footnotes

1. https://okmij.org/ftp/continuations/zipper.html ↩

2. https://pavpanchekha.com/blog/zippers/huet.html ↩

3. https://www.cambridge.org/core/services/aop-cambridge-core/content/view/0C058890B8A9B588F26E6D68CF0CE204/S0956796897002864a.pdf/zipper.pdf ↩

4. https://pavpanchekha.com/blog/zippers/huet.html ↩

5. https://learnyouahaskell.com/zippers ↩

6. https://en.wikibooks.org/wiki/Haskell/Zippers#Ariadne’s_Zipper ↩

7. https://okmij.org/ftp/continuations/zipper.html ↩

8. https://pavpanchekha.com/blog/zippers/huet.html ↩

9. https://okmij.org/ftp/continuations/zipper.html ↩

10. https://pavpanchekha.com/blog/zippers/huet.html ↩

[niklasdewally]

Overthought things somewhat again, but I think this could work.

The primary open questions I am unsure about are algorithmic complexity, whether storing all those closures will be horrible or not, and whether uniplate actually reduces things down to a tree like I think.

RFC @Kieranoski702 @ozgurakgun @gskorokhod