add note

[lambda.git] / topics / week12_list_and_tree_zippers.mdwn

<!-- λ ◊ ≠ ∃ Λ ∀ ≡ α β γ ρ ω φ ψ Ω ○ μ η δ ζ ξ ⋆ ★ • ∙ ● ⚫ 𝟎 𝟏 𝟐 𝟘 𝟙 𝟚 𝟬 𝟭 𝟮 ⇧ (U+2e17) ¢ -->

[[!toc]]

##List Zippers##

Say you've got some moderately-complex function for searching through a list, for example:

        let find_nth (test : 'a -> bool) (n : int) (lst : 'a list) : (int * 'a) ->
            let rec helper (position : int) n lst =
                match lst with
                | [] -> failwith "not found"
                | x :: xs when test x -> (if n = 1
                    then (position, x)
                    else helper (position + 1) (n - 1) xs
                )
                | x :: xs -> helper (position + 1) n xs
            in helper 0 n lst;;

This searches for the `n`th element of a list that satisfies the predicate `test`, and returns a pair containing the position of that element, and the element itself. (We follow the dominant convention of counting list positions from the left starting at 0.) Good. But now what if you wanted to retrieve a different kind of information, such as the `n`th element matching `test`, together with its preceding and succeeding elements? In a real situation, you'd want to develop some good strategy for reporting when the target element doesn't have a predecessor and successor; but we'll just simplify here and report them as having some default value:

        let find_nth' (test : 'a -> bool) (n : int) (lst : 'a list) (default : 'a) : ('a * 'a * 'a) ->
            let rec helper (predecessor : 'a) n lst =
                match lst with
                | [] -> failwith "not found"
                | x :: xs when test x -> (if n = 1
                    then (predecessor, x, match xs with [] -> default | y::ys -> y)
                    else helper x (n - 1) xs
                )
                | x :: xs -> helper x n xs
            in helper default n lst;;

This duplicates a lot of the structure of `find_nth`; it just has enough different code to retrieve different information when the matching element is found. But now what if you wanted to retrieve yet a different kind of information...?

Ideally, there should be some way to factor out the code to find the target element---the `n`th element of the list satisfying the predicate `test`---from the code that retrieves the information you want once the target is found. We might build upon the initial `find_nth` function, since that returns the *position* of the matching element. We could hand that result off to some other function that's designed to retrieve information of a specific sort surrounding that position. But suppose our list has millions of elements, and the target element is at position 600512. The search function will already have traversed 600512 elements of the list looking for the target, then the retrieval function would have to *start again from the beginning* and traverse those same 600512 elements again. It could go a bit faster, since it doesn't have to check each element against `test` as it traverses. It already knows how far it has to travel. But still, this should seem a bit wasteful.

Here's an idea. What if we had some way of representing a list as "broken" at a specific point. For example, if our base list is:

        [10; 20; 30; 40; 50; 60; 70; 80; 90]

we might imagine the list "broken" at position 3 like this:

                    40;
                30;     50;
            20;             60;
        [10;                    70;
                                    80;
                                        90]

Then if we move one step forward in the list, it would be "broken" at position 4:

                        50;
                    40;     60;
                30;             70;
            20;                     80;
        [10;                            90]

If we had some convenient representation of these "broken" lists, then our search function could hand *that* off to the retrieval function, and the retrieval function could start right at the position where the list was broken, without having to start at the beginning and traverse many elements to get there. The retrieval function would also be able to inspect elements both forwards and backwards from the position where the list was "broken".

The kind of data structure we're looking for here is called a **list zipper**. To represent our first broken list, we'd use two lists: (1) containing the elements in the left branch, preceding the target or focused element, *in the order reverse to their appearance in the base list*. (2) containing the target or focus element and the rest of the list, in normal order. So:

                    40;
                30;     50;
            20;             60;
        [10;                    70;
                                    80;
                                        90]

would be represented as `([30; 20; 10], [40; 50; 60; 70; 80; 90])`. To move forward in the base list, we pop the head element `40` off of the head element of the second list in the zipper, and push it onto the first list, getting `([40; 30; 20; 10], [50; 60; 70; 80; 90])`. To move backwards again, we pop off of the first list, and push it onto the second. To reconstruct the base list, we just "moved backwards" until the first list is empty. (This is supposed to evoke the image of zipping up a zipper; hence the data structure's name.)

Last time we gave the class, we had some discussion of what's the right way to apply the "zipper" metaphor. I suggest it's best to think of the tab of the zipper being here:

                 t
                  a
                   b
                    40;
                30;     50;
            20;             60;
        [10;                    70;
                                    80;
                                        90]

And imagine that you're just seeing the left half of a real-zipper, rotated 60 degrees counter-clockwise. When the list is all "zipped up", we've "move backwards" to the state where the first element is targeted or in focus:

    ([], [10; 20; 30; 40; 50; 60; 70; 80; 90])

However you understand the "zipper" metaphor, this is a very handy data structure, and it will become even more handy when we translate it over to more complicated base structures, like trees. To help get a good conceptual grip on how to do that, it's useful to introduce a kind of symbolism for talking about zippers. This is just a metalanguage notation, for us theorists.

    [10; 20; 30; *; 50; 60; 70; 80; 90], * filled by 40

would represent a list zipper where the break is at position 3, and the element occupying that position is `40`. For a list zipper, this could be implemented using the pairs-of-lists structure described above.

Alternatively, we could present it in a form more like we used in the seminar for tree zippers:

    in_focus = 40, context = (before = [30; 20; 10], after = [50; 60; 70; 80; 90])

In order to facilitate the discussion of tree zippers, 
let's consolidate a bit with a concrete implementation.

<pre>
type int_list_zipper = int * (int list) * (int list)
let zip_open (z:int_list_zipper):int_list_zipper = match z with
    focus, ls, r::rs -> r, focus::ls, rs
  | _ -> z
let zip_closed (z:int_list_zipper):int_list_zipper = match z with
    focus, l::ls, rs -> l, ls, focus::rs
</pre>

Here, an int list zipper is an int list with one element in focus.
The context of that element is divided into two subparts: the left
context, which gives the elements adjacent to the focussed element
first (so looks reversed relative to the original list); and the right
context, which is just the remainder of the list to the right of the
focussed element.

Then we have the following behavior:

<pre>
# let z1:int_list_zipper = 1, [], [2;3;4];;
val z1 : int_list_zipper = (1, [], [2; 3; 4])
# let z2 = zip_open z1;;
val z2 : int_list_zipper = (2, [1], [3; 4])
# let z3 = zip_open z2;;
val z3 : int_list_zipper = (3, [2; 1], [4])
# let z4 = zip_closed (zip_closed z3);;
val z4 : int_list_zipper = (1, [], [2; 3; 4])
# z4 = z1;;
# - : bool = true
</pre>



##Tree Zippers##

Now how could we translate a zipper-like structure over to trees? What we're aiming for is a way to keep track of where we are in a tree, in the same way that the "broken" lists let us keep track of where we are in the base list.

Thus tree zippers are analogous to list zippers, but with one
additional dimension to deal with: in addition to needing to shift
focus to the left or to the right, we want to be able to shift the
focus up or down.

In order to emphasize the similarity with list zippers, we'll use
trees that are conceived of as lists of lists:

    type tree = Leaf of int | Branch of tree list

On this conception, a tree is nothing more than a list of subtrees.
For instance, we might have

    let t1 = Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]];;

    _|__
    |  |
    1  |
      _|__
      |  |
      |  4
     _|__
     |  |
     2  3

For simplicity, we'll work with trees that don't have labels on their
internal nodes.  Note that there can be any number of siblings, though
we'll work with binary trees here to prevent clutter.

    _*__
    |  |
    1  |
      _|__
      |  |
      |  4
     _|__
     |  |
     2  3

How should we represent a tree with the starred subtree in focus?
Well, that's easy: the focussed element is the entire tree, and the
context is null.  We'll represent this as the ordered pair (t1, Root).

    _|__
    |  |
    1  |
      _*__
      |  |
      |  4
     _|__
     |  |
     2  3

How should we represent a tree with this other starred subtree in
focus?  Well, viewing this tree as a list of subtrees, we've merely
put the second element of the list in focus.  We can almost just use
the list zipper technique from the previous section:

    Branch (Branch (Leaf 2, Leaf 3), Leaf 4), ([Leaf 1], [])

This is just a list zipper where the list elements are trees instead
of ints.

But this won't be quite enough if we go one more level down.

    _|__
    |  |
    1  |
      _|__
      |  |
      |  4
     _*__
     |  |
     2  3

The focussed element is the subtree Branch (Leaf 2, Leaf 3).
And we know how to represent the part of the context that involves the
siblings of the focussed tree:

    Branch (Leaf 2, Leaf 3), ([], [Leaf 4])

We still need to add the rest of the context.  But we just computed that
context a minute ago.  It was ([Leaf 1], []).  If we add it here, we get:

    Branch (Leaf 2, Leaf 3), ([], [Leaf 4], ([Leaf 1], [])

Here's the type suggested by this idea:

    type context = Root | Context of (tree list) * (tree list) * context
    type zipper = tree * context

We can gloss the triple `(tree list) * (tree list) * context` as 
`(left siblings) * (right siblings) * (context of parent)`.

Here, then, is the full tree zipper we've been looking for:

    (Branch [Leaf 2; Leaf 3],
     Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))

Just as with the simple list zipper, note that elements that are near
the focussed element in the tree are near the focussed element in the
zipper representation.  This is what makes it easy to shift the
focus to nearby elements in the tree.

It should be clear that moving left and right in the tree zipper is
just like moving left and right in a list zipper. 

Moving down requires looking inside the tree in focus, and grabbing
hold of one of its subtrees.  Since that subtree is the new focus, its
context will be the list zipper consisting of its siblings (also
recovered from the original focus).

    let downleft (z:zipper):zipper = match z with
        (Branch (l::rest)), context -> l, Context ([], rest, context)

Moving up involves gathering up the left and right siblings and
re-building the original subtree.  It's easiest to do this when the
sibling zipper is fully closed, i.e., when the list of left siblings
is empty:

    let rec up (z:zipper):zipper = match z with
        focus, Context ([], rs, rest) -> Branch (focus::rs), rest
      | focus, Context (l::ls, _, _) -> up (left z)

The second match says that if the list of left siblings isn't empty,
we just shift focus left and try again.

This tree zipper works for trees with arbitrary numbers of siblings
per subtree.  If one were designing a tree zipper for a more
restricted kind of tree, however, such as a binary tree, one would
probably not represent siblings with a list zipper, but with something
more special-purpose and economical.

With these functions, we can refocus on any part of the tree.
Let's abbreviate a tree zipper like this:

    [2;3], ([] [4] ([1], [], Root)) 

    ≡ (Branch [Leaf 2; Leaf 3],
       Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))

Then we can take a tour of the original tree like this:

<pre>
_|__
|  |
1  |
  _|__
  |  |
  |  4
 _|__
 |  |
 2  3

    [1;[[2;3];4]],Root           =                                                              [1;[[2;3];4]],Root
  downleft                                                                                               up
1, ([],[[2;3];4],Root) right [[2;3];4],([1],[],Root)                                            [[2;3];4],([1],[],Root)
                           downleft                                                                      up                                
                        [2;3],([],[4],([1],[],Root))         [2;3],([],[4],([1],[],Root)) right 4,([2;3],[],([1],[],Root))
                      downleft                                           up
                    2, ([],[3],([],[4],([1],[],Root))) right 3, ([2],[],([],[4],([1],[],Root)))
</pre>

Here's more on zippers:

*       [[!wikipedia Zipper (data structure)]]
*       [Haskell wikibook on zippers](http://en.wikibooks.org/wiki/Haskell/Zippers)
*       Huet, Gerard. ["Functional Pearl: The Zipper"](http://www.st.cs.uni-sb.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf) Journal of Functional Programming 7 (5): 549-554, September 1997.
*       As always, [Oleg](http://okmij.org/ftp/continuations/Continuations.html#zipper) takes this a few steps deeper.