hangscer

scala写算法-Tree以及有关于implicit的坑

2017/04/18
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package nathan.fp
/**
* Created by jianghang on 17/4/17.
*/
trait Tree[+A]{ self=>
import Tree.{node}
def fold[B](z:B)(f:(B,A,B)=>B):B=self match {
case EmptyTree => z
case Node(value,left,right)=>f(left.fold(z)(f),value,right.fold(z)(f))
}
def size=fold(0)((left,_,right)=>left+right+1)
def map[B](f:A=>B):Tree[B]=fold(Tree.empty[B])((left,value,right)=>Node(f(value),left,right))
def invertTreeViaFold=fold(Tree.empty[A])((left,value,right)=>Node(value,right,left))
def find(f:A=>Boolean):Tree[A]=self match {
case EmptyTree => EmptyTree
case Node(value,left,right)=> f(value) match {
case true => self
case false =>left.find(f) match {
case EmptyTree => right.find(f)
case i => i
}
}
}
def findMin:Tree[A]=self match {
case Node(_,left,_) => left match {
case EmptyTree => self
case _ => left.findMin
}
}
def findMax:Tree[A]=self match {
case Node(_,_,right) => right match {
case EmptyTree=> self
case _ => right.findMax
}
}
//这里有个坑 implicit 有无问题
def insert[B>:A](x:B)(implicit numeric: Numeric[B]):Tree[B]=self match {
case EmptyTree =>node[B](x)
case Node(value,left,right) => Tree.compare(x,value) match {
case 1 =>Node(value,left,right.insert(x))
case 0 =>self
case -1=>Node(value,left.insert(x),right)
}
}
def invert:Tree[A]=self match {
case EmptyTree => EmptyTree
case Node(value,left,right)=>Node(value,right.invert,left.invert)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
case object EmptyTree extends Tree[Nothing]{
override def toString: String = "N"
}
case class Node[A](value:A,left:Tree[A],right:Tree[A]) extends Tree[A]
object Tree{
def empty[A]:Tree[A]=EmptyTree
def node[A](value:A,left:Tree[A]=empty,right:Tree[A]=empty)=
Node(value,left,right)
def compare[A](a:A,b:A)(implicit numeric: Numeric[A])=numeric.compare(a,b)
def height[A](tree: Tree[A]):Int=tree match {
case EmptyTree=>0
case Node(_,left,right)=>
val left_height=height(left)
val right_height=height(right)
(if(left_height>right_height) left_height else right_height)+1
}
}

由于Tree需要实现范型类型变量的比较,本程序意在实现算法本身,所以采用Int类型的比较方法def compare[A](a:A,b:A)(implicit numeric: Numeric[A])=numeric.compare(a,b), 本方法定义在object Tree中,在class Tree中的insert方法中调用.必须在调用compare的方法上再次传入implicit参数,如下:

1
2
3
4
5
def insert[B>:A](x:B)(implicit numeric: Numeric[B]):Tree[B]={
...
Tree.compare(...)
...
}

而不是:

1
2
3
4
5
def insert[B>:A](x:B)={
...
Tree.compare(...)
...
}