目录


1. 介绍

2. 纯函数式编程回顾

2.1 函数式数据类型(Pattern Matching)

函数式数据类型的实现来源于函数式函数的实现,而后者的实现就是基于Pattern Matching的。Pattern Matching其实是对函数分流本质的体现,特别是在输入Pattern对应不同的输出表达式的函数,比如递归在退出条件里和在一般条件里的输出表达式是不一样的。而Pattern Mathing简化了这一分流的实现。关于Pattern Match vs Decomposition 用来扩展类的方法的好处,我们在这篇文章中讨论过。如果对于子类种类固定的父类来扩展方法,Pattern Matching 更方便;如果对于子类种类个数会增加的父类来扩展方法,则用Decompostion更灵活。下面是ScalaPattern MatchingJSON的一种实现。

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 hierachy

这些Collection子类都有一些重要的高阶函数,如mapflatMapfilterfoldLeftfoldRight等。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表达式其实是对filterflatMapmap应用的一种语法糖。

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)

  1. 还有一点需要注意的是性能问题,对于之前探索过的Set[State]Pathextend后要过滤掉回到之前State的Path。

water pouring

5. assignment

6. 总结

7 参考资料


Share Post

Twitter Google+

Shunmian

The only programmers in a position to see all the differences in power between the various languages are those who understand the most powerful one.