movements
[lambda.git] / topics / week12_list_and_tree_zippers.mdwn
index 2f5d5dc..89d83b6 100644 (file)
@@ -1,3 +1,5 @@
+<!-- λ ◊ ≠ ∃ Λ ∀ ≡ α β γ ρ ω φ ψ Ω ○ μ η δ ζ ξ ⋆ ★ • ∙ ● ⚫ 𝟎 𝟏 𝟐 𝟘 𝟙 𝟚 𝟬 𝟭 𝟮 ⇧ (U+2e17) ¢ -->
+
 [[!toc]]
 
 ##List Zippers##
@@ -213,7 +215,7 @@ siblings of the focussed tree:
 
     Branch (Leaf 2, Leaf 3), ([], [Leaf 4])
 
-We still need to add the rest of the context.  But just computed that
+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], [])
@@ -223,13 +225,13 @@ 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 `Context of (tree list) * (tree list) * context` as 
-`Context of (left siblings) * (right siblings) * (context of parent)`.
+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)))
+    (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
@@ -266,50 +268,33 @@ 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.
-Here's a complete tour:
+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>
-# let z1 = (t1, Root);;
-val z1 : zipper =
-  (Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]], Root)
-# let z2 = downleft z1;;
-val z2 : zipper =
-  (Leaf 1, Context ([], [Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]], Root))
-# let z3 = right z2;;
-val z3 : zipper =
-  (Branch [Branch [Leaf 2; Leaf 3]; Leaf 4], Context ([Leaf 1], [], Root))
-# let z4 = downleft z3;;
-val z4 : zipper =
-  (Branch [Leaf 2; Leaf 3],
-   Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))
-# let z5 = downleft z4;;
-val z5 : zipper =
-  (Leaf 2,
-   Context ([], [Leaf 3],
-    Context ([], [Leaf 4], Context ([Leaf 1], [], Root))))
-# let z6 = right z5;;
-val z6 : zipper =
-  (Leaf 3,
-   Context ([Leaf 2], [],
-    Context ([], [Leaf 4], Context ([Leaf 1], [], Root))))
-# let z7 = up z6;;
-val z7 : zipper =
-  (Branch [Leaf 2; Leaf 3],
-   Context ([], [Leaf 4], Context ([Leaf 1], [], Root)))
-# let z8 = right z7;;
-val z8 : zipper =
-  (Leaf 4,
-   Context ([Branch [Leaf 2; Leaf 3]], [], Context ([Leaf 1], [], Root)))
-# let z9 = up z8;;
-val z9 : zipper =
-  (Branch [Branch [Leaf 2; Leaf 3]; Leaf 4], Context ([Leaf 1], [], Root))
-# let z10 = up z9;;
-val z10 : zipper =
-  (Branch [Leaf 1; Branch [Branch [Leaf 2; Leaf 3]; Leaf 4]], Root)
-# z10 = z1;;
-- : bool = true
-# z10 == z1;;
-- : bool = false
+_|__
+|  |
+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: