Zippers

A zipper is a technique for implementing data structures (such as lists and trees) with some idea of a focus on one particular element, at the same time allowing for fast, functional (immutable) updates of a specific point in the structure.

Let’s try building a list in the style of a zipper.

First we define a data type for a list zipper.

(** A list zipper.
    It maintains focus on 1 particular element in the list. *)
type 'a list_zipper = 'a list * 'a list

Strange enough, a list zipper is made up of 2 lists, let’s call it back and front. (This may seem strange, but we will see the benefits soon.)

Let’s have a convenience function to build a list zipper from a normal list.

(** Builds a list zipper from a list. *)
let zipper_of_list xs = ([], xs)

The initial focus of the list zipper will be the first element of the front.

We can move the focus forward on to the next element of the front

(** Move the focus in the list zipper forward *)
let forward z =
  match z with
  | (bs, x::xs) -> Some (x::bs, xs)
  | (_, []) -> None

The interesting here is that the back list is actually reversed. Given a list [1; 2; 3; 4], if we build a zipper and focused on 3, the front and back list will look like this:

front = [2; 1]
back = [3; 4]

Notice how we cannot concatenate the front and the back list to get the original list. In fact, to reconstruct the original list, the easy way is:

(** Converts a list zipper back into a list. *)
let list_of_zipper (z : 'a list_zipper) =
  match z with
  | xs, ys -> List.rev xs @ ys

This reversed form is how we get moving focus to be efficient.

And similarly, we can move the focus backwards.

(** Move the focus in the list zipper backward *)
let backward z =
  match z with
  | (b::bs, xs) -> Some (bs, b::xs)
  | ([], _) -> None

Here, the :: operator (like cons), is fast and we can only do this if the back list is reversed.

The last operation the list zipper supports is changing the focused element.

(** Set the current focused value in the list to x *)
let set x z =
  match z with
  | (bs, _::xs) -> Some (bs, x::xs)
  | (_, []) -> None

With this data structure and the operations defined, you can get fast, functional updates on a list:

(* construct a simple list zipper *)
let z = zipper_of_list [1; 2; 3; 4]

let twice_forward_once_backward_and_set =
  z
  |> forward
  |> and_then forward
  |> and_then backward
  |> and_then (set 5)
(* z remains unchanged *)
(* twice_forward_once_backward_and_set is now [1; 5; 3; 4] *)

If this was instead performed on a normal cons-nil list, you would only be able to get fast updates on the next cons cell (instead of the currently focused one), or you would have to traverse up till the cell before the current.

The examples in this post have are available here. You can also find a experimental implementation of a tree with zipper in the repository.

References

https://en.wikipedia.org/wiki/Zipper_(data_structure)

http://learnyouahaskell.com/zippers

http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip1/

http://okmij.org/ftp/continuations/zipper.html