# Scalaz（24）－ 泛函数据结构： Tree-数据游览及维护

上节我们讨论了Zipper－串形不可变集合（immutable sequencial collection）游标，在串形集合中左右游走及元素维护操作。这篇我们谈谈Tree。在电子商务应用中对于xml,json等格式文件的处理要求非常之普遍，scalaz提供了Tree数据类型及相关的游览及操作函数能更方便高效的处理xml,json文件及系统目录这些树形结构数据的相关编程。scalaz Tree的定义非常简单：scalaz/Tree.scala

`* A multi-way tree, also known as a rose tree. Also known as Cofree[Stream, A].*/sealed abstract class Tree[A] {import Tree._/** The label at the root of this tree. */def rootLabel: A/** The child nodes of this tree. */def subForest: Stream[Tree[A]]...`

Tree是由一个A值rootLabel及一个流中子树Stream[Tree[A]]组成。Tree可以只由一个A类型值rootLabel组成，这时流中子树subForest就是空的Stream.empty。只有rootLabel的Tree俗称叶（leaf），有subForest的称为节（node）。scalaz为任何类型提供了leaf和node的构建注入方法：syntax/TreeOps.scala

`final class TreeOps[A](self: A) {def node(subForest: Tree[A]*): Tree[A] = Tree.node(self, subForest.toStream)def leaf: Tree[A] = Tree.leaf(self)}trait ToTreeOps {implicit def ToTreeOps[A](a: A) = new TreeOps(a)}`

`trait TreeFunctions {/** Construct a new Tree node. */def node[A](root: => A, forest: => Stream[Tree[A]]): Tree[A] = new Tree[A] {lazy val rootLabel = rootlazy val subForest = forestoverride def toString = "<tree>"}/** Construct a tree node with no children. */def leaf[A](root: => A): Tree[A] = node(root, Stream.empty)`

Tree提供了构建和模式拆分函数：

`object Tree extends TreeInstances with TreeFunctions {/** Construct a tree node with no children. */def apply[A](root: => A): Tree[A] = leaf(root)object Node {def unapply[A](t: Tree[A]): Option[(A, Stream[Tree[A]])] = Some((t.rootLabel, t.subForest))}}`

` 1 Tree("ALeaf") === "ALeaf".leaf //> res5: Boolean = true 2 val tree: Tree[Int] = 3 1.node( 4 11.leaf, 5 12.node( 6 121.leaf), 7 2.node( 8 21.leaf, 9 22.leaf)10 ) //> tree : scalaz.Tree[Int] = <tree>11 tree.drawTree //> res6: String = "112 //| |13 //| +- 1114 //| |15 //| +- 1216 //| | |17 //| | `- 12118 //| |19 //| `- 220 //| |21 //| +- 2122 //| |23 //| `- 2224 //| "`

Tree实现了下面众多的接口函数：

`sealed abstract class TreeInstances {implicit val treeInstance: Traverse1[Tree] with Monad[Tree] with Comonad[Tree] with Align[Tree] with Zip[Tree] = new Traverse1[Tree] with Monad[Tree] with Comonad[Tree] with Align[Tree] with Zip[Tree] {def point[A](a: => A): Tree[A] = Tree.leaf(a)def cobind[A, B](fa: Tree[A])(f: Tree[A] => B): Tree[B] = fa cobind fdef copoint[A](p: Tree[A]): A = p.rootLabeloverride def map[A, B](fa: Tree[A])(f: A => B) = fa map fdef bind[A, B](fa: Tree[A])(f: A => Tree[B]): Tree[B] = fa flatMap fdef traverse1Impl[G[_]: Apply, A, B](fa: Tree[A])(f: A => G[B]): G[Tree[B]] = fa traverse1 foverride def foldRight[A, B](fa: Tree[A], z: => B)(f: (A, => B) => B): B = fa.foldRight(z)(f)override def foldMapRight1[A, B](fa: Tree[A])(z: A => B)(f: (A, => B) => B) = (fa.flatten.reverse: @unchecked) match {case h #:: t => t.foldLeft(z(h))((b, a) => f(a, b))}override def foldLeft[A, B](fa: Tree[A], z: B)(f: (B, A) => B): B =fa.flatten.foldLeft(z)(f)override def foldMapLeft1[A, B](fa: Tree[A])(z: A => B)(f: (B, A) => B): B = fa.flatten match {case h #:: t => t.foldLeft(z(h))(f)}override def foldMap[A, B](fa: Tree[A])(f: A => B)(implicit F: Monoid[B]): B = fa foldMap fdef alignWith[A, B, C](f: (\&/[A, B]) ⇒ C) = {def align(ta: Tree[A], tb: Tree[B]): Tree[C] =Tree.node(f(\&/(ta.rootLabel, tb.rootLabel)), Align[Stream].alignWith[Tree[A], Tree[B], Tree[C]]({case \&/.This(sta) ⇒ sta map {a ⇒ f(\&/.This(a))}case \&/.That(stb) ⇒ stb map {b ⇒ f(\&/.That(b))}case \&/.Both(sta, stb) ⇒ align(sta, stb)})(ta.subForest, tb.subForest))align _}def zip[A, B](aa: => Tree[A], bb: => Tree[B]) = {val a = aaval b = bbTree.node((a.rootLabel, b.rootLabel),Zip[Stream].zipWith(a.subForest, b.subForest)(zip(_, _)))}}implicit def treeEqual[A](implicit A0: Equal[A]): Equal[Tree[A]] =new TreeEqual[A] { def A = A0 }implicit def treeOrder[A](implicit A0: Order[A]): Order[Tree[A]] =new Order[Tree[A]] with TreeEqual[A] {def A = A0import std.stream._override def order(x: Tree[A], y: Tree[A]) =A.order(x.rootLabel, y.rootLabel) match {case Ordering.EQ =>Order[Stream[Tree[A]]].order(x.subForest, y.subForest)case x => x}}`

` 1 // 是 Functor... 2 (tree map { v: Int => v + 1 }) === 3 2.node( 4 12.leaf, 5 13.node( 6 122.leaf), 7 3.node( 8 22.leaf, 9 23.leaf)10 ) //> res7: Boolean = true1112 // ...是 Monad13 1.point[Tree] === 1.leaf //> res8: Boolean = true14 val t2 = tree >>= (x => (x == 2) ? x.leaf | x.node((-x).leaf))15 //> t2 : scalaz.Tree[Int] = <tree>16 t2 === 1.node((-1).leaf, 2.leaf, 3.node((-3).leaf, 4.node((-4).leaf)))17 //> res9: Boolean = false18 t2.drawTree //> res10: String = "119 //| |20 //| +- -121 //| |22 //| +- 1123 //| | |24 //| | `- -1125 //| |26 //| +- 1227 //| | |28 //| | +- -1229 //| | |30 //| | `- 12131 //| | |32 //| | `- -12133 //| |34 //| `- 235 //| |36 //| +- 2137 //| | |38 //| | `- -2139 //| |40 //| `- 2241 //| |42 //| `- -2243 //| "44 // ...是 Foldable45 tree.foldMap(_.toString) === "1111212122122" //> res11: Boolean = true`

` def pathTree[E](root: E, paths: Seq[Seq[E]]): Tree[E] = {root.node(paths groupBy (_.head) map {case (parent, subpaths) =>pathTree(parent, subpaths collect {case pp +: rest if rest.nonEmpty => rest})} toSeq: _*)}`

` 1 val paths = List(List("A","a1","a2"),List("B","b1")) 2 //> paths : List[List[String]] = List(List(A, a1, a2), List(B, b1)) 3 pathTree("root",paths) drawTree //> res0: String = ""root" 4 //| | 5 //| +- "A" 6 //| | | 7 //| | `- "a1" 8 //| | | 9 //| | `- "a2"10 //| |11 //| `- "B"12 //| |13 //| `- "b1"14 //| "15 val paths = List(List("A","a1","a2"),List("B","b1"),List("B","b2","b3"))16 //> paths : List[List[String]] = List(List(A, a1, a2), List(B, b1), List(B, b2,17 //| b3))18 pathTree("root",paths) drawTree //> res0: String = ""root"19 //| |20 //| +- "A"21 //| | |22 //| | `- "a1"23 //| | |24 //| | `- "a2"25 //| |26 //| `- "B"27 //| |28 //| +- "b2"29 //| | |30 //| | `- "b3"31 //| |32 //| `- "b1"33 //| "`

`1 val paths = List(List("A")) //> paths : List[List[String]] = List(List(A))2 val gpPaths =paths.groupBy(_.head) //> gpPaths : scala.collection.immutable.Map[String,List[List[String]]] = Map(A-> List(List(A)))3 List(List("A")) collect { case pp +: rest if rest.nonEmpty => rest }4 //> res0: List[List[String]] = List()`

`1 "root".node(2 "A".node(List().toSeq: _*)3 ) drawTree //> res3: String = ""root"4 //| |5 //| `- "A"6 //| "`

`1 "root".node(2 "A".node(List().toSeq: _*),3 "B".node(List().toSeq: _*)4 ) drawTree //> res4: String = ""root"5 //| |6 //| +- "A"7 //| |8 //| `- "B"9 //| "`

` 1 val paths = List(List("A","a1")) //> paths : List[List[String]] = List(List(A, a1)) 2 val gpPaths =paths.groupBy(_.head) //> gpPaths : scala.collection.immutable.Map[String,List[List[String]]] = Map(A 3 //| -> List(List(A, a1))) 4 List(List("A","a1")) collect { case pp +: rest if rest.nonEmpty => rest } 5 //> res0: List[List[String]] = List(List(a1)) 6 7 //化解成 8 "root".node( 9 "A".node(10 "a1".node(11 List().toSeq: _*)12  )13 ) drawTree //> res3: String = ""root"14 //| |15 //| `- "A"16 //| |17 //| `- "a1"18 //| "`

合并目录：

` 1 val paths = List(List("A","a1"),List("A","a2")) //> paths : List[List[String]] = List(List(A, a1), List(A, a2)) 2 val gpPaths =paths.groupBy(_.head) //> gpPaths : scala.collection.immutable.Map[String,List[List[String]]] = Map(A 3 //| -> List(List(A, a1), List(A, a2))) 4 List(List("A","a1"),List("A","a2")) collect { case pp +: rest if rest.nonEmpty => rest } 5 //> res0: List[List[String]] = List(List(a1), List(a2)) 6 7 //相当产生结果 8 "root".node( 9 "A".node(10 "a1".node(11 List().toSeq: _*)12  ,13 "a2".node(14 List().toSeq: _*)15  )16 ) drawTree //> res3: String = ""root"17 //| |18 //| `- "A"19 //| |20 //| +- "a1"21 //| |22 //| `- "a2"23 //| "`

`final case class TreeLoc[A](tree: Tree[A], lefts: TreeForest[A],rights: TreeForest[A], parents: Parents[A]) {...trait TreeLocFunctions {type TreeForest[A] =Stream[Tree[A]]type Parent[A] =(TreeForest[A], A, TreeForest[A])type Parents[A] =Stream[Parent[A]]`

` 1 /** A TreeLoc zipper of this tree, focused on the root node. */ 2 def loc: TreeLoc[A] = TreeLoc.loc(this, Stream.Empty, Stream.Empty, Stream.Empty) 3 4 val tree: Tree[Int] = 5 1.node( 6 11.leaf, 7 12.node( 8 121.leaf), 9 2.node(10 21.leaf,11 22.leaf)12 ) //> tree : scalaz.Tree[Int] = <tree>1314 tree.loc //> res7: scalaz.TreeLoc[Int] = TreeLoc(<tree>,Stream(),Stream(),Stream())`

TreeLoc的游动函数：

` def root: TreeLoc[A] =parent match {case Some(z) => z.rootcase None => this}/** Select the left sibling of the current node. */def left: Option[TreeLoc[A]] = lefts match {case t #:: ts => Some(loc(t, ts, tree #:: rights, parents))case Stream.Empty => None}/** Select the right sibling of the current node. */def right: Option[TreeLoc[A]] = rights match {case t #:: ts => Some(loc(t, tree #:: lefts, ts, parents))case Stream.Empty => None}/** Select the leftmost child of the current node. */def firstChild: Option[TreeLoc[A]] = tree.subForest match {case t #:: ts => Some(loc(t, Stream.Empty, ts, downParents))case Stream.Empty => None}/** Select the rightmost child of the current node. */def lastChild: Option[TreeLoc[A]] = tree.subForest.reverse match {case t #:: ts => Some(loc(t, ts, Stream.Empty, downParents))case Stream.Empty => None}/** Select the nth child of the current node. */def getChild(n: Int): Option[TreeLoc[A]] =for {lr <- splitChildren(Stream.Empty, tree.subForest, n)ls = lr._1} yield loc(ls.head, ls.tail, lr._2, downParents)`

` 1 val tree: Tree[Int] = 2 1.node( 3 11.leaf, 4 12.node( 5 121.leaf), 6 2.node( 7 21.leaf, 8 22.leaf) 9 ) //> tree : scalaz.Tree[Int] = <tree>10 tree.loc //> res7: scalaz.TreeLoc[Int] = TreeLoc(<tree>,Stream(),Stream(),Stream())11 val l = for {12 l1 <- tree.loc.some13 l2 <- l1.firstChild14 l3 <- l1.lastChild15 l4 <- l3.firstChild16 } yield (l1,l2,l3,l4) //> l : Option[(scalaz.TreeLoc[Int], scalaz.TreeLoc[Int], scalaz.TreeLoc[Int],17 //| scalaz.TreeLoc[Int])] = Some((TreeLoc(<tree>,Stream(),Stream(),Stream()),T18 //| reeLoc(<tree>,Stream(),Stream(<tree>, <tree>),Stream((Stream(),1,Stream()),19 //| ?)),TreeLoc(<tree>,Stream(<tree>, <tree>),Stream(),Stream((Stream(),1,Stre20 //| am()), ?)),TreeLoc(<tree>,Stream(),Stream(<tree>, ?),Stream((Stream(<tree>,21 //| <tree>),2,Stream()), ?))))2223 l.get._1.getLabel //> res8: Int = 124 l.get._2.getLabel //> res9: Int = 1125 l.get._3.getLabel //> res10: Int = 226 l.get._4.getLabel //> res11: Int = 21`

` /** Select the nth child of the current node. */def getChild(n: Int): Option[TreeLoc[A]] =for {lr <- splitChildren(Stream.Empty, tree.subForest, n)ls = lr._1} yield loc(ls.head, ls.tail, lr._2, downParents)/** Select the first immediate child of the current node that satisfies the given predicate. */def findChild(p: Tree[A] => Boolean): Option[TreeLoc[A]] = {@tailrecdef split(acc: TreeForest[A], xs: TreeForest[A]): Option[(TreeForest[A], Tree[A], TreeForest[A])] =(acc, xs) match {case (acc, Stream.cons(x, xs)) => if (p(x)) Some((acc, x, xs)) else split(Stream.cons(x, acc), xs)case _ => None}for (ltr <- split(Stream.Empty, tree.subForest)) yield loc(ltr._2, ltr._1, ltr._3, downParents)}/**Select the first descendant node of the current node that satisfies the given predicate. */def find(p: TreeLoc[A] => Boolean): Option[TreeLoc[A]] =Cobind[TreeLoc].cojoin(this).tree.flatten.find(p)`

find用法示范：

` 1 val tree: Tree[Int] = 2 1.node( 3 11.leaf, 4 12.node( 5 121.leaf), 6 2.node( 7 21.leaf, 8 22.leaf) 9 ) //> tree : scalaz.Tree[Int] = <tree>10 tree.loc //> res7: scalaz.TreeLoc[Int] = TreeLoc(<tree>,Stream(),Stream(),Stream())11 val l = for {12 l1 <- tree.loc.some13 l2 <- l1.find{_.getLabel == 2}14 l3 <- l1.find{_.getLabel == 121}15 l4 <- l2.find{_.getLabel == 22}16 l5 <- l1.findChild{_.rootLabel == 12}17 l6 <- l1.findChild{_.rootLabel == 2}18 } yield l6 //> l : Option[scalaz.TreeLoc[Int]] = Some(TreeLoc(<tree>,Stream(<tree>, ?),St19 //| ream(),Stream((Stream(),1,Stream()), ?)))`

` /** Replace the current node with the given one. */def setTree(t: Tree[A]): TreeLoc[A] = loc(t, lefts, rights, parents)/** Modify the current node with the given function. */def modifyTree(f: Tree[A] => Tree[A]): TreeLoc[A] = setTree(f(tree))/** Modify the label at the current node with the given function. */def modifyLabel(f: A => A): TreeLoc[A] = setLabel(f(getLabel))/** Get the label of the current node. */def getLabel: A = tree.rootLabel/** Set the label of the current node. */def setLabel(a: A): TreeLoc[A] = modifyTree((t: Tree[A]) => node(a, t.subForest))/** Insert the given node to the left of the current node and give it focus. */def insertLeft(t: Tree[A]): TreeLoc[A] = loc(t, lefts, Stream.cons(tree, rights), parents)/** Insert the given node to the right of the current node and give it focus. */def insertRight(t: Tree[A]): TreeLoc[A] = loc(t, Stream.cons(tree, lefts), rights, parents)/** Insert the given node as the first child of the current node and give it focus. */def insertDownFirst(t: Tree[A]): TreeLoc[A] = loc(t, Stream.Empty, tree.subForest, downParents)/** Insert the given node as the last child of the current node and give it focus. */def insertDownLast(t: Tree[A]): TreeLoc[A] = loc(t, tree.subForest.reverse, Stream.Empty, downParents)/** Insert the given node as the nth child of the current node and give it focus. */def insertDownAt(n: Int, t: Tree[A]): Option[TreeLoc[A]] =for (lr <- splitChildren(Stream.Empty, tree.subForest, n)) yield loc(t, lr._1, lr._2, downParents)/** Delete the current node and all its children. */def delete: Option[TreeLoc[A]] = rights match {case Stream.cons(t, ts) => Some(loc(t, lefts, ts, parents))case _ => lefts match {case Stream.cons(t, ts) => Some(loc(t, ts, rights, parents))case _ => for (loc1 <- parent) yield loc1.modifyTree((t: Tree[A]) => node(t.rootLabel, Stream.Empty))}}`

` 1 val tr = 1.leaf //> tr : scalaz.Tree[Int] = <tree> 2 val tl = for { 3 l1 <- tr.loc.some 4 l3 <- l1.insertDownLast(12.leaf).some 5 l4 <- l3.insertDownLast(121.leaf).some 6 l5 <- l4.root.some 7 l2 <- l5.insertDownFirst(11.leaf).some 8 l6 <- l2.root.some 9 l7 <- l6.find{_.getLabel == 12}10 l8 <- l7.setLabel(102).some11 } yield l8 //> tl : Option[scalaz.TreeLoc[Int]] = Some(TreeLoc(<tree>,Stream(<tree>, ?),S12 //| tream(),Stream((Stream(),1,Stream()), ?)))1314 tl.get.toTree.drawTree //> res8: String = "115 //| |16 //| +- 1117 //| |18 //| `- 10219 //| |20 //| `- 12121 //| "22  `

setTree和delete会替换当前节点下的所有子树：

` 1 val tree: Tree[Int] = 2 1.node( 3 11.leaf, 4 12.node( 5 121.leaf), 6 2.node( 7 21.leaf, 8 22.leaf) 9 ) //> tree : scalaz.Tree[Int] = <tree>10 def modTree(t: Tree[Int]): Tree[Int] = {11 val l = for {12 l1 <- t.loc.some13 l2 <- l1.find{_.getLabel == 22}14 l3 <- l2.setTree { 3.node (31.leaf) }.some15 } yield l316 l.get.toTree17 } //> modTree: (t: scalaz.Tree[Int])scalaz.Tree[Int]18 val l = for {19 l1 <- tree.loc.some20 l2 <- l1.find{_.getLabel == 2}21 l3 <- l2.modifyTree{modTree(_)}.some22 l4 <- l3.root.some23 l5 <- l4.find{_.getLabel == 12}24 l6 <- l5.delete25 } yield l6 //> l : Option[scalaz.TreeLoc[Int]] = Some(TreeLoc(<tree>,Stream(<tree>, ?),St26 //| ream(),Stream((Stream(),1,Stream()), ?)))27 l.get.toTree.drawTree //> res7: String = "128 //| |29 //| +- 1130 //| |31 //| `- 232 //| |33 //| +- 2134 //| |35 //| `- 336 //| |37 //| `- 3138 //| "`

Top