+If your trees are very big---say, millions of leaves---you can imagine how this would be quicker and more memory-efficient than traversing each tree to construct a list of its fringe, and then comparing the two lists so built to see if they're equal. For one thing, the zipper method can abort early if the fringes diverge early, without needing to traverse or build a list containing the rest of each tree's fringe.
+
+Let's sketch the implementation of this. We won't provide all the details for an implementation of the tree zipper (you'll need to fill those in), but we will sketch an interface for it.
+
+In these exercises, we'll help ourselves to OCaml's **record types**. These are nothing more than tuples with a pretty interface. Instead of saying:
+
+ # type blah = Blah of (int * int * (char -> bool));;
+
+and then having to remember which element in the triple was which:
+
+ # let b1 = Blah (1, (fun c -> c = 'M'), 2);;
+ Error: This expression has type int * (char -> bool) * int
+ but an expression was expected of type int * int * (char -> bool)
+ # (* damnit *)
+ # let b1 = Blah (1, 2, (fun c -> c = 'M'));;
+ val b1 : blah = Blah (1, 2, <fun>)
+
+records let you attach descriptive labels to the components of the tuple:
+
+ # type blah_record = { height : int; weight : int; char_tester : char -> bool };;
+ # let b2 = { height = 1; weight = 2; char_tester = (fun c -> c = 'M') };;
+ val b2 : blah_record = {height = 1; weight = 2; char_tester = <fun>}
+ # let b3 = { height = 1; char_tester = (fun c -> c = 'K'); weight = 3 };; (* also works *)
+ val b3 : blah_record = {height = 1; weight = 3; char_tester = <fun>}
+
+These were the strategies to extract the components of an unlabeled tuple:
+
+ let h = fst some_pair;; (* accessor functions fst and snd are only predefined for pairs *)
+
+ let (h, w, test) = b1;; (* works for arbitrary tuples *)
+
+ match b1 with
+ | (h, w, test) -> ...;; (* same as preceding *)
+
+Here is how you can extract the components of a labeled record:
+
+ let h = b2.height;; (* handy! *)
+
+ let {height = h; weight = w; char_tester = test} = b2 in
+ (* go on to use h, w, and test ... *)
+
+ match test with
+ | {height = h; weight = w; char_tester = test} ->
+ (* same as preceding *)
+
+Anyway, using record types, we might define the tree zipper interface like so. First, we define a type for leaf-labeled, binary trees:
+
+ type 'a tree = Leaf of 'a | Node of ('a tree * 'a tree)
+
+Next, the types for our tree zippers:
+
+ type 'a zipper = { in_focus: 'a tree; context : 'a context }
+ and 'a context = Root | Nonroot of 'a nonroot_context
+ and 'a nonroot_context = { up : 'a context; left: 'a tree option; right: 'a tree option }
+
+Unlike in seminar, here we represent the siblings as `'a tree option`s rather than `'a tree list`s. Since we're dealing with binary trees, each context will have exactly one sibling, either to the right or to the left.
+
+The following function takes an `'a tree` and returns an `'a zipper` focused on its root:
+
+ let new_zipper (t : 'a tree) : 'a zipper =
+ {in_focus = t; context = Root}
+
+Here are the beginnings of functions to move from one focused tree to another:
+
+ let rec move_botleft (z : 'a zipper) : 'a zipper =
+ (* returns z if the focused node in z has no children *)
+ (* else returns move_botleft (zipper which results from moving down from z's focused node to its leftmost child) *)
+ _____ (* YOU SUPPLY THE DEFINITION *)
+
+<!--
+ match z.in_focus with
+ | Leaf _ -> z
+ | Node(left, right) ->
+ move_botleft {in_focus = left; context = Nonroot {up = z.context; left = None; right = Some right}}
+-->
+
+
+ let rec move_right_or_up (z : 'a zipper) : 'a zipper option =
+ (* if it's possible to move right in z, returns Some (the result of doing so) *)
+ (* else if it's not possible to move any further up in z, returns None *)
+ (* else returns move_right_or_up (result of moving up in z) *)
+ _____ (* YOU SUPPLY THE DEFINITION *)
+
+<!--
+ match z.context with
+ | Nonroot {up; left= None; right = Some right} ->
+ Some {in_focus = right; context = Nonroot {up; left = Some z.in_focus; right = None}}