001    package fj.data;
002    
003    import fj.F;
004    import fj.F2;
005    import fj.F4;
006    import fj.P;
007    import fj.P1;
008    import fj.P2;
009    import fj.P3;
010    import fj.P4;
011    import static fj.Function.*;
012    import static fj.F2W.$$;
013    import fj.function.Booleans;
014    import static fj.data.Option.some;
015    import static fj.data.Option.none;
016    import static fj.data.Tree.node;
017    import static fj.data.Tree.unfoldTree;
018    import static fj.data.Stream.nil;
019    import static fj.data.Stream.unfold;
020    import fj.pre.Equal;
021    import fj.pre.Show;
022    import static fj.pre.Show.*;
023    import static fj.pre.Equal.*;
024    
025    import java.util.Iterator;
026    
027    /**
028     * Provides a zipper structure for rose trees, which is a Tree supplied with a location within that tree.
029     * Provides navigation, insertion, deletion, and memorization of visited locations within a tree.
030     */
031    public class TreeZipper<A> implements Iterable<TreeZipper<A>> {
032    
033      /**
034       * Returns an iterator of all the positions of this TreeZipper. Exists for use with the foreach syntax.
035       *
036       * @return An iterator of all the positions of this TreeZipper.
037       */
038      public Iterator<TreeZipper<A>> iterator() {
039        return positions().toTree().iterator();
040      }
041    
042      private final Tree<A> tree;
043      private final Stream<Tree<A>> lefts;
044      private final Stream<Tree<A>> rights;
045      private final Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>> parents;
046    
047      private TreeZipper(final Tree<A> tree,
048                         final Stream<Tree<A>> lefts,
049                         final Stream<Tree<A>> rights,
050                         final Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>> parents) {
051        this.tree = tree;
052        this.lefts = lefts;
053        this.rights = rights;
054        this.parents = parents;
055      }
056    
057      /**
058       * Creates a new tree zipper given a currently selected tree, a forest on the left, a forest on the right,
059       * and a stream of parent contexts.
060       *
061       * @param tree    The currently selected tree.
062       * @param lefts   The selected tree's left siblings, closest first.
063       * @param rights  The selected tree's right siblings, closest first.
064       * @param parents The parent of the selected tree, and the parent's siblings.
065       * @return A new zipper with the given tree selected, and the given forests on the left and right.
066       */
067      public static <A> TreeZipper<A> treeZipper(final Tree<A> tree,
068                                                 final Stream<Tree<A>> lefts,
069                                                 final Stream<Tree<A>> rights,
070                                                 final Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>> parents) {
071        return new TreeZipper<A>(tree, lefts, rights, parents);
072      }
073    
074      /**
075       * First-class constructor for tree zippers.
076       *
077       * @return A function that returns a new tree zipper, given a selected tree, left and right siblings,
078       *         and a parent context.
079       */
080      public static <A>
081      F<Tree<A>, F<Stream<Tree<A>>, F<Stream<Tree<A>>, F<Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>>, TreeZipper<A>>>>>
082      treeZipper() {
083        return curry(
084            new F4<Tree<A>, Stream<Tree<A>>, Stream<Tree<A>>, Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>>, TreeZipper<A>>() {
085              public TreeZipper<A> f(final Tree<A> tree,
086                                     final Stream<Tree<A>> lefts,
087                                     final Stream<Tree<A>> rights,
088                                     final Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>> parents) {
089                return treeZipper(tree, lefts, rights, parents);
090              }
091            });
092      }
093    
094      /**
095       * Returns the product-4 representation of this zipper.
096       *
097       * @return the product-4 representation of this zipper.
098       */
099      public P4<Tree<A>, Stream<Tree<A>>, Stream<Tree<A>>, Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>>> p() {
100        return P.p(tree, lefts, rights, parents);
101      }
102    
103      /**
104       * A first-class function that returns the product-4 representation of a given zipper.
105       *
106       * @return a function that converts a given zipper to its product-4 representation.
107       */
108      public static <A>
109      F<TreeZipper<A>, P4<Tree<A>, Stream<Tree<A>>, Stream<Tree<A>>, Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>>>> p_() {
110        return new F<
111            TreeZipper<A>,
112            P4<Tree<A>,
113                Stream<Tree<A>>,
114                Stream<Tree<A>>,
115                Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>>>>() {
116          public P4<
117              Tree<A>,
118              Stream<Tree<A>>,
119              Stream<Tree<A>>,
120              Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>>> f(final TreeZipper<A> a) {
121            return a.p();
122          }
123        };
124      }
125    
126      /**
127       * An Equal instance for tree zippers.
128       *
129       * @param e An Equal instance for tree elements.
130       * @return An Equal instance for tree zippers.
131       */
132      public static <A> Equal<TreeZipper<A>> eq(final Equal<A> e) {
133        return p4Equal(
134            treeEqual(e),
135            streamEqual(treeEqual(e)),
136            streamEqual(treeEqual(e)),
137            streamEqual(p3Equal(streamEqual(treeEqual(e)), e, streamEqual(treeEqual(e))))).comap(TreeZipper.<A>p_());
138      }
139    
140      /**
141       * A Show instance for tree zippers.
142       *
143       * @param s A Show instance for tree elements.
144       * @return A Show instance for tree zippers.
145       */
146      public static <A> Show<TreeZipper<A>> show(final Show<A> s) {
147        return p4Show(
148            treeShow(s),
149            streamShow(treeShow(s)),
150            streamShow(treeShow(s)),
151            streamShow(p3Show(streamShow(treeShow(s)), s, streamShow(treeShow(s))))).comap(TreeZipper.<A>p_());
152      }
153    
154      private static <A> Stream<Tree<A>> combChildren(final Stream<Tree<A>> ls,
155                                                      final Tree<A> t,
156                                                      final Stream<Tree<A>> rs) {
157        return ls.foldLeft(compose(flip(Stream.<Tree<A>>cons()), P.<Stream<Tree<A>>>p1()), Stream.cons(t, P.p(rs)));
158      }
159    
160      /**
161       * Navigates to the parent of the current location.
162       *
163       * @return A new tree zipper focused on the parent node of the current node,
164       *         or none if the current node is the root node.
165       */
166      public Option<TreeZipper<A>> parent() {
167        if (parents.isEmpty())
168          return none();
169        else {
170          final P3<Stream<Tree<A>>, A, Stream<Tree<A>>> p = parents.head();
171          return some(treeZipper(node(p._2(), combChildren(lefts, tree, rights)), p._1(), p._3(), parents.tail()._1()));
172        }
173      }
174    
175      /**
176       * Navigates to the top-most parent of the current location.
177       *
178       * @return A new tree zipper focused on the top-most parent of the current node.
179       */
180      public TreeZipper<A> root() {
181        return parent().option(this, TreeZipper.<A>root_());
182      }
183    
184      /**
185       * A first-class version of the root function.
186       *
187       * @return A function that returns a new tree-zipper focused on the root of the given tree zipper's tree.
188       */
189      public static <A> F<TreeZipper<A>, TreeZipper<A>> root_() {
190        return new F<TreeZipper<A>, TreeZipper<A>>() {
191          public TreeZipper<A> f(final TreeZipper<A> a) {
192            return a.root();
193          }
194        };
195      }
196    
197      /**
198       * Navigates to the left sibling of the current location.
199       *
200       * @return A new tree zipper focused on the left sibling of the current node,
201       *         or none if there are no siblings on the left.
202       */
203      public Option<TreeZipper<A>> left() {
204        return lefts.isEmpty() ? Option.<TreeZipper<A>>none()
205                               : some(treeZipper(lefts.head(), lefts.tail()._1(), rights.cons(tree), parents));
206      }
207    
208      /**
209       * Navigates to the right sibling of the current location.
210       *
211       * @return A new tree zipper focused on the right sibling of the current node,
212       *         or none if there are no siblings on the right.
213       */
214      public Option<TreeZipper<A>> right() {
215        return rights.isEmpty() ? Option.<TreeZipper<A>>none()
216                                : some(treeZipper(rights.head(), lefts.cons(tree), rights.tail()._1(), parents));
217      }
218    
219      /**
220       * Navigtes to the first child of the current location.
221       *
222       * @return A new tree zipper focused on the first child of the current node, or none if the node has no children.
223       */
224      public Option<TreeZipper<A>> firstChild() {
225        final Stream<Tree<A>> ts = tree.subForest()._1();
226        return ts.isEmpty() ? Option.<TreeZipper<A>>none()
227                            : some(treeZipper(ts.head(), Stream.<Tree<A>>nil(), ts.tail()._1(), downParents()));
228      }
229    
230      /**
231       * Navigtes to the last child of the current location.
232       *
233       * @return A new tree zipper focused on the last child of the current node, or none if the node has no children.
234       */
235      public Option<TreeZipper<A>> lastChild() {
236        final Stream<Tree<A>> ts = tree.subForest()._1().reverse();
237        return ts.isEmpty() ? Option.<TreeZipper<A>>none()
238                            : some(treeZipper(ts.head(), ts.tail()._1(), Stream.<Tree<A>>nil(), downParents()));
239      }
240    
241      /**
242       * Navigates to the given child of the current location, starting at index 0.
243       *
244       * @param n The index of the child to which to navigate.
245       * @return An optional tree zipper focused on the child node at the given index, or none if there is no such child.
246       */
247      public Option<TreeZipper<A>> getChild(final int n) {
248        Option<TreeZipper<A>> r = none();
249        for (final P2<Stream<Tree<A>>, Stream<Tree<A>>> lr
250            : splitChildren(Stream.<Tree<A>>nil(), tree.subForest()._1(), n)) {
251          r = some(treeZipper(lr._1().head(), lr._1().tail()._1(), lr._2(), downParents()));
252        }
253        return r;
254      }
255    
256      /**
257       * Navigates to the first child of the current location, that satisfies the given predicate.
258       *
259       * @param p A predicate to be satisfied by the child node.
260       * @return An optional tree zipper focused on the first child node that satisfies the given predicate,
261       *         or none if there is no such child.
262       */
263      public Option<TreeZipper<A>> findChild(final F<Tree<A>, Boolean> p) {
264        Option<TreeZipper<A>> r = none();
265    
266        final F2<Stream<Tree<A>>, Stream<Tree<A>>, Option<P3<Stream<Tree<A>>, Tree<A>, Stream<Tree<A>>>>> split =
267            new F2<Stream<Tree<A>>, Stream<Tree<A>>, Option<P3<Stream<Tree<A>>, Tree<A>, Stream<Tree<A>>>>>() {
268              public Option<P3<Stream<Tree<A>>, Tree<A>, Stream<Tree<A>>>> f(final Stream<Tree<A>> acc,
269                                                                             final Stream<Tree<A>> xs) {
270                return p.f(xs.head()) ? some(P.p(acc, xs.head(), xs.tail()._1()))
271                                      : xs.isNotEmpty() ? f(acc.cons(xs.head()), xs.tail()._1())
272                                                        : Option.<P3<Stream<Tree<A>>, Tree<A>, Stream<Tree<A>>>>none();
273              }
274            };
275        for (final P3<Stream<Tree<A>>, Tree<A>, Stream<Tree<A>>> ltr
276            : split.f(Stream.<Tree<A>>nil(), tree.subForest()._1())) {
277          r = some(treeZipper(ltr._2(), ltr._1(), ltr._3(), downParents()));
278        }
279        return r;
280      }
281    
282      private Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>> downParents() {
283        return parents.cons(P.p(lefts, tree.root(), rights));
284      }
285    
286      private static <A> Option<P2<Stream<A>, Stream<A>>> splitChildren(final Stream<A> acc,
287                                                                        final Stream<A> xs,
288                                                                        final int n) {
289        return n == 0 ? some(P.p(acc, xs))
290                      : xs.isNotEmpty() ? splitChildren(acc.cons(xs.head()), xs.tail()._1(), n - 1)
291                                        : Option.<P2<Stream<A>, Stream<A>>>none();
292      }
293    
294      private static <A> Stream<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>> lp3nil() {
295        return nil();
296      }
297    
298      /**
299       * Creates a new tree zipper focused on the root of the given tree.
300       *
301       * @param t A tree over which to create a new zipper.
302       * @return a new tree zipper focused on the root of the given tree.
303       */
304      public static <A> TreeZipper<A> fromTree(final Tree<A> t) {
305        return treeZipper(t, Stream.<Tree<A>>nil(), Stream.<Tree<A>>nil(), TreeZipper.<A>lp3nil());
306      }
307    
308      /**
309       * Creates a new tree zipper focused on the first element of the given forest.
310       *
311       * @param ts A forest over which to create a new zipper.
312       * @return a new tree zipper focused on the first element of the given forest.
313       */
314      public static <A> Option<TreeZipper<A>> fromForest(final Stream<Tree<A>> ts) {
315        return ts.isNotEmpty()
316               ? some(treeZipper(ts.head(), Stream.<Tree<A>>nil(), ts.tail()._1(), TreeZipper.<A>lp3nil()))
317               : Option.<TreeZipper<A>>none();
318      }
319    
320      /**
321       * Returns the tree containing this location.
322       *
323       * @return the tree containing this location.
324       */
325      public Tree<A> toTree() {
326        return root().tree;
327      }
328    
329      /**
330       * Returns the forest containing this location.
331       *
332       * @return the forest containing this location.
333       */
334      public Stream<Tree<A>> toForest() {
335        final TreeZipper<A> r = root();
336        return combChildren(r.lefts, r.tree, r.rights);
337      }
338    
339      /**
340       * Returns the tree at the currently focused node.
341       *
342       * @return the tree at the currently focused node.
343       */
344      public Tree<A> focus() {
345        return tree;
346      }
347    
348      /**
349       * Returns the left siblings of the currently focused node.
350       *
351       * @return the left siblings of the currently focused node.
352       */
353      public Stream<Tree<A>> lefts() {
354        return lefts;
355      }
356    
357      /**
358       * Returns the right siblings of the currently focused node.
359       *
360       * @return the right siblings of the currently focused node.
361       */
362      public Stream<Tree<A>> rights() {
363        return rights;
364      }
365    
366      /**
367       * Indicates whether the current node is at the top of the tree.
368       *
369       * @return true if the current node is the root of the tree, otherwise false.
370       */
371      public boolean isRoot() {
372        return parents.isEmpty();
373      }
374    
375      /**
376       * Indicates whether the current node is the leftmost tree in the current forest.
377       *
378       * @return true if the current node has no left siblings, otherwise false.
379       */
380      public boolean isFirst() {
381        return lefts.isEmpty();
382      }
383    
384      /**
385       * Indicates whether the current node is the rightmost tree in the current forest.
386       *
387       * @return true if the current node has no siblings on its right, otherwise false.
388       */
389      public boolean isLast() {
390        return rights.isEmpty();
391      }
392    
393      /**
394       * Indicates whether the current node is at the bottom of the tree.
395       *
396       * @return true if the current node has no child nodes, otherwise false.
397       */
398      public boolean isLeaf() {
399        return tree.subForest()._1().isEmpty();
400      }
401    
402      /**
403       * Indicates whether the current node is a child node of another node.
404       *
405       * @return true if the current node has a parent node, otherwise false.
406       */
407      public boolean isChild() {
408        return !isRoot();
409      }
410    
411      /**
412       * Indicates whether the current node has any child nodes.
413       *
414       * @return true if the current node has child nodes, otherwise false.
415       */
416      public boolean hasChildren() {
417        return !isLeaf();
418      }
419    
420      /**
421       * Replaces the current node with the given tree.
422       *
423       * @param t A tree with which to replace the current node.
424       * @return A new tree zipper in which the focused node is replaced with the given tree.
425       */
426      public TreeZipper<A> setTree(final Tree<A> t) {
427        return treeZipper(t, lefts, rights, parents);
428      }
429    
430      /**
431       * Modifies the current node with the given function.
432       *
433       * @param f A function with which to modify the current tree.
434       * @return A new tree zipper in which the focused node has been transformed by the given function.
435       */
436      public TreeZipper<A> modifyTree(final F<Tree<A>, Tree<A>> f) {
437        return setTree(f.f(tree));
438      }
439    
440      /**
441       * Modifies the label at the current node with the given function.
442       *
443       * @param f A function with which to transform the current node's label.
444       * @return A new tree zipper with the focused node's label transformed by the given function.
445       */
446      public TreeZipper<A> modifyLabel(final F<A, A> f) {
447        return setLabel(f.f(getLabel()));
448      }
449    
450      /**
451       * Replaces the label of the current node with the given value.
452       *
453       * @param v The new value for the node's label.
454       * @return A new tree zipper with the focused node's label replaced by the given value.
455       */
456      public TreeZipper<A> setLabel(final A v) {
457        return modifyTree(new F<Tree<A>, Tree<A>>() {
458          public Tree<A> f(final Tree<A> t) {
459            return Tree.node(v, t.subForest());
460          }
461        });
462      }
463    
464      /**
465       * Returns the label at the current node.
466       *
467       * @return the label at the current node.
468       */
469      public A getLabel() {
470        return tree.root();
471      }
472    
473      /**
474       * Inserts a tree to the left of the current position. The inserted tree becomes the current tree.
475       *
476       * @param t A tree to insert to the left of the current position.
477       * @return A new tree zipper with the given tree in focus and the current tree on the right.
478       */
479      public TreeZipper<A> insertLeft(final Tree<A> t) {
480        return treeZipper(t, lefts, rights.cons(tree), parents);
481      }
482    
483      /**
484       * Inserts a tree to the right of the current position. The inserted tree becomes the current tree.
485       *
486       * @param t A tree to insert to the right of the current position.
487       * @return A new tree zipper with the given tree in focus and the current tree on the left.
488       */
489      public TreeZipper<A> insertRight(final Tree<A> t) {
490        return treeZipper(t, lefts.cons(tree), rights, parents);
491      }
492    
493      /**
494       * Inserts a tree as the first child of the current node. The inserted tree becomes the current tree.
495       *
496       * @param t A tree to insert.
497       * @return A new tree zipper with the given tree in focus, as the first child of the current node.
498       */
499      public TreeZipper<A> insertDownFirst(final Tree<A> t) {
500        return treeZipper(t, Stream.<Tree<A>>nil(), tree.subForest()._1(), downParents());
501      }
502    
503      /**
504       * Inserts a tree as the last child of the current node. The inserted tree becomes the current tree.
505       *
506       * @param t A tree to insert.
507       * @return A new tree zipper with the given tree in focus, as the last child of the current node.
508       */
509      public TreeZipper<A> insertDownLast(final Tree<A> t) {
510        return treeZipper(t, tree.subForest()._1().reverse(), Stream.<Tree<A>>nil(), downParents());
511      }
512    
513      /**
514       * Inserts a tree at the specified location in the current node's stream of children. The inserted tree
515       * becomes the current node.
516       *
517       * @param n The index at which to insert the given tree, starting at 0.
518       * @param t A tree to insert.
519       * @return A new tree zipper with the given tree in focus, at the specified index in the current node's stream
520       *         of children, or None if the current node has fewer than <code>n</code> children.
521       */
522      public Option<TreeZipper<A>> insertDownAt(final int n, final Tree<A> t) {
523        Option<TreeZipper<A>> r = none();
524        for (final P2<Stream<Tree<A>>, Stream<Tree<A>>> lr
525            : splitChildren(Stream.<Tree<A>>nil(), tree.subForest()._1(), n)) {
526          r = some(treeZipper(t, lr._1(), lr._2(), downParents()));
527        }
528        return r;
529      }
530    
531      /**
532       * Removes the current node from the tree. The new position becomes the right sibling, or the left sibling
533       * if the current node has no right siblings, or the parent node if the current node has no siblings.
534       *
535       * @return A new tree zipper with the current node removed.
536       */
537      public Option<TreeZipper<A>> delete() {
538        Option<TreeZipper<A>> r = none();
539        if (rights.isNotEmpty())
540          r = some(treeZipper(rights.head(), rights.tail()._1(), lefts, parents));
541        else if (lefts.isNotEmpty())
542          r = some(treeZipper(lefts.head(), rights, lefts.tail()._1(), parents));
543        else for (final TreeZipper<A> loc : parent())
544            r = some(loc.modifyTree(new F<Tree<A>, Tree<A>>() {
545              public Tree<A> f(final Tree<A> t) {
546                return node(t.root(), Stream.<Tree<A>>nil());
547              }
548            }));
549        return r;
550      }
551    
552      /**
553       * Zips the nodes in this zipper with a boolean that indicates whether that node has focus.
554       * All of the booleans will be false, except for the focused node.
555       *
556       * @return A new zipper of pairs, with each node of this zipper paired with a boolean that is true if that
557       *         node has focus, and false otherwise.
558       */
559      public TreeZipper<P2<A, Boolean>> zipWithFocus() {
560        final F<A, P2<A, Boolean>> f = flip(P.<A, Boolean>p2()).f(false);
561        return map(f).modifyLabel(P2.<A, Boolean, Boolean>map2_(Booleans.not));
562      }
563    
564      /**
565       * Maps the given function across this zipper (covariant functor pattern).
566       *
567       * @param f A function to map across this zipper.
568       * @return A new zipper with the given function applied to the label of every node.
569       */
570      public <B> TreeZipper<B> map(final F<A, B> f) {
571        final F<Tree<A>, Tree<B>> g = Tree.<A, B>fmap_().f(f);
572        final F<Stream<Tree<A>>, Stream<Tree<B>>> h = Stream.<Tree<A>, Tree<B>>map_().f(g);
573        return treeZipper(tree.fmap(f), lefts.map(g), rights.map(g), parents.map(
574            new F<P3<Stream<Tree<A>>, A, Stream<Tree<A>>>, P3<Stream<Tree<B>>, B, Stream<Tree<B>>>>() {
575              public P3<Stream<Tree<B>>, B, Stream<Tree<B>>> f(final P3<Stream<Tree<A>>, A, Stream<Tree<A>>> p) {
576                return p.map1(h).map2(f).map3(h);
577              }
578            }));
579      }
580    
581      /**
582       * First-class conversion of a Tree to the corresponding tree zipper.
583       *
584       * @return A function that takes a tree to its tree zipper representation.
585       */
586      public static <A> F<Tree<A>, TreeZipper<A>> fromTree() {
587        return new F<Tree<A>, TreeZipper<A>>() {
588          public TreeZipper<A> f(final Tree<A> t) {
589            return fromTree(t);
590          }
591        };
592      }
593    
594      /**
595       * A first-class version of the left() function.
596       *
597       * @return A function that focuses the given tree zipper on its left sibling.
598       */
599      public static <A> F<TreeZipper<A>, Option<TreeZipper<A>>> left_() {
600        return new F<TreeZipper<A>, Option<TreeZipper<A>>>() {
601          public Option<TreeZipper<A>> f(final TreeZipper<A> z) {
602            return z.left();
603          }
604        };
605      }
606    
607      /**
608       * A first-class version of the right() function.
609       *
610       * @return A function that focuses the given tree zipper on its right sibling.
611       */
612      public static <A> F<TreeZipper<A>, Option<TreeZipper<A>>> right_() {
613        return new F<TreeZipper<A>, Option<TreeZipper<A>>>() {
614          public Option<TreeZipper<A>> f(final TreeZipper<A> z) {
615            return z.right();
616          }
617        };
618      }
619    
620      /**
621       * Returns a zipper over the tree of all possible permutations of this tree zipper (comonad pattern).
622       * This tree zipper becomes the focused node of the new zipper.
623       *
624       * @return A tree zipper over the tree of all possible permutations of this tree zipper.
625       */
626      public TreeZipper<TreeZipper<A>> positions() {
627        final Tree<TreeZipper<A>> t = unfoldTree(TreeZipper.<A>dwn()).f(this);
628        final Stream<Tree<TreeZipper<A>>> l = uf(TreeZipper.<A>left_());
629        final Stream<Tree<TreeZipper<A>>> r = uf(TreeZipper.<A>right_());
630        final Stream<P3<Stream<Tree<TreeZipper<A>>>, TreeZipper<A>, Stream<Tree<TreeZipper<A>>>>> p = unfold(
631            new F<Option<TreeZipper<A>>,
632                Option<P2<
633                    P3<Stream<Tree<TreeZipper<A>>>, TreeZipper<A>, Stream<Tree<TreeZipper<A>>>>,
634                    Option<TreeZipper<A>>>>>() {
635              public Option<P2<
636                  P3<Stream<Tree<TreeZipper<A>>>, TreeZipper<A>, Stream<Tree<TreeZipper<A>>>>,
637                  Option<TreeZipper<A>>>> f(final Option<TreeZipper<A>> o) {
638                Option<P2<
639                    P3<Stream<Tree<TreeZipper<A>>>, TreeZipper<A>, Stream<Tree<TreeZipper<A>>>>,
640                    Option<TreeZipper<A>>>> r = none();
641                for (final TreeZipper<A> z : o) {
642                  r = some(P.p(P.p(z.uf(TreeZipper.<A>left_()), z, z.uf(TreeZipper.<A>right_())), z.parent()));
643                }
644                return r;
645              }
646            }, parent());
647        return treeZipper(t, l, r, p);
648      }
649    
650      private Stream<Tree<TreeZipper<A>>> uf(final F<TreeZipper<A>, Option<TreeZipper<A>>> f) {
651        return unfold(
652            new F<Option<TreeZipper<A>>, Option<P2<Tree<TreeZipper<A>>, Option<TreeZipper<A>>>>>() {
653              public Option<P2<Tree<TreeZipper<A>>, Option<TreeZipper<A>>>> f(final Option<TreeZipper<A>> o) {
654                Option<P2<Tree<TreeZipper<A>>, Option<TreeZipper<A>>>> r = none();
655                for (final TreeZipper<A> c : o) {
656                  r = some(P.p(unfoldTree(TreeZipper.<A>dwn()).f(c), f.f(c)));
657                }
658                return r;
659              }
660            }, f.f(this));
661      }
662    
663      private static <A> F<TreeZipper<A>, P2<TreeZipper<A>, P1<Stream<TreeZipper<A>>>>> dwn() {
664        return new F<TreeZipper<A>, P2<TreeZipper<A>, P1<Stream<TreeZipper<A>>>>>() {
665          public P2<TreeZipper<A>, P1<Stream<TreeZipper<A>>>> f(final TreeZipper<A> tz) {
666            return P.<TreeZipper<A>, P1<Stream<TreeZipper<A>>>>p(tz, new P1<Stream<TreeZipper<A>>>() {
667              private F<Option<TreeZipper<A>>, Option<P2<TreeZipper<A>, Option<TreeZipper<A>>>>> fwd() {
668                return new F<Option<TreeZipper<A>>, Option<P2<TreeZipper<A>, Option<TreeZipper<A>>>>>() {
669                  public Option<P2<TreeZipper<A>, Option<TreeZipper<A>>>> f(final Option<TreeZipper<A>> o) {
670                    Option<P2<TreeZipper<A>, Option<TreeZipper<A>>>> r = none();
671                    for (final TreeZipper<A> c : o) {
672                      r = some(P.p(c, c.right()));
673                    }
674                    return r;
675                  }
676                };
677              }
678    
679              public Stream<TreeZipper<A>> _1() {
680                return unfold(fwd(), tz.firstChild());
681              }
682            });
683          }
684        };
685      }
686    
687      /**
688       * Maps the given function over the tree of all positions for this zipper (comonad pattern). Returns a zipper
689       * over the tree of results of the function application.
690       *
691       * @param f A function to map over the tree of all positions for this zipper.
692       * @return A zipper over the tree of results of the function application.
693       */
694      public <B> TreeZipper<B> cobind(final F<TreeZipper<A>, B> f) {
695        return positions().map(f);
696      }
697    
698      /**
699       * A first-class version of the findChild function.
700       *
701       * @return a function that finds the first child, of a given tree zipper, that matches a given predicate.
702       */
703      public static <A> F2<F<Tree<A>, Boolean>, TreeZipper<A>, Option<TreeZipper<A>>> findChild() {
704        return new F2<F<Tree<A>, Boolean>, TreeZipper<A>, Option<TreeZipper<A>>>() {
705          public Option<TreeZipper<A>> f(final F<Tree<A>, Boolean> f, final TreeZipper<A> az) {
706            return az.findChild(f);
707          }
708        };
709      }
710    
711      /**
712       * Zips this TreeZipper with another, applying the given function lock-step over both zippers in all directions.
713       * The structure of the resulting TreeZipper is the structural intersection of the two TreeZippers.
714       *
715       * @param bs A TreeZipper to zip this one with.
716       * @param f  A function with which to zip together the two TreeZippers.
717       * @return The result of applying the given function over this TreeZipper and the given TreeZipper, location-wise.
718       */
719      public <B, C> TreeZipper<C> zipWith(final TreeZipper<B> bs, final F2<A, B, C> f) {
720        return $$(f).zipTreeZipper().f(this, bs);
721      }
722    
723      /**
724       * Zips this TreeZipper with another, applying the given function lock-step over both zippers in all directions.
725       * The structure of the resulting TreeZipper is the structural intersection of the two TreeZippers.
726       *
727       * @param bs A TreeZipper to zip this one with.
728       * @param f  A function with which to zip together the two TreeZippers.
729       * @return The result of applying the given function over this TreeZipper and the given TreeZipper, location-wise.
730       */
731      public <B, C> TreeZipper<C> zipWith(final TreeZipper<B> bs, final F<A, F<B, C>> f) {
732        return zipWith(bs, uncurryF2(f));
733      }
734    }