Scalaz(24)- 泛函数据结构: Tree-数据游览及保卫安全

一旦总结有些公司 company 的雇员平均年龄。即 age
字段的丰硕,然后除以雇员数量。先计算一下 DevCode 公司:

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

此地的“case(key,value)”表达了Scala提供的形式匹配机制是多么强大。请参见Scala的文书档案来获得更加多的消息。

 

scala> devCodeEmployees

 

res3: List[Employee] = List(Employee(Anna,30,DevCode), Employee(guest,30,DevCod

 

), Employee(Thomas,41,DevCode))

 

scala> val devCodeAges=devCodeEmployees.map(_.age)

 

devCodeAges: List[Int] = List(30, 30, 41)

 

scala> val devCodeAverageAge=devCodeAges.sum / devCodeAges.size

 

devCodeAverageAge: Int = 33

 

scala>
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                                                   //| "
scala> val darth=Employee("Darth","DevCode")

 

<console>:9: error: type mismatch;

 

 found   : String("DevCode")

 

 required: Int

 

       val darth=Employee("Darth","DevCode")

 

                                  ^

 

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

正文只是带你进去 Scala 的世界,蕴涵安装、不可变量 val、可变量
var、定义类、集合(包蕴列表(list)、集(set)、映射(map))以及集聚遍历和集合库(能达到并行/并发效果)。

题外话,如若 Java 争气的话,还就真不晤面世像 Scala
这几个语言。对于函数式编制程序风格的支撑,尤其是对此 拉姆da
表明式的扶助,能收缩必要求编写制定的逻辑毫不相关的样板代码,让程序员集中精力任务自作者。而
Java 对 Lamdba 表明式的支撑到 JavaSE8 才落到实处(你能够查一下 Java SE8
的颁发时间,和别的语言在语言层面上曾几何时帮助的匿名函数、拉姆da
表达式、函数式编制程序、并行编制程序……)。

Scala,一门强类型定义的静态类型语言,结合了面向对象编制程序与函数式编制程序思想,语法简洁,完全匹配
Java,运维在 JVM 上。JVM 上的任何语言还有 Groovy、JRuby、Clojure,而
Scala
有怎么着两样?——能同时提供函数式风格和可观并发援救的强类型语言,只有Scala。JRuby 和 Groovy 都是动态语言(Scala
是静态类型语言),它们不是函数式的,也无从提供比 Java
更好的面世化解方案。另一方面,Clojure
是一种混合型的函数式语言,它天生便是动态的,因而不是静态类型。而且它的语法类似
Lisp,除非您很熟习,不然那可不是一种易于明白的语言(Lisp
是名叫高智的人才能使用的言语,假若您看过《黑客与美术师》,应该记得作者的一句话,马虎是,假设竞争对手采取Lisp 开发 Web,那就应有小心了,言下之意是,Lisp
跟任何语言比较,生产成效太高了,很不难达成三个想方设法)。

计算起来,Scala 特点浮以往偏下几上边:

  • 也运行在 JVM 上,使 Scala 能够和现存的选取还要运营;
  • 能够直接运用 Java 类库,使开发职员能够采用现有的框架和遗留代码;
  • 与 Java 一样都是静态类型语言。遵从千篇一律的编制程序理学;
  • 语法与 Java
    比较相近,使得开发人士能够长足驾驭语言功底(看怎么写,我觉得Scala的凝练程度,会让初我们崩溃);
  • 既支持面向对象范型,也支撑函数式编程范型,开发职员能够稳步选取函数式编制程序的思考。

Scala 对 Java 的不同:

  • 花色推测。Java 中必须注明变量、实参或形参的门类。而在 Scala
    中则不用,它会估量出变量的品种;
  • 函数式编制程序。Scala 将函数式编制程序的重点概念引入
    Java,包罗代码块、高阶函数(high-order
    function)以及错综复杂的集合库;
  • 不变量。Java
    也同意利用不变量,但是是透过一个很少使用的修饰符完成的。此外,Java
    的 String 也是不变量的七个完毕,而 Scala
    会让你控制一个变量是不是可变,比如 val,还是var。这将对程序在出现环境中的行为,产生巨大影响;
  • 高等程序构造。Scala
    很好地行使了根基语言,并将实惠的定义分层。包罗并发 Actor
    模型、使用高阶函数 Ruby
    风格的聚众以及作为头号对象类型(first-class)的 XML 处理。

文中代码自身在 Scala 2.11 上编写翻译并运维通过。

第贰步,先安装好 Scala Typesafe
stack
,打开命令行窗口,键入“scala”,将开行REPL(读入-运算 输出 循环)交互式编码环境。然后就可以写下您的第叁行
Scala 代码:

 

假设 allEmployees 集合是选用 SQL 查询获得的,类似 SELECT \ FROM
employees WHERE company = ‘DevCode’ 。今后用 groupBy 函数按 company
分组,就会得到二个以
company 为键、Employee 为值的 Map*:

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

其余集合方法,可以参见 scaladoc
API
。那个方式结合起来(例如:numbers.reverse.filter……)使用会让代码特别简洁,不过尔尔会潜移默化可读性。

最后,{ n => n + 10 } 能够大概地写成 (_ + 10),也正是说,n
是个匿名变量,叫什么都行,还不用注解。那么,下划线的地方代表要求用你列表中的每一个元一向填补的空域。(与“_”的效果看似,Groovy
保留了重点字 it,Python 则使用的是 self)。

其实,用 (_ + 10) 来代替 { n => n + 10 },就是将 n=>n 换成
_,因为,n 不要求注脚的内部匿名变量,有重复的嫌疑。那更阐明 Scala
是何许简洁。

 

scala> case class Employee(name:String="guest",

 

     | age:Int=30,

 

     | company:String="DevCode")

 

defined class Employee

 

scala>

加多一层: 

回去地点的商店分组,Map (key:String
->value:List[Employee]),假使想计算分组内职工的平均年龄,唯有几行代码:

 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   

MapReduce.scala:

case class Employee(name: String = "guest", age: Int = 30, company: String = "DevCode")

 

    object MapReduce {

        def main(args: Array[String]): Unit = {

 

        val guest = Employee()

        val anna = Employee("Anna")

        val thomas = Employee("Thomas", 41)

        val luke = Employee("Luke", company = "LucasArt")

        val yoda = luke.copy("Yoda", age = 800)

 

        val allEmployees = List(luke, anna, guest, yoda, thomas)

        val sortedEmployees = allEmployees.groupBy(_.company)

        val averageAgeByCompany = sortedEmployees.map { case (key, value) =>

            value(0).copy(name = "average", age = (value.map(_.age).sum) / value.size)

      }

        println("Result: "+averageAgeByCompany)

    }

}

相信这么些跟踪进程丰裕通晓整个函数的行事规律了。
有了Tree营造立模型式后就须求Tree的游动和操作函数了。与串形集合的直线游动分化的是,树形集合游动格局是分岔的。所以Zipper不太适用于树形结构。scalaz特别提供了树形集合的永恒游标TreeLoc,大家看看它的定义:scalaz/TreeLoc.scala

scala> val hightNumbers=numbers.map (_+10)

 

hightNumbers: List[Int] = List(11, 12, 13)

 

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

那里的 for 循环语法结构非凡相近于 Java 的命令式编制程序风格。在
Scala(以及 Java 虚拟机上任何过多言语如:Groovy、JRuby 或
JPython)里还有别的一种方法来完毕地点的逻辑。这种方法接纳一种更加偏向函数编制程序的作风,引入了
拉姆da 表明式(有时也叫做闭包——closure)。简单地说,Lambda
表达式就是您能够拿来作为参数字传送递的函数。那些函数使用参数作为输入(在这些例子中正是n 整型变量),重临语句作为函数体的最终语句。他们的款式如下:

 

运作结果:

 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                                                   //| "
scala> val columbus: Int = 1492

 

columbus: Int = 1492

 

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

不要求像 Java 中那么还要定义字段以及 setter 和 getter 方法。这几个对
Scala 来说,是规范代码,完全是多余的。

case 关键字相当于 Java 的 switch
语句,可是更灵敏。它表达该类具有格局匹配的额外机制,以及别的部分风味,包括用来创立实例的厂子方法(不需求使用
new 关键字来组织),同样也不必要创设缺省的 getter 方法。

与 Java 分裂,默许访问控制是 public(而不是 protected),Scala 为
public 变量自动创制三个 getter
方法。当然也能够把字段定义成可变且/或个人(private)的,只要在近年来使用
var(例如,case class Person(private var
name:String)),那样您就无法透过 guest.name 来访问 name 字段。

接下去,用分化措施成立一些实例,看看其余的特征,如命名参数和缺省参数(从Scala2.8开头引入):

 

scala> val guest=Employee()

 

guest: Employee = Employee(guest,30,DevCode)

 

scala> val guestAge=guest.age

 

guestAge: Int = 30

 

scala> val anna=Employee("Anna")

 

anna: Employee = Employee(Anna,30,DevCode)

 

scala> val thomas=Employee("Thomas",41)

 

thomas: Employee = Employee(Thomas,41,DevCode)

 

scala> val luke=Employee("Luke",company="LucasArt")

 

luke: Employee = Employee(Luke,30,LucasArt)

 

scala> val yoda=luke.copy("Yoda",age=800)

 

yoda: Employee = Employee(Yoda,800,LucasArt)

 

scala>

 

functionName { input =>

    body

}

scala> numbers.foreach {n:Int=> println("Number "+n) }

 

Number 1

 

Number 2

 

Number 3

 

scala>

果然能行,而且还是可以把”B”节点合并汇集。这么些函数的撰稿人大概便是个神人,起码是个算法和FP语法运用大师。笔者纵然还无法完成大师的水平能写出这么的泛函程序,但好奇心是挡不住的,总想了然这么些函数是怎么运作的。能够用某些测试数据来逐步跟踪一下: 

对此你定义的类,Scala 自动也提供了用来克隆类实例的 copy
方法。克隆方法,也是榜样代码。从此,你就无须本人写了。

不过,下边包车型大巴写法是分外的(可不是因为 Darth 不是 DevCode
的雇员!)。

 

到那里大家的任务就到位了。我们兑现的是1个总结的Map-Reduce算法。由于各类商户雇员的联结是截然独立于任何公司,那几个算法万分直观地贯彻了并行计算。

只顾:下边八个跳动都事业有成了。如若不恐怕跳转结果会是None
insert,modify,delete那一个操作函数:

scala>  val devCodeEmployees=allEmployees.filter {_.company=="DevCode"}

 

devCodeEmployees: List[Employee] = List(Employee(Anna,30,DevCode), Employee(gues

 

t,30,DevCode), Employee(Thomas,41,DevCode))

 

scala> val oldEmployees=allEmployees.filter(_.age>100).map(_.name)

 

oldEmployees: List[String] = List(Yoda)

 

scala>

Tree落成了上边众多的接口函数:

作为首个变量传递给 foldLeft
的值0,是开头值(即在把函数用到第3个列表成分的时候 total=0)。而
(total,element) 代表了3个 Tuple2 二元组。

实质上,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]]
...

附录


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

Map Reduce.Java

public class Employee {

 

    final String name;

    final Integer age;

    final String company;

 

    public Employee(String name, Integer age, String company) {

        this.name = name == null ? "guest" : name;

        this.age = age == null ? 30 : age;

        this.company = company == null ? "DevCode" : company;

    }

 

    public String getName() {

        return name;

    }

 

    public int getAge() {

        return age;

    }

 

    public String getCompany() {

        return company;

    }

 

    @Override

    public String toString() {

        return "Employee [name=" + name + ", age=" + age + ",

               company="

               + company + "]";

    }

}

 

class Builder {

    String name, company;

    Integer age;

 

    Builder(String name) {

        this.name = name;

 

    }

 

    Employee build() {

        return new Employee(name, age, company);

    }

 

    Builder age(Integer age) {

        this.age = age;

        return this;

    }

 

    Builder company(String company) {

        this.company = company;

        return this;

    }

}

 

import java.util.ArrayList;

import java.util.Collection;

import java.util.List;

import com.google.common.base.Function;

import com.google.common.collect.ImmutableListMultimap;

import com.google.common.collect.ImmutableSet;

import com.google.common.collect.Multimaps;

 

public class MapReduce {

 

    public static final void main(String[] args) {

        Employee guest = new Builder("Guest").build();

        Employee anna = new Builder("Anna").build();

        Employee thomas = new Builder("Thomas").age(41).build();

        Employee luke = new

            Builder("Luke").company("LucasArt").build();

        Employee yoda = new

            Builder("Yoda").age(800).company("LucasArt").build();

 

        Collection<Employee> employees = new ArrayList<Employee>();

        employees.add(guest);

        employees.add(anna);

        employees.add(thomas);

        employees.add(luke);

        employees.add(yoda);

 

        ImmutableListMultimap<String, Employee>

            personsGroupByCompany = Multimaps.index(employees, new Function<Employee,String>() {

 

                public String apply(Employee person) {

                   return person.getCompany();

                 }

 

              });

 

        ImmutableSet<String> companyNamesFromMap =

            personsGroupByCompany.keySet();

 

        List<Employee> averageAgeByCompany = new

            ArrayList<Employee>();

 

        for(String company: companyNamesFromMap) {

             List<Employee> employeesForThisCompany =

                personsGroupByCompany.get(company);

             int sum = 0;

             for(Employee employee: employeesForThisCompany) {

                 sum+= employee.getAge();

             }

             averageAgeByCompany.add(new

                Employee("average",sum/employeesForThisCompany.size(),company));

     }

     System.out.println("Result: "+averageAgeByCompany);

 

    }

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

参考资料


 

scala> val reversedList=numbers.reverse

 

reversedList: List[Int] = List(3, 2, 1)

 

scala> val numbersLessThan3=numbers.filter {n=>n<3}

 

numbersLessThan3: List[Int] = List(1, 2)

 

scala> val oddNumbers=numbers.filterNot {n=>n%2==0}

 

oddNumbers: List[Int] = List(1, 3)

 

scala> val highterNumbers=numbers.map {n=>n+10}

 

highterNumbers: List[Int] = List(11, 12, 13)

 

scala>

 

scala> var columbus = 1492

 

columbus: Int = 1492

 

scala> columbus = 1500

 

columbus: Int = 1500

 

scala>

 

scala> val numbers=List(1,2,3)

 

numbers: List[Int] = List(1, 2, 3)

 

scala> for(n<-numbers) println("Number "+n)

 

Number 1

 

Number 2

 

Number 3

 

scala>

设若再充实二个点就一定于:

scala> val averageAgeByCompany = sortedEmployees.map{ case(key,value)=>

 

     | value(0).copy(name="average",age=(value.map(_.age).sum)/value.size)}

 

averageAgeByCompany: scala.collection.immutable.Iterable[Employee] = List(Employ

 

ee(average,33,DevCode), Employee(average,415,LucasArt))

 

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

介绍了对整数集合的骨干处理后,能够进入下一阶段,如何对复杂集合的转换,例如,使用方面定义的
Employee 类:

 

看看了啊,功能在集结上函数,你可以不写圆括号,少了不可枚举典范代码。

变换 map 相当有用,它对列表的每种成分选拔闭包,重返1个新的列表。

大家在此地还想介绍最终的三个主意,就是
foldLeft,它把状态从3个因素传播到另一个要素。比如,要算出三个列表里拥有因素的和,你须要丰硕,并在切换来分的时候保存中间的计数:

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

scala> columbus=1500

 

<console>:8: error: reassignment to val

 

       columbus=1500

 

               ^

 

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

地点的事例中,函数体只有一条语句(println……),重返“空结果”Unit,差不多也就是Java 中的 void。

除此之外打字与印刷列表外,大家更想对列表相月素做些处理和转换。让大家尝试一些例证:

 

Number 1

 

Number 2

 

Number 3

 

scala> val sortedEmployees=allEmployees.groupBy(_.company)

 

sortedEmployees: scala.collection.immutable.Map[String,List[Employee]] = Map(Dev

 

Code -> List(Employee(Anna,30,DevCode), Employee(guest,30,DevCode), Employee(Tho

 

mas,41,DevCode)), LucasArt -> List(Employee(Luke,30,LucasArt), Employee(Yoda,800

 

,LucasArt)))

 

scala>

 

List<Integer> numbers = new arrayList<Integer>();

numbers.add(1);

numbers.add(2);

numbers.add(3);

for(Integer n:numbers) {

    System.out.println("Number "+n);

}

 

在末端的附录里给出了此算法的杰出的贯彻,分为Java版本和Scala版本。

find用法示范:

有关小编

图片 1

Thomas亚历克斯andre是DevCode的高等咨询顾问,专注于Java和Scala软件开发。他心爱技术,热衷于分享文化,永远在谋求办法、采用新的开源软件和行业内部来落到实处更为可行的编制程序。在十四年的Java开发经历之外,过去几年他集中精力在新的编制程序语言和Web框架上,例如Groovy/Grails和Scala/Lift。托马斯从法兰西新山大学得到了计算机科研生学位,在卡耐基梅隆高校走过了两年的大学生后硕士涯,斟酌方向是高枕无忧和电子商务。

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

接下去,定义1个类,名为 Employee,有三个不可变的字段:nameage
company,拥有各自的缺省值。

Tree是由三个A值rootLabel及三个流中子树Stream[Tree[A]]重组。Tree能够只由叁个A类型值rootLabel组成,那时代风尚中子树subForest正是空的Stream.empty。唯有rootLabel的Tree俗称叶(leaf),有subForest的称为节(node)。scalaz为别的项目提供了leaf和node的营造注入方法:syntax/TreeOps.scala

宣示了2个门类为 Int 变量,开头值为 1492,就像在Java里 Int
columbus = 1492;
一样。

Scala 把项目放在变量之后(反向注解格局),使用 val
显式地把变量声明为不可变的。假如想修改这一个变量,将报错:

TreeLoc的游动函数:

原来的作品地址

Tree提供了创设和方式拆分函数:

Scala
对于可变集合和不可变集合实行了系统性地分别处理。但鼓励利用不可变集合,因此在缺省气象下创建的是不可变集合,通过模拟的艺术贯彻拉长、更新和删除。注意,这几个操作不是修改集合,而是回到新的集纳。

与后面 Java 代码等价的 Scala 代码或然像上面那样:

骨子里注入方法调用了Tree里的构建函数:

scala> val sumOfNumbers=numbers.sum

 

sumOfNumbers: Int = 6

 

scala>

 
上节大家谈谈了Zipper-串形不可变集合(immutable sequential
collection)游标,在串形集合中左右游走及要素维护操作。那篇大家谈谈Tree。在电子商务应用中对于xml,json等格式文件的处理供给丰裕之广大,scalaz提供了Tree数据类型及连锁的漫游及操作函数能更便于快速的处理xml,json文件及系统目录这么些树形结构数据的连带编制程序。scalaz
Tree的概念11分不难:scalaz/Tree.scala

荒谬音信确切地提出了错误位于行的岗位。

再尝试申明那几个变量,这一次用 var,让其可变。编写翻译器能猜测出 1492
是八个整数,所以,无需钦命项目:

 

scala> val allEmployees=List(luke, anna, guest, yoda, thomas)

 

allEmployees: List[Employee] = List(Employee(Luke,30,LucasArt), Employee(Anna,30

 

,DevCode), Employee(guest,30,DevCode), Employee(Yoda,800,LucasArt), Employee(Tho

 

mas,41,DevCode))

 

scala>

说到创设Tree,偶然在网上发现了那样七个Tree构建函数:

对那么些职员和工人集合列表,能够应用匿名方式,用一个准绳来过滤,查找 compay 为
DevCode 的职工:

 

scala> val sumOfNumbers=numbers.foldLeft(0) {( total,element)=>

 

     | total+element

 

     | }

 

sumOfNumbers: Int = 6

 

scala>

 

因为构造函数在那么些地方须要的 age
作为参数,而你又从不显性地开展命名,company=”DevCode”。

现行反革命我们再来看集合,这才是的确令人欢跃的地点。Scala
集合类型包蕴列表(list)、集(set)和照耀(map)。

有了泛型(Java5 以上),Java
遍历2个列表,比如整数型列表,代码如下所示:

跳动函数:

树形集合游标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())

 

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

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

咱们得以直接创设Tree:

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

 

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

据他们说这几个pathTree函数能把List里的目录结构转化成Tree。先看看究竟是否兼具那样效果:

用法示范:

 

 

 

通过下面的跟踪约化大家看看List(List(A))在pathTree里的执行进程。那里把纷纷的groupBy和collect函数的用法和结果理解了。实际上任何进程也便是:

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

Leave a Comment.