泛函编程(8)-数据结构-Tree

    上节介绍了泛函数据结构List及相关的泛函编程函数设计使用,还附带了少许多态类型(Polymorphic Type)及变形(Type Variance)的介绍。有关Polymorphism的详细介绍会放在typeclass讨论中。为了更多了解泛函数据结构(Functional Data Structure),想在这个章节把另一个我们熟悉的数据结构-Tree做些简单介绍。

  Tree的状态不是枝(Branch)就是叶(Leaf),这个很容易理解。那么就按照上节设计List那样设计Tree类型:

1   trait Tree[+A] 
2   case class Leaf[A](value: A) extends Tree[A]
3   case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

类参数+A代表协变(covariant),这个在上节List中已经介绍过了。先创建一个Tree实例(Tree Instance):

1  val tree = Branch(Branch(Leaf(1),Leaf(2)),Branch(Branch(Leaf(10),Leaf(8)),Leaf(3)))
2                                                   //> tree  : ch3.tree.Branch[Int] = Branch(Branch(Leaf(1),Leaf(2)),Branch(Branch(
3                                                   //| Leaf(10),Leaf(8)),Leaf(3)))

创建了一个Tree Instance tree,如下图:

数数有几个节点:

1       def size: Int = this match {
2           case Leaf(_) => 1
3           case Branch(l,r) => 1 + l.size + r.size
4       }
1   tree size                                       //> res0: Int = 9

这是所有branch + leaf 总数。

分开计算branch 和 leaf 数量:

1       def countLeafs: Int = this match {
2           case Leaf(_) => 1
3           case Branch(l,r) => 0 + l.size + r.size
4       }
5        def countBranches: Int = this match {
6           case Leaf(_) => 0
7           case Branch(l,r) => 1 + l.size + r.size
8       }
9  
1   tree.countLeafs                                 //> res1: Int = 8
2   tree.countBranches                              //> res2: Int = 9

探探最深有多深:

1       def depth: Int = this match {
2           case Leaf(_) => 0
3           case Branch(l,r) => 1 + (l.depth max r.depth)
4       }
1   tree depth                                      //> res1: Int = 3

找出最大值的Leaf:

1       def maxValue: Int = this match {
2           case Leaf(a: Int) => a
3           case Branch(l,r) => l.maxValue max r.maxValue
4       }
1  tree maxValue                                   //> res2: Int = 10

可以从以上这些函数得出一下共性。把共性抽象出来用fold来实现:

1         def fold[B](f: A => B)(g: (B,B) => B): B = this match {
2             case Leaf(n) => f(n)
3             case Branch(l,r) => g(l.fold(f)(g), r.fold(f)(g))
4         }

函数fold分别收到两个方法f,g:f用来处理Leaf,g用来处理Branch。看看用fold来实现上面的函数:

1         def sizeByfold = fold(a => 1)(1 + _ + _)
2         def maxValueByfold(l: Tree[Int]) = l.fold(a => a)((x,y) => 0 + (x max y))
3         def depthByfold = fold(a => 0)((x,y) => 1 + (x max y))
1   tree sizeByfold                                 //> res3: Int = 9
2   
3   tree depthByfold                                //> res4: Int = 3
4   
5   tree.maxValueByfold(tree)                       //> res5: Int = 10

 可能这个 tree.maxValueByfold(tree) 有点怪,但如果把函数实现放到 object Tree里然后import Tree._就可以了。

下面把map和flatMap实现了:

1       def map[B](f: A => B): Tree[B] = this match {
2           case Leaf(a) => Leaf(f(a))
3           case Branch(l,r) => Branch(l.map(f),r.map(f))
4       }
5       def flatMap[B](f: A => Tree[B]): Tree[B] = this match {
6           case Leaf(a) => f(a)
7           case Branch(l,r) => Branch(l.flatMap(f), r.flatMap(f))
8       }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

框架开发之Java注解的妙用

2.本来可能需要很多配置文件,需要很多逻辑才能实现的内容,就可以使用一个或者多个注解来替代,这样就使得编程更加简洁,代码更加清晰。

993
来自专栏JadePeng的技术博客

JavaScript 实现接口 (Interfaces In JavaScript)

接口是面向对象编程里的重要特性,遗憾的是JavaScript并没有提供对接口的支持!怎么实现接口呢? 在实际中,我们可以在注释中定义好接口,在实际的代码中予以实...

3566
来自专栏青玉伏案

Java编程之反射中的注解详解

“注解”这个词,可谓是在Java编程中出镜率比较高,而且也是一个老生常谈的话题。我们之前在聊Spring相关的东西时,注解是无处不在,之前我们简单的聊过一些“注...

1806
来自专栏GIS讲堂

Geotools中蜂巢的实现

1222
来自专栏浪淘沙

java设计模式--组合

import java.util.ArrayList; import java.util.List;

1121
来自专栏difcareer的技术笔记

JNI实现源码分析【四 函数调用】正文0x01:dvmCallMethodV0x02:nativeFunc0x03: 何时赋值

有了前面的铺垫,终于可以说说虚拟机是如何调用JNI方法的了。JNI方法,对应Java中的native方法,所以我们跟踪对Native方法的处理即可。

854
来自专栏ImportSource

图解ByteBuffer

概述 ByteBuffer是NIO里用得最多的Buffer,它包含两个实现方式:HeapByteBuffer是基于Java堆的实现,而DirectByteBuf...

3725
来自专栏游戏杂谈

JavaScript立即调用的函数表达式

主要参考知乎上这个问题:javascript 匿名函数有哪几种执行方式 长天之云的回答。

962
来自专栏黑泽君的专栏

day19_java基础加强_动态代理+注解+类加载器

        Proxy Pattern(即:代理模式),23种常用的面向对象软件的设计模式之一。         代理模式的定义:为其他对象提供一种代理以控...

984
来自专栏静晴轩

lua表排序

Lua作为一种很强大且轻量级脚本语言的存在,对于掌握其几乎无所不能的Table(其实就是一个Key Value的数据结构,它很像Javascript中的Obje...

40111

扫码关注云+社区