泛函数据结构

 
上节大家谈谈了Zipper-串形不可变集合(immutable sequential
collection)游标,在串形集合中左右游走及要素维护操作。那篇我们谈论Tree。在电子商务应用中对此xml,json等格式文件的拍卖供给11分之广泛,scalaz提供了Tree数据类型及有关的观光及操作函数能更有利于高效的拍卖xml,json文件及系统目录那几个树形结构数据的连锁编制程序。scalaz
Tree的概念相当简单:scalaz/Tree.scala

上节咱们谈谈了Zipper-串形不可变集合(immutable sequential
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]]
...
* 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可以只由3个A类型值rootLabel组成,那时代前卫中子树subForest正是空的Stream.empty。只有rootLabel的Tree俗称叶(leaf),有subForest的称为节(node)。scalaz为其余类型提供了leaf和node的塑造注入方法:syntax/TreeOps.scala

Tree是由八个A值rootLabel及三个流中子树Stream[Tree[A]]结合。Tree可以只由1个A类型值rootLabel组成,那时代洋气中子树subForest便是空的Stream.empty。只有rootLabel的Tree俗称叶,有subForest的称为节。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)
}
final class TreeOps[A] {  def node(subForest: Tree[A]*): Tree[A] = Tree.node(self, subForest.toStream)  def leaf: Tree[A] = Tree.leaf}trait ToTreeOps {  implicit def ToTreeOps[A] = new TreeOps}

实在注入方法调用了Tree里的创设函数:

实际上注入方法调用了Tree里的营造函数:

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)
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提供了创设和格局拆分函数:

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

咱俩能够直接构建Tree:

我们能够间接构建Tree:

 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                                                   //| "
 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完结了下边众多的接口函数:

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
        }
    }
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    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    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 => f    }    override def foldLeft[A, B](fa: Tree[A], z: B) => B): B =      fa.flatten.foldLeft    override def foldMapLeft1[A, B](fa: Tree[A])(z: A => B) => B): B = fa.flatten match {      case h #:: t => t.foldLeft    }    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 map {a ⇒ f(\&/.This}          case \&/.That ⇒ stb map {b ⇒ f(\&/.That}          case \&/.Both ⇒ align        })(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))      )    }  }  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        }    }

那么Tree正是个Monad,也是Functor,Applicative,依旧traversable,foldable。Tree也促成了Order,Equal实例,能够进行值的依次相比。我们就用些例子来证实呢: 

那正是说Tree正是个Monad,也是Functor,Applicative,依旧traversable,foldable。Tree也落到实处了Order,Equal实例,能够张开值的逐条比较。我们就用些例子来注明呢:

 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 
12  // ...是 Monad
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
 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 = true11 12  // ...是 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

聊到创设Tree,偶然在网上发现了那般三个Tree营造函数:

谈到创设Tree,偶然在网上发现了如此三个Tree塑造函数:

  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: _*)
  }
  def pathTree[E](root: E, paths: Seq[Seq[E]]): Tree[E] = {    root.node(paths groupBy  map {      case (parent, subpaths) =>        pathTree(parent, subpaths collect {          case pp +: rest if rest.nonEmpty => rest        })    } toSeq: _*)  }

据称那几个pathTree函数能把List里的目录结构转化成Tree。先看看到底是或不是享有那样效果:

据称那一个pathTree函数能把List里的目录结构转化成Tree。先看看到底是或不是独具那样功能:

 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","a1","a2"),List("B","b1")) 2                                                   //> paths  : List[List[String]] = List(List(A, a1, a2), List 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, 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                                                   //| "

果不其然能行,而且还是能把”B”节点合并汇聚。那些函数的我俨然正是个神人,起码是个算法和FP语法运用大师。作者即使还不可能到达大师的品位能写出这么的泛函程序,但好奇心是挡不住的,总想精晓那个函数是怎么运维的。能够用壹些测试数据来日趋追踪一下: 

果不其然能行,而且还是能把”B”节点合并汇聚。那么些函数的撰稿人大概正是个神人,起码是个算法和FP语法运用大师。我即便还不恐怕落成大师的程度能写出这么的泛函程序,但好奇心是挡不住的,总想明白那几个函数是怎么运作的。能够用一些测试数据来逐步追踪一下:

 

1   val paths = List(List("A"))           //> paths  : List[List[String]] = List2   val gpPaths =paths.groupBy    //> gpPaths  : scala.collection.immutable.Map[String,List[List[String]]] = Map(A-> List3   List(List("A")) collect { case pp +: rest if rest.nonEmpty => rest }4                                                   //> res0: List[List[String]] = List()
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()

通过上边的追踪约化我们看看List在pathTree里的实行进度。那里把复杂的groupBy和collect函数的用法和结果精晓了。实际上任何经过也便是:

 

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

因而地点的追踪约化我们见到List(List(A))在pathTree里的实践进度。这里把纷纭的groupBy和collect函数的用法和结果掌握了。实际上任何进度相当于:

设若再追加贰个点就一定于:

 

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

增多一层:

 

 1   val paths = List(List("A","a1"))                //> paths  : List[List[String]] = List(List 2   val gpPaths =paths.groupBy              //> gpPaths  : scala.collection.immutable.Map[String,List[List[String]]] = Map(A 3                                                   //|  -> List(List 4   List(List("A","a1")) collect { case pp +: rest if rest.nonEmpty => rest } 5                                                   //> res0: List[List[String]] = List 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  "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"),List("A","a2")) //> paths  : List[List[String]] = List(List, List 2   val gpPaths =paths.groupBy              //> gpPaths  : scala.collection.immutable.Map[String,List[List[String]]] = Map(A 3                                                   //|  -> List(List, List 4   List(List("A","a1"),List("A","a2")) collect { case pp +: rest if rest.nonEmpty => rest } 5                                                   //> res0: List[List[String]] = List, List 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                                                   //| "

扩张1层: 

深信这么些追踪进度丰盛领会全部函数的劳作规律了。
有了Tree创设格局后就供给Tree的游动和操作函数了。与串形集合的直线游动区别的是,树形集合游动情势是分岔的。所以Zipper不太适用于树形结构。scalaz尤其提供了树形集合的固化游标TreeLoc,大家看看它的概念:scalaz/TreeLoc.scala

 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                                                   //| "
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]]

 合并目录:

树形集合游标TreeLoc由近日节点tree、左子树lefts、右子树rights及父树parents组成。lefts,rights,parents都以在流中的树形Stream[Tree[A]]。
用Tree.loc能够间接对指标树生成TreeLoc:

 

 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
 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                                                   //| "

TreeLoc的游动函数:

 

  def root: TreeLoc[A] =    parent match {      case Some => 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: Option[TreeLoc[A]] =    for {lr <- splitChildren(Stream.Empty, tree.subForest, n)         ls = lr._1    } yield loc(ls.head, ls.tail, lr._2, downParents)

深信不疑这么些追踪进度丰硕领会全体函数的办事原理了。
有了Tree营造格局后就必要Tree的游动和操作函数了。与串形集合的直线游动不一样的是,树形集合游动情势是分岔的。所以Zipper不太适用于树形结构。scalaz尤其提供了树形集合的定势游标TreeLoc,大家看看它的定义:scalaz/TreeLoc.scala

小编们试着用这几个函数游动:

 

 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(),Stream11   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,1,Stream,19                                                   //|  ?)),TreeLoc(<tree>,Stream(<tree>, <tree>),Stream(),Stream,1,Stre20                                                   //| am,TreeLoc(<tree>,Stream(),Stream(<tree>, ?),Stream((Stream(<tree>,21                                                   //|  <tree>),2,Stream22   23   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
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]]

跳动函数:

 

  /** Select the nth child of the current node. */  def getChild: 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])] =       match {        case (acc, Stream.cons => if  Some((acc, x, xs)) else split(Stream.cons, 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

树形集合游标TreeLoc由如今节点tree、左子树lefts、右子树rights及父树parents组成。lefts,rights,parents都是在流中的树形Stream[Tree[A]]。
用Tree.loc能够一直对目的树生成TreeLoc:

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(),Stream11   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,1,Stream
 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())

小心:上边四个跳动都成功了。假设不可能跳转结果会是None
insert,modify,delete这么些操作函数:

 

  /** 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  /** Modify the label at the current node with the given function. */  def modifyLabel(f: A => A): TreeLoc[A] = setLabel(f)  /** Get the label of the current node. */  def getLabel: A = tree.rootLabel  /** Set the label of the current node. */  def setLabel: 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 => Some(loc(t, lefts, ts, parents))    case _                  => lefts match {      case Stream.cons => Some(loc(t, ts, rights, parents))      case _                  => for (loc1 <- parent) yield loc1.modifyTree((t: Tree[A]) => node(t.rootLabel, Stream.Empty))    }  }

TreeLoc的游动函数:

用法示范:

 

 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,1,Stream13   14   tl.get.toTree.drawTree                          //> res8: String = "115                                                   //| |16                                                   //| +- 1117                                                   //| |18                                                   //| `- 10219                                                   //|    |20                                                   //|    `- 12121                                                   //| "22   
  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)

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,1,Stream27   l.get.toTree.drawTree                           //> res7: String = "128                                                   //| |29                                                   //| +- 1130                                                   //| |31                                                   //| `- 232                                                   //|    |33                                                   //|    +- 2134                                                   //|    |35                                                   //|    `- 336                                                   //|       |37                                                   //|       `- 3138                                                   //| "

我们试着用这一个函数游动:

经过scalaz的Tree和TreeLoc数据结构,以及一整套树形结构游览、操作函数,大家得以便宜有效地促成FP风格的不可变树形集合编程。

 

 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()), ?)))

 

留意:下边多少个跳动都成功了。假若不可能跳转结果会是None
insert,modify,delete这一个操作函数:

  /** 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                                                   //| "

通过scalaz的Tree和TreeLoc数据结构,以及壹整套树形结构游览、操作函数,大家可以一本万利实用地促成FP风格的不足变树形集合编制程序。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

相关文章