hangscer

函数式编程入门

2017/12/09

  scala完美结合了OOP和FP两种编程范式。对于OOP,大家都很熟悉它,比如继承、封装和多态等等耳熟能详的概念。现在来说说业界不太主流的FP编程思想中几个基本概念。

Monoid(幺半群)

  请思考下列现象:

  • 对于字符串有:"fun"+"" == ""+"fun",一个字符串加上空字符串得到本身,(("1"+"2")+"3") == ("1"+("2"+"3")),对于一系列字符串连接操作,从左算和从右算得到结果相同。
  • 对于整数有:1+0 == 0+1,一个任意数加上0得到本身,((1+2)+3) == (1+(2+3)),对于一系列数字相加,从左算和从右算,结果相同。

  以上,对于某个类型A,可以找出某二元操作op(接收两个A类型的参数,并返回A类型的结果,op(A,A)=>A),对于任意x:A,y:A,z:A,能够满足op(op(x,y),z) == op(x,op(y,z))。并且一定存在值zero:A,满足任意x:A,xzero经过op操作后等于自身,op(zero,x) == op(x,zero)。(“幺半群”中“幺”,指的是“一个单位元素zero”)。
借助scala的trait来描述这一规则:

1
2
3
4
trait Monoid[A]{
def op(x:A,y:A):A //op(op(x,y),z)==op(x,op(y,z))
def zero:A //op(x,zero)==op(zero,x)
}

  以下给出Option结合操作的Monoid实例:

1
2
3
4
5
6
7
8
9
def optionMonid[A] = new Monoid[Option[A]] {
override def op(x: Option[A], y: Option[A]): Option[A] = x.orElse(y)
override def zero: Option[A] = None
}
//测试
val m = optionMonid[Int]
import m.{op,zero}
println(op(op(Some(1), None), Some(3)) == op(Some(1), op(None, Some(3)))) //true
println(op(zero,Some(1))==op(Some(1),zero)) // true

Functor(函子)

  高中数学或者大学高数中,函数的概念是从一个集合中的任意元素,经过映射的法则变换后,总能在另一个集合中找到唯一对应的值。现在考虑以下法则:fun(i:Int):String或者Int=>String,可以理解为从由Int实例组成的集合映射到由String实例组成的集合。对于此类现象,在函数式编程中称为函子。
用scala语言描述如下:

1
2
3
trait Functor[F[_]] {
def map[A, B](fa: F[A])(f: A => B): F[B]
}

以上,F[_]理解为带任意泛型参数的容器,比如List[A]Option[A]。现在我们来实现List的Functor实例:

1
2
3
val listFunctor=new Functor[List] {
override def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
}

Monad(单子)

  Monad从中提取了重复的代码,它是一个接口,为抽象数据类型提供了完备的API。Monad是一种设计模式,多个步骤组合成一个运算,只需要传入下一步所需要的函数,整个运算就可以连续下去。

1
2
3
4
trait Monad[F[_]] extends Functor[F] { //所有的monad是functor,但是不是每一个functor都是monad
def unit[A](a: => A): F[A]
def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}

  flatMapmap等函数在scala中用于for表达式推导,将一个类型实现faltMap等函数,就可以使用for推导式编写代码。
以下是,实现了非标准库的List集合,并且完善了filterflatMapmap等接口(详细编码在这里):

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
55
56
57
58
59
60
61
62
63
64
65
66
67
trait List[+A]{
self =>
def tail = self match {
case Nil => Nil
case _ :: t => t
}
def print = {
def loop(list: List[A]): String = list match {
case Nil => "Nil"
case h :: t => s"$h :: ${loop(t)}"
}
loop(self)
}
override def toString = print
def foldRight[B](z: B)(f: (A, B) => B) = {
@tailrec
def loop(list: List[A])(z: B)(f: (A, B) => B): B = list match {
case Nil => z
case h :: t => loop(t)(f(h, z))(f)
}
loop(self)(z)(f)
}
def flatMap[B](f: A => List[B]): List[B] = self match {
case Nil => Nil
case h :: t => f(h) ++ t.flatMap(f)
}
def map[B](f: A => B) = {
@tailrec
def loop(list: List[A])(result: List[B])(f: A => B): List[B] = list match {
case Nil => result
case h :: t => loop(t)(::(f(h), result))(f)
}
loop(self)(Nil: List[B])(f).invert
}
def filter(p: A => Boolean): List[A] = {
@tailrec
def loop(list: List[A])(result: List[A])(p: A => Boolean): List[A] = list match {
case Nil => result
case h :: t => p(h) match {
case true => loop(t)(::(h, result))(p)
case false => loop(t)(result)(p)
}
}
loop(self)(Nil)(p).invert
.....
}
case class ::[+A](h: A, t: List[A]) extends List[A]
case object Nil extends List[Nothing]
object List {
def empty[A]: List[A] = Nil
def apply[A](xs: A*): List[A] = {
if (xs.isEmpty) empty[A]
else ::(xs.head, apply(xs.tail: _*))
}
}
//测试
//测试
case class Gen(int: Int, str: String)
val list :List[Gen] = for {
int <- List(22)
str <- List(int.toString)
} yield Gen(int, str)
println(list) // Gen(22,22) :: Nil
//或者 无糖版
val list2:List[Gen]=List(22)
.flatMap(i=>List(i.toString)
.flatMap(str=>List(Gen(i,str))))

  cats是基于scala语言编写的函数式编程库,优雅简约实现了包括Maybe、Monad、State、Monoid、Effect、IO、typeclass、Lazy等等基础设施,值得学习。