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

```* 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 = root
lazy val subForest = forest

override 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 = "1
12                                                   //| |
13                                                   //| +- 11
14                                                   //| |
15                                                   //| +- 12
16                                                   //| |  |
17                                                   //| |  `- 121
18                                                   //| |
19                                                   //| `- 2
20                                                   //|    |
21                                                   //|    +- 21
22                                                   //|    |
23                                                   //|    `- 22
24                                                   //| "```

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 f
def copoint[A](p: Tree[A]): A = p.rootLabel
override def map[A, B](fa: Tree[A])(f: A => B) = fa map f
def bind[A, B](fa: Tree[A])(f: A => Tree[B]): Tree[B] = fa flatMap f
def traverse1Impl[G[_]: Apply, A, B](fa: Tree[A])(f: A => G[B]): G[Tree[B]] = fa traverse1 f
override 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 f
def 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 = aa
val b = bb
Tree.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 = A0
import 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 = true
11
13     1.point[Tree] === 1.leaf                      //> res8: Boolean = true
14     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 = false
18     t2.drawTree                                   //> res10: String = "1
19                                                   //| |
20                                                   //| +- -1
21                                                   //| |
22                                                   //| +- 11
23                                                   //| |  |
24                                                   //| |  `- -11
25                                                   //| |
26                                                   //| +- 12
27                                                   //| |  |
28                                                   //| |  +- -12
29                                                   //| |  |
30                                                   //| |  `- 121
31                                                   //| |     |
32                                                   //| |     `- -121
33                                                   //| |
34                                                   //| `- 2
35                                                   //|    |
36                                                   //|    +- 21
37                                                   //|    |  |
38                                                   //|    |  `- -21
39                                                   //|    |
40                                                   //|    `- 22
41                                                   //|       |
42                                                   //|       `- -22
43                                                   //| "
44  // ...是 Foldable
45     tree.foldMap(_.toString) === "1111212122122"  //> res11: Boolean = true```

```  def pathTree[E](root: E, paths: Seq[Seq[E]]): Tree[E] = {
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>
13
14   tree.loc                      //> res7: scalaz.TreeLoc[Int] = TreeLoc(<tree>,Stream(),Stream(),Stream())```

TreeLoc的游动函数：

```  def root: TreeLoc[A] =
parent match {
case Some(z) => z.root
case 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.some
13    l2 <- l1.firstChild
14    l3 <- l1.lastChild
15    l4 <- l3.firstChild
16    } 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()),T
18                                                   //| reeLoc(<tree>,Stream(),Stream(<tree>, <tree>),Stream((Stream(),1,Stream()),
19                                                   //|  ?)),TreeLoc(<tree>,Stream(<tree>, <tree>),Stream(),Stream((Stream(),1,Stre
20                                                   //| am()), ?)),TreeLoc(<tree>,Stream(),Stream(<tree>, ?),Stream((Stream(<tree>,
21                                                   //|  <tree>),2,Stream()), ?))))
22
23   l.get._1.getLabel                               //> res8: Int = 1
24   l.get._2.getLabel                               //> res9: Int = 11
25   l.get._3.getLabel                               //> res10: Int = 2
26   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]] = {
@tailrec
def 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.some
13    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>, ?),St
19                                                   //| 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).some
11   } yield l8                                      //> tl  : Option[scalaz.TreeLoc[Int]] = Some(TreeLoc(<tree>,Stream(<tree>, ?),S
12                                                   //| tream(),Stream((Stream(),1,Stream()), ?)))
13
14   tl.get.toTree.drawTree                          //> res8: String = "1
15                                                   //| |
16                                                   //| +- 11
17                                                   //| |
18                                                   //| `- 102
19                                                   //|    |
20                                                   //|    `- 121
21                                                   //| "
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.some
13         l2 <- l1.find{_.getLabel == 22}
14         l3 <- l2.setTree { 3.node (31.leaf) }.some
15       } yield l3
16       l.get.toTree
17    }                                              //> modTree: (t: scalaz.Tree[Int])scalaz.Tree[Int]
18    val l = for {
19    l1 <- tree.loc.some
20    l2 <- l1.find{_.getLabel == 2}
21    l3 <- l2.modifyTree{modTree(_)}.some
22    l4 <- l3.root.some
23    l5 <- l4.find{_.getLabel == 12}
24    l6 <- l5.delete
25   } yield l6                                      //> l  : Option[scalaz.TreeLoc[Int]] = Some(TreeLoc(<tree>,Stream(<tree>, ?),St
26                                                   //| ream(),Stream((Stream(),1,Stream()), ?)))
27   l.get.toTree.drawTree                           //> res7: String = "1
28                                                   //| |
29                                                   //| +- 11
30                                                   //| |
31                                                   //| `- 2
32                                                   //|    |
33                                                   //|    +- 21
34                                                   //|    |
35                                                   //|    `- 3
36                                                   //|       |
37                                                   //|       `- 31
38                                                   //| "```

0 条评论

## 相关文章

### ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3749

### 高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分，其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

1K4

902

### c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候，禁用定时器，你...

3071

5166

### 简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349

### Failed to set permissions of path

12/09/04 16:46:34 INFO support.ClassPathXmlApplicationContext: Refreshing org...

2757

### java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods\$ jmod list java....

1182

### Effective Testing with RSpec 3 （英文版）(序言)

Early praise for Effective Testing with RSpec 3

1864

### Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1876