Scalaz(24)- 泛函数据结构: Tree-数据游览和保护

果不其然能行,而且还能够将”B”节点合并汇集。这个函数的作者简直就是独神,起码是单算法和FP语法运用大师。我则还无法直达大师之水平会写来这般的泛函程序,但好奇心是遮不鸣金收兵的,总想打听是函数是怎运作的。可以用有些测试数据来慢慢跟踪一下: 

  9、开发人员修复Bug

 

  15、附件下充斥

   一些于标准的内部测试文档不克共享出来,所以找测试用了有删减版的测试文档与模板,大家如果发生趣味之言语可以下载看。

测试文档.rar

 

出于框架不是很成熟,很多情侣不是为此来读而是一直用到品种蒙,但不熟识框架引起广大稍题目,所以停止提供下载,出需要上学之好交群共享里生,不便的处约谅解。

 

修改模板函数GetFieldValue执行更新时,条件字段为null的挺,更新后呼吁复生成逻辑层代码

 

 

 版权声明:

  本文由AllEmpty原创并公布于博客园,欢迎转载,未经自己同意要保留这个段子声明,且以文章页面明显位置让闹本和链接,要不保留追究法律责任的权。如发生问题,可以由此1654937@qq.com
联系自身,非常感谢。

 

  发表本编内容,只要主为了同豪门一同学习共同进步,有趣味之朋友可以加加Q群:327360708
,大家一块儿追。

 

  更多内容,敬请观注博客:http://www.cnblogs.com/EmptyFS/

 

 

 

* 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]]
...

  15、附件下充斥


 

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

  12、灵活使用压力测试工具

  对于开发人员,除了自测外动测试工具的空子连无多,而在项目进展优化等或者上线后版迭代时,使用一些压力测试工具(比如Jmeter)对友好之代码进行压力测试还是异常有必要之。如果无亮堂压力测试工具的说话,那么写起的代码就发或受不停止上丝后的下压力,而招致网站访问缓慢、客户流失。同时自己生为难分析产生代码的瓶颈做好优化办事。

  举几只例证让大家看:

  曾经试了针对性一部分客户的网站做过压力测试(中小型电商网),10单连作运行一会晚网站就是吊掉了。

  以前曾插手开发了一个电商网,300单连作运行了后,CPU与内存正常,但服务器出口带来富一碰头就爆掉了,查明原因是网站图过多了好,需要以图纸与网站服务器分开处理。

  也曾经跃跃欲试过服务器性能一下暴跌得老盛,检查发现凡是由某些数据表记录量过特别,导致数据库查询运算占用了长日子,导致CPU飚升。

  以前做过的一个电商网,在压力测试时1K并发没有问题,然后对有些重中之重的数量表添加记录,当记录多及个别时即便意识了有些杀,检查下意识凡是由采取NOSQL缓存,程序一次性加载的记录量过非常时,加载时间了长导致数据加载超时出现异常。

  ……

  从者例子可以望,很多题材还好当上线前透过有些测试工具提前查找出来,而未是上线后面世问题重新开展优化处理。有的题材或许得透过优化手段解决,而部分则可能得对少数代码,甚至要针对框架架构进行改动才能够搞定,提早发现题目可以拉咱减过多不必要之损失。

  当然要来业内的测试师帮您办好这些工作的话,那开发人员就足以轻松多。

 

据称这pathTree函数能拿List里的目录结构转化成Tree。先看看到底是不是富有这样效果:

  6、关于测试用例

  于即将完成代码工作,进入测试阶段前,通常测试人员会跟技能联合开个小会讨论测试的系工作,而这时候测试人员会用他们编好之测试用例转发一卖让到我们。一份详细的测试用例,会带动被咱很多之惊奇喜,使我们发现本测试还可以如此打的,程序是这么操作爆出Bug的。就仿佛突然前面以咱们的前打开了扳平鼓大门,让咱们的思路和视野突然开阔了起来。

  看测试师给的测试用例后,才理解好写的代码对于片输入判断还是产生很多地方没有考虑到的,才亮原来测试是这么做的。多看测试用例,可以减我们先后出现的Bug,特别是描摹购物车、订单之类的成效,稍微一个大意就得来漏洞,给他人攻击。

  会员登陆测试用例:

  图片 1

 

 

  7、执行测试用例

 

  4、关于软件测试

这就是说Tree就是只Monad,也是Functor,Applicative,还是traversable,foldable。Tree也兑现了Order,Equal实例,可以拓展价值的依次比较。我们就算就此把例子来证明吧: 

  5、关于测试计划

  顾名思义,制定测试计划,就是布局好将进行的测试工作计划。

  俗话说没规矩无成为方圆,制定出测试计划后才会配置好实际的办事步骤,协调有关人口配合做好对应工作,做好对接下去的测试工作。一个测试计划应包括:产品核心状况调研、测试需要说明、测试策略与笔录、测试资源配置、计划表、问题跟报告、测试计划的评审、结果等等(摘自网上,具体内容请出趣味的恋人自行检索有关文章)。其实呢堪略的知晓也,要修测试计划,首先使查项目有关的各种文档,了解需要、功能和系统结构,然后又依据功能模块与各个测试阶段来安排工作计划。

  举行呢一个开发人员,我们不待知道测试计划具体怎么去编写,整个测试计划如何履行,但我们须了解测试的劳作内容是什么,这便于加强我们出效率,减少Bug的出现。根据测试计划,我们特别爱安排接下的支付任务,以便配合测试人员做好对应的开发工作。当然我们惟有了解了测试的计措施,我们才能够还好之抓好自测工作。

  简单的测试计划例子:

  图片 2

  图片 3

 

 

  13、测试和版本控制

  我们开发的代码不可避免的急需更新换代,而代码的迭代过程被,测试师是一个坏关键的角色。

  虽然大部分软件商店还生应用Git、WTF、CVS、Subversion等版本控制工具来管理源代码,而具体中当成千上万软件商店得以发现这种情景,领导、运营机构要客户提出一个要求开展改动后,则抢更新至服务器遭受,根本不怕无开展正规化的测试,控制好上线版本工作,而经过发出了累累不可预知的各种题材。

  于发生测试师参与的路面临,这种光景虽于少发,原因在规范的测试会针对版本控制得比较严厉,凡是需要更新至服务器上的次第,都见面由此测试师严格的测试都无问题后,才见面更新至服务器上。而每次换代到劳动器端的版,都见面由此同多重的测试,而这些本子的源码也会创造一个分备份,做为一个安定版本单独保存,其他程序员则以中心继续进行付出,万一更新不成功则可就使用上一个本子进行调换。

 

树形集合游标TreeLoc由时节点tree、左子树lefts、右子树rights及父树parents组成。lefts,rights,parents都是在流中的树形Stream[Tree[A]]。
之所以Tree.loc可以直接对目标树生成TreeLoc:

  9、开发人员修复Bug

  对于本项工作相信大家都隔三差五于举行,所以就算不再罗嗦了。想唤起的少数不时,Bug修改时绝对不要粗心大意,很多题材即是这么有的。而改完后定要按照测试用例自测一不折不扣,宁愿花多一点岁月,而不是过于自信立马提交,那样做的话语很爱出现前故事所说的那种情景。

 

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)

  8、发现并提交Bug

  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: _*)
  }

  2、不堪回首的出往事

 

  10、对曾经修复Bug进行返测

Tree实现了下众多底接口函数:

  14、小结

  我弗是标准的测试,所以广大有关测试的底细就未详细描述了,只由开支的角度来说话出口测试的连带常识,了解一下有关测试的基础知识,如产生啊不科学或漏的处在约谅解。

  由于时日有限,所以就不针对比照框架进行完美的测试与编辑对应之测试文档(水平有限),希望大家在以的进程中窥见Bug后告诉自己转,我会尽快修复后将补丁发布出来的。

 

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)
}

  13、测试与版本控制

 合并目录:

  11、将修复完成的Bug关闭,对匪修复的Bug重新激活

 

  14、小结

 

  4、关于软件测试

  软件测试,是为此来推动鉴定软件之科学、完整性、安全性以及质地的进程。软件测试的经典定义是:在确定之尺码下对先后开展操作,以发现先后不当,衡量软件质量,并对其是否能满足设计要求开展评估的过程。

  对于软件测试,在软件开发周期中,它是好关键之同一起工作。一个软件最终颁后质量怎么,这就要扣测试专不正经了。

  从软件开发的长河仍号划分出
  1)单元测试
  2)集成测试
  3)确认测试
  4)系统测试
  5)验收测试
  6)回归测试
  7)Alpha测试
  8)Beta测试

  以上是规范测试的归类,而于我们开发人员经常接触的虽然是底下这些内容。

  Web测试阶段分开主要概括下面内容:

  功能测试、界面测试、兼容性测试、安全测试、性能测试(包括负载/压力测试)、预发布测试(如果严格点来说还会分开不同条件做多一点栽测试)等。

  当然也发转变外一律种植说法:功能测试、界面测试、可靠性测试、易用性测试、可维护性测试、性能测试、可移植性测试、安全性测试等。

  正规的测试流程包括下面几乎接触(每个阶段大多还见面随下流程来开展):
  1)制定测试计划
  2)编写测试用例
  3)执行测试用例
  4)发现并交Bug
  5)开发人员修复Bug
  6)对曾经修复Bug进行返测
  7)将修复完成的Bug关闭,对不修复的Bug重新激活

  测试过程被得编制的文档有好多,但总的来说每个阶段如果编的文档主要发生测试计划、测试方案、测试用例和测试报告。

 

故此法示范:

  3、测试推动开发之成材——将Bug消灭在自测中

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

  3、测试推动开发的成长——将Bug消灭在自测中

   还是说说一个稍稍故事,4月份常常生星星点点员同事负责一个电子商务网站的报、登录、密码修改、忘记密码,弄了四五上才搞定(当然除了是事情他还来其它事情在百忙之中),总是提交测试于回去,然后修改再付,再起回……这个更了N次,气得晴大哥吐血,聊天记录不便宜全部犯下,而这种事情是否也早就产生在公、我、他……大家之身上吗?

  图片 4

  事后她们友善总,主要还是匪足够严谨,粗心大意引起的,且做到后一直是自以为这样改就决然就了,没有经自测就扔到测试环境中。这些基本上发生在经验不足的开发者身上,而于其他老牛来说即使最好少来这种事情,因为一直牛当初也说不定被虐了千百整后成长起来了。

  当然经过这同赖深刻的训诫后,他们少独都得到了老死之发展,对于如果发表之主次自测都举行得较足,类似之业务虽比少生。而我们别程序员在晴哥近一半年之抨击之下,也发出异水平的进化,整个集团开发出的质量曾今非昔比往日而言了。

 

 

  6、编写测试用例

 

  7、执行测试用例

  我们不是格外企业,测试师只有晴哥哥一个总人口,所以提交给他测试前,我们要进行完美的自测一次,而自测时见面仍他于咱们的测试用例,逐个输入测试相同全体。而诸一样不良Bug修改后,也要召开同样糟糕到的测试。对于欲耐心的同等举又平等普的准测试用例操作,对于我这样脾气很好耐心也是的食指有时候都见面深感烦躁,有时想偷一下累没有完全以测试用例做好自测工作,就给晴哥哥抓个现行,当然让抓捕现行的不仅仅是自身,还出其它同事,哈哈……看到大家还受虐了同等尽,心情自然为不利了……对晴哥哥已经不克算得佩服了,应该是至了钦佩的顶礼膜拜者层次了。

 

 

  11、将修复好的Bug关闭,对无修复的Bug重新激活

  测试师返测完毕后,如果无发现发题目就会见将Bug关闭,而后续出现Bug,则会重新激活这个Bug……再然后是程序员就难受了……继续他的Bug修复之路……

 

find用法示范:

  2、不堪回首的支出往事

  几乎每个开发人员都见面坚信自己的这次修改形成经过,没有Bug,然后一次次于摧毁这种幻想回到现实。这种经历犯傻的事体我以前为时常产生,而结果可想而知。

  03、04年之早晚,开发的网站多没测试就直放大上线,经常报黄页或错后,才立马进行修改,弄得晕头转向的。

  08年之时光以深圳等同寒软件企业上班,有一样不成帮东莞客户于供应链管理网多部分新的效益,在当地写了程序后我反省后看没问题,然后更新代码并写SQL语句更新数据,其中起同样修删除语句要抹某个条件的记录,动手前想得好,可写的时刻忘了加条件,然后径直以生育环境达到付出实施……将通纪念录全删除了,而这而非亮堂数据恢复,公司为未吃权力上百度那些网站,整个人瞬间即使蒙了……还吓老板那里出数据库备份,帮忙恢复了回……

  11年的早晚以举行KJava手机端应用开发,有相同次于而对准动进行相同次好有些的改,改了后自我感觉应该对其余地方并未影响,然后就付给运营机构开群发,当时运营部门也从不测试直接坐网站及,并大力发送。过了十大抵分钟查数据发现没扣费记录,然后再测量了软件才察觉原先有个参数改的时光给注释掉了+_+
……还好群发的数据量不算是尽怪,损失不多……

  ……

  还有多藏的历史或生在同事身上的囧事,现在且记不知底了,而起这些业务的重要性原因是,开发人员没有办好自测工作,太满。当然公司本着这同片没有注重呢是非常关键之原委,并没形成一致模拟为开发人员自律之正经,缺少测试部门。

 

 

  12、灵活利用压力测试工具

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

  1、前言

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、前言

  对于测试,很多供销社并无扣更,接触了众多情人或客户,打开网站随便点击一下,就足以非常易察觉爆黄页、404、UI变型(浏览器兼容)、流程走不通、错别字……等五花八门的不当。当然也包罗自家先工作了的号,基本上都拿测试交给了客户或网站来访者,发现发生题目常常常常是发出了问题之后。

  而己要好直接以来为如出一辙对立即同片不熟识,虽然看它怪要紧,但无非设有概念上的物,而不明白怎么去实施。经手的制品上线前为是温馨简单的测试后看没有问题就是上线,而不是系的测试。直到去年下半年,公司造成了各项在某个互联网知名企业的测试工程师大牛晴哥哥过来后,我才真的亮什么为测试,给我上了一如既往堂宝贵的科目,在他的暴力以下,整个技术集团得以充分明白的向上,当然我啊有了杀显著的成材,在是对晴哥哥无私的付与赞助表示诚心之感恩戴德,谢谢了。

 

留意:上面6单跳动都成功了。如果无法过反结果会是None
insert,modify,delete这些操作函数:

  10、对已经修复Bug进行返测

  对于我们交的Bug修复,测试人员会指向斯Bug进行重复测试,责任心强之测试师会从头来了,按测试用例一条条的双重创设记录,进行认证。从中可以看到能当测试的食指脾性和耐心是拳拳的正确,只要大家发妹子未嫁的口舌,不防可以介绍为测试师哦,哈哈哈……

 

 

  导航


  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)

  5、制定测试计划

  /** 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))
    }
  }

  8、发现并交Bug

  通过正规及非专业测试提交的Bug对比后,才知道什么才是正式精神。

  以测试时公司见面叫上几乎个客服与运营人员增援测试,而她们交的某些Bug有时会一头雾水,只知道有错了,但未亮凡是怎么回事。只有大概的几乎句或截了一半单图,认真看了大体上龙呢不知道是死页面做了什么操作后产生了……还得找到当事人慢慢沟通几潮受他重演示后才知道,有时他协调吗无理解为何会来这种情景,在那边截的图,那是虔诚的无语。

  而业内的测试,会详细的写明测试的手续,提交的内容,正常情形下要出现的始末,而产出的Bug是安来的,再下放上几乎帧详细的截图。一看便清晰明了,重现Bug也针锋相对好多,自然修复起来呢蛮容易。

  当然做吧开发人员,测试师与我们是对称的,从他们之做事态势中就可以看出她们啊很不便于,要互谅解,必竟他们用重的更同一的办事,有时心情烦燥也是好正常的,呵呵…

 

 

 

 

 

setTree和delete会替换当前节点产卵之拥有子树:

 

 

 

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

 

俺们可直接构建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   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()

通过scalaz的Tree和TreeLoc数据结构,以及一整套树形结构游览、操作函数,我们可以一本万利实用地贯彻FP风格的不行变树形集合编程。

 

 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   

使再次添一个点就一定给:

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

 
上节咱们谈论了Zipper-串形不可变集合(immutable sequential
collection)游标,在串形集合中左右游走及要素维护操作。这首我们谈谈Tree。在电子商务应用被于xml,json等格式文件的拍卖要求很之广泛,scalaz提供了Tree数据类型及连锁的巡礼和操作函数能还利于快捷的拍卖xml,json文件及系统目录这些树形结构数据的连锁编程。scalaz
Tree的定义非常简单:scalaz/Tree.scala

说到构建Tree,偶然在网上发现了这样一个Tree构建函数:

 

 

TreeLoc的游动函数:

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

 

 

 

 

加以多同叠: 

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

Tree是由一个A值rootLabel及一个流中子树Stream[Tree[A]]组成。Tree可以单独出于一个A类型值rootLabel组成,这时流中子树subForest就是空的Stream.empty。只有rootLabel的Tree俗称叶(leaf),有subForest的称为节(node)。scalaz为外类型提供了leaf和node的构建注入方法:syntax/TreeOps.scala

实际注入方法调用了Tree里之构建函数:

经过上面的跟约化我们看出List(List(A))在pathTree里的推行进程。这里将纷繁的groupBy和collect函数的用法及结果了解了。实际上任何过程相当给:

 

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

 

相信这些跟过程足够了解任何函数的工作原理了。
发生矣Tree构建方式后即得Tree的游动和操作函数了。与串形集合的直线游动不同之凡,树形集合游动方式是分岔的。所以Zipper不顶适用于树形结构。scalaz特别提供了树形集合的永恒游标TreeLoc,我们看看她的定义:scalaz/TreeLoc.scala

俺们尝试着用这些函数游动:

Leave a Comment.