目录
1. 介绍
2. 纯函数式编程回顾
2.1 函数式数据类型(Pattern Matching)
函数式数据类型的实现来源于函数式函数的实现,而后者的实现就是基于Pattern Matching的。Pattern Matching其实是对函数分流本质的体现,特别是在输入Pattern对应不同的输出表达式的函数,比如递归在退出条件里和在一般条件里的输出表达式是不一样的。而Pattern Mathing简化了这一分流的实现。关于Pattern Match vs Decomposition 用来扩展类的方法的好处,我们在这篇文章中讨论过。如果对于子类种类固定的父类来扩展方法,Pattern Matching 更方便;如果对于子类种类个数会增加的父类来扩展方法,则用Decompostion更灵活。下面是Scala用Pattern Matching对JSON的一种实现。
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
object MyJSON extends App {
abstract class JSON
case class JObj(bindings: Map[String, JSON]) extends JSON
case class JSeq(elems: List[JSON]) extends JSON
case class JNum(num: Double) extends JSON
case class JBool(bool: Boolean) extends JSON
case class JStr(str: String) extends JSON
case object JNull extends JSON
def show(json: JSON): String = json match {
case JObj(bindings) =>
val assocs = bindings map {
case (key, value) => "[ " + "\"" + key +"\"" + ": " + show(value) + " ]"
}
"{ " + (assocs mkString ",\n") + " }"
case JSeq(elems) => "\n" + "[" + (elems map show mkString ",") + "]"
case JNum(num) => num.toString()
case JBool(bool) => bool.toString()
case JStr(str) => "\"" + str + "\""
case JNull => "null"
}
override def main(args: Array[String]) {
val data = JObj(Map(
"firstName" -> JStr("Johnson"),
"lastName" -> JStr("Smith"),
"address" -> JObj(Map(
"streetAddress" -> JStr("21 2nd Street"),
"state" -> JStr("NY"),
"postalCode" -> JNum(10021))),
"phoneNumbers" -> JSeq(List(
JObj(Map(
"type" -> JStr("home"),
"number" -> JStr("212 555-1234"))),
JObj(Map(
"type" -> JStr("fax"),
"number" -> JStr("646 555-4567")))))))
println(show(data))
}
}
程序本身并不困难,但其中有一些细节需要我们去解释。第15行代码的type是什么呢?显然这是高阶函数map的一个输入,也就是函数,因此有“=>“的形式。
1
{ case (key, value) => "[ " + "\"" + key +"\"" + ": " + show(value) + " ]" }
这行代码表示的是如果输入是一个pair的形式,则返回如下String,因此它的type是(String,JSON) => String
.
这是一个匿名函数,在Scala里匿名函数和函数一样,都是一个实现了def apply(args1:type1,...argsn:typen):typem
方法的类Functionn+1(type1,...typen,typem)
。因此第15行代码将会被转换成如下代码:
1
2
3
4
5
new Function1[(String, JSON), String]{
def apply(x:(String,JSON)) = x match {
case (key, value) => "[ " + "\"" + key +"\"" + ": " + show(value) + " ]"
}
}
可以看到匿名函数就像java里new出来的一个data实例,只不过没有变量来point指向这个函数。
因此函数式数据结构的实现在JSON这里例子里得到了很好的体现。
2.2 子类化函数
那么既然函数就是类,那么可否子类化函数呢?答案是可以的。
我们知道Map和函数本质上是一样的,Map对于给定的key,返回一个value,函数也是一样。在命令式编程里,数据是一等公民,而函数不是,Map是数据,因此函数也是数据建立在data比function优先的基础上。这里我们要讲的是另外一面,在函数式编程里,函数提升到一等公民(数据当然也是),甚至可以认为比数据更优先。因此Map,即数据,是可以通过继承函数来实现的。这就是我们所说的子类化函数。
1
2
trait Map[Key, Value] extends (Key => Value)...
trait Seq[Elem] extends Int => Elem ...
除了上述的数据类型Map
继承(Key=>Value)
,Seq
继承Int=>Elem
。还有一个特殊的函数继承函数,那就是Partial Function。
1
2
3
4
5
6
7
8
9
10
11
12
13
val pf: PartialFunction[String, String] = { case "Ping" => "Pong" }
pf.isDefinedAt("Ping") //return true
pf.isDefinedAt("Hello") //return false
pf("Ping") //return Pong
pf("hello") //exception
if (pf.isDefinedAt("Hello") pf("hello") //no exception
trait PartialFunction[-A,+R] extends Function1[-A,+R]{
def apply(x:A):R
def isDefinedAt(x:A):Boolean
}
Partial Function继承了函数,同时声明了def isDefinedAt(x:A):Boolean
。因此为了避免调用函数时抛出未定义的异常,我们先用isDefinedAt
判断再取值。
2.3 Collection Hierachy
在Scala里,Collection作为Algebraic Data Type(ADT),它的Class Hierachy 如下图所示。
这些Collection子类都有一些重要的高阶函数,如map
,flatMap
,filter
和foldLeft
,foldRight
等。List对其中一些方法的实现如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def map[U](f:T=>U):List[U] = this match {
case x::xs => f(x):: xs.map(f)
case Nil => Nil
}
def flatMap[U](f: T=>List[U]):List[U] this match {
case x::xs => f(x) ++ xs.map(f)
case Nil => Nil
}
def filter(f: T=>Boolean):[T] this match {
case x::xs => if(f(x)) x :: xs.filter(f) else xs.filter(f)
case Nil => Nil
}
这些高阶函数其实是Category Thoery里对于Monoid(foldRight,foldLeft),Functor(map),Monad(flatMap)的实现。这些我们在第三部分讨论。
2.4 for表达式本质
for表达式其实是对filter
,flatMap
,map
应用的一种语法糖。
1
2
3
4
5
6
7
8
9
10
(1 until n) flatMap (i=>
(1 until i) filter (j =>
isPrime(i+j)) map (j=>
(i,j))
//简化成
for{
i <- 1 until n
j <- 1 until i
if isPrime(i+j)
} yield (i,j)
需要注意的是<-
的左边也可以是pattern,比如
1
2
3
4
5
6
7
for {
JObj(bindings) <- data
JSeq(phones) = bindings("phoneNumbers")
JObj(phone) <- phones
JStr(digits) = phone("number")
if digits startsWith "212"
} yield (bindings("firstName"), bindings("lastName"))
这里是找到所有电话号码以212开头的JObj,然后将firstName和lastName返回。
2.5 随机数产生器
3. 范畴轮(Category Thoery)
3.1 幺半群(Monoid)
3.2 函子(Functor)
3.3 应用函子(Applicative Functor)
3.4 单子(Monad)
4. 响应式编程(Reactive Programming)
- 还有一点需要注意的是性能问题,对于之前探索过的
Set[State]
,Path
extend后要过滤掉回到之前State
的Path。