- Share an interesting data structure
- Show some Scala code

at your peril!

- Reification of a walk
- Derivative of a data structure
- A data structure with a hole
- Just something useful

It allows us to navigate a data structure and modify components as we go along

"Solving" the in-place edit "problem"

- O(1) - In Place Update

vs

- O(n)/O(log n) - Update

Take a List[T],

we can make a Zipper of form,

(before: List[T], focus: T, after: List[T])

val ls = List('a','b','c','d','e')

if 'd' is the focus

val zipper = (['c','b','a'],'d',['e'])

case class ZippedList[T](before: List[T], focus: T, after: List[T]) { def goLeft(): ZippedList[T] = before match { case Nil => throw new Exception("Can't move left") case x::xs => ZippedList(xs,x,focus::after) } def goRight(): ZippedList[T] = after match { case Nil => throw new Exception("Can't move right") case x::xs => ZippedList(focus::before,x,xs) } def update(f: T => T): ZippedList[T] = ZippedList(before,f(focus),after) def zipUp(): List[T] = (focus :: before).reverse ++ after }

PATH, FOCUS, REST

Take a binary tree with values,

abstract class BTree[A] case class Leaf[A](value: A) extends BTree[A] case class Node[A](value: A, left: BTree[A], right: BTree[A]) extends BTree[A]

Simplify to Path, Focus

case class ZippedTree[T](path: List[Decision[BTree[T]]], focus: BTree[T])

def goLeft() : ZippedTree[T] = focus match { case Leaf(_) => throw new Exception("Can't move left") case Node(_,l,_) => ZippedTree(Left(focus)::path,l) }

abstract class Decision[T] case class Left[T](value: T) extends Decision[T] case class Right[T](value: T) extends Decision[T]

def goRight() : ZippedTree[T] = focus match { case Leaf(_) => throw new Exception("Can't move right") case Node(_,_,r) => ZippedTree(Right(focus)::path,r) }

def goUp() : ZippedTree[T] = path match { case Nil => throw new Exception("Can't go up") case Left(Node(v,_,r)) :: rest => ZippedTree(rest,Node(v,focus,r)) case Right(Node(v,l,_)) :: rest => ZippedTree(rest,Node(v,l,focus)) }

def update(f: BTree[T] => BTree[T]): ZippedTree[T] = ZippedTree(path,f(focus))

def zipUp(): BTree[T] = { def rollup(z: ZippedTree[T]): BTree[T] = z match { case ZippedTree(Nil,f) => f case x => rollup(x.goUp()) } rollup(this) }

val t: BTree[Int] = Node(1, Node(7, Leaf(3), Leaf(4)), Node(7, Node(7, Leaf(9), Leaf(2)), Leaf(4)))

<*Insert bad demo here...*>

- N-ary Trees
- Streams
- ...any simple sum, product or recursive type

What are we doing?

Really all about creating paths to the current focus

Bit more formality

Path is a list of decisions, so let's annotate our decision and store the siblings of a node in the tree.

path to f is;

Left(N2) :: Left(N1)

Left(N2) :: Left(N1) + f => ZIPPER

Since we can recover the tree from the Zipper,

Left(N2) :: Left(N1) is the tree minus f,

the tree with a hole

Left(N2) :: Left(N1)

That's a one hole context of BTree,

where BTree is a product type of Leaf | BTree*BTree

The notation * indicates a product type.

*Think any tree with any other tree*

You can do the same for ternary trees

Leaf | TTree*TTree*TTree

Each decision we make in a BTree has the type

Decision[Btree] which can be expressed

Left(BTree) | Right(BTree)

Which happens to be a sum type, BTree+BTree

*Think all lefts and all rights*

So a generous rewriting may give us,

BTree = 1 + BTree^2

TTree = 1 + TTree^3

∂BTree = 2BTree

∂TTree = 3TTree …

The derivative of a regular type is its type of one-hole contexts

In theory it is possible to synthesise a Zipper from any regular type, with arbitrary navigation and update.

In practise we need more type-level programing...