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 }