函数式编程扫盲

发表于 分类于 Disqus： 本文字数： 3.4k 阅读时长 ≈ 6 分钟

名谓扫盲，实则是为自己扫盲。前些日子通过Elm的学习接触到了函数式编程的概念，发现语言风格和以C为代表的命令式编程大不相同，接触不同的编程思维还是很有助于自我提升的。在回顾的同时，这里走马观花地带过一些函数式编程的“热门词汇”。

历史故事

什么是函数式编程（Functional Programming，FP）？它从何而来？可以吃吗？这得从20世纪30年代开始讲起：

新建成的哥特式办公楼给普林斯顿大学带来一种天堂般的安全感。来自世界各地的逻辑学者应邀来到普林斯顿，他们将组建一个新的学部。正当大部分美国人还在为找不到一片面包做晚餐而发愁的时候，在普林斯顿却是这样一番景象：高高的天花板和木雕包覆的墙，每天品茶论道，漫步丛林。 一个名叫阿隆佐·邱奇(Alonzo Church)的年轻数学家就过着这样优越的生活。阿隆佐本科毕业于普林斯顿后被留在研究院。他觉得这样的生活完全没有必要，于是他鲜少出现在那些数学茶会中也不喜欢到树林里散心。阿隆佐更喜欢独处：自己一个人的时候他的工作效率更高。尽管如此他还是和普林斯顿学者保持着联系，这些人当中有艾伦·图灵、约翰·冯·诺伊曼、库尔特·哥德尔。

在与这些人的合作下，阿隆佐设计了一个名为lambda演算的形式系统。在这种语言里面，函数的参数是函数，返回值也是函数。篇幅和本人能力限制，不对lambda演算做更多讲解。

除了阿隆佐·邱奇，艾伦·图灵也在进行类似的研究。他设计了一种完全不同的系统（后来被称为图灵机），并用这种系统得出了和阿隆佐相似的答案。到了后来人们证明了图灵机和lambda演算的能力是一样的。

到了50年代末，一个叫John McCarthy的MIT教授（他也是普林斯顿的硕士）对阿隆佐的成果产生了兴趣。1958年他发明了一种列表处理语言（Lisp），这种语言是一种阿隆佐lambda演算在现实世界的实现，而且它能在冯·诺伊曼计算机上运行！而后的诸多函数式编程语言（如Haskell，ML等）也多少收到Lisp的影响。

法则

函数式编程的思想来源Lambda演算在最初设计时就是用来解决计算相关问题，它是一种相对于“命令式编程”完全不同的编程范式，后者告诉计算机怎么做，前者着眼在从数学角度描述问题。它的特点也很明显：

  • 变量不可变，即默认带上const或是final（当然函数式编程里压根没有const和final的概念）。这么来看，叫它为“符号”似乎更合适
  • 惰性求值，变量直到使用时才会真正计算它的值，因为这个特点，Haskell甚至允许无限列表的出现。同时，这也意味着语句的出现顺序和执行顺序并不相关。
  • 高阶函数，函数可以作为入参或是返回值，这个也被很多不那么OOP的语言借鉴去了
  • 无副作用，函数只负责映射数据，更像是个管道，绝不改变外部状态，同样的输入在任何时候会得到同样的输出（测试人员笑开了花）。这一点使得函数式编程语言天生支持并发执行。
  • 一切皆函数，函数是第一公民

λ演算用来描述一种形式系统，它的语法只有三条：

语法 术语 描述
a 变量 一个代表参数或数字/逻辑值的符号或字符串
(λx.M) 定义 函数定义，.前面的标识符x为入参，M为表达式
(M N) 调用 应用函数到一个入参

例如：((λ x y. x + y) 1 2)表示1和2相加。

λ演算公理只有两个：

操作 名称 描述
(λx.M[x]) → (λy.M[y]) α变换 改变入参名不影响结果
((λx.M) E) → (M[x:=E]) β规约 将入参传入λ意味着对它做演算

还以上面的相加为例，α变换就是λ x y. x + y → λ a b. a + b；β规约就是(λ x y. x + y) a b → a + b。是不是很好理解。

通过这两个基本的公理，结合基本变量类型可以构造各种函数。如not函数，and函数，or函数，甚至if函数。

1
2
3
4
5
6
7
8
let and =
true value  ->  value
false value ->  false
value true  ->  value
value false ->  false

let if =
λ cond tvalue fvalue. (cond and tvalue) or (not cond  and fvalue)

高阶函数

高阶函数意味着，我们可以把函数直接作为入参传入，或作为返回值返回。这早已不是函数式编程语言的专利，Python，JavaScript等也吸收了这个设计理念。

函数柯里化即部分求值，就利用了高阶函数的特点提出的技术，它使得函数可以一个一个接受入参，返回相同的计算结果。类似于下面的感觉：

1
2
3
4
5
6
function pow(i, j) {
  return i^j;
}
funtion square(j) {
  return pow(i, 2)
}

square函数返回的函数需要指定i才可执行。柯里的名字来自于第一次提出这个技巧的逻辑学家Haskell Curry。

另外，值得注意的是，在函数式编程下，高阶函数通过将函数作为参数惰性求值实现。那命令式编程下呢，答案是闭包（lexical closure）。

递归？

函数式编程里没有状态变量（可以用其他方式实现），因此自然没有循环结构。实际上，函数式编程中的循环都是通过递归实现的。比如，斐波那契数列函数像下面这样：

1
let fact = λ n. if (n == 0) 1 (n * fact n-1)

这里fact函数引用了自身，虽然编译器可以识别这种写法，但是显然它并不符合严格的数学公理。

重新审视这个变换，我们可以通过传入自身的方式来让它“数学化”。let P = λ self n. if (n == 0) 1 (n * self(self n-1))，然后在令let fact n = P (P n)。如此这般：

1
2
3
4
5
6
7
fact 4
-> P (P 4)
-> if (4 == 0) (1) (4 * P(P 3))
-> 4 * P(P 3)
-> 4 * 3 * P(P 2)
-> 4 * 3 * 2 * P(P 1)
-> 4 * 3 * 2 * 1

可是，这个函数看上去并不自然，不像一个真正的递归函数，且λ演算的公理里并没有这样一条公理可以让你在定义函数的时候引用本身。还好，已经有人做了研究，借助Y组合子的帮助，可以实现真正的递归函数。

1
2
let Y = λ F. G(G)
G = λ self. F(self(self))

这相当于我们在λ演算公理体系中添加了一条“可以在函数调用时引用自身”。这也是证明λ演算图灵等价的关键一步。这意味着它的计算能力和计算机是一致的，能通过λ演算描述的函数一定可以由计算机计算。

Haskell

Haskell是一个纯函数式编程语言，它得名于上面提到过的Haskell Curry。Y组合子也是他发现的。

Haskell中一切都是函数，甚至没有指令式编程中变量的概念，它的变量全部都是只允许一次赋值，不可改变。

Haskell还没有一般意义上的控制流结构，如for循环，取而代之的是递归。同样，Haskell还有两个重要的特性，即无副作用和惰
性求值。偏数学的问题，用Haskell解决通常代码量都很小。下面是一个列表去重例子

1
2
3
4
5
6
cut cond  []  = []
cut cond  (elem:rest) = if  cond elem then
cut cond  rest  else  elem:rest
compress  []  = []
compress  (elem:rest) = elem  : compress
(cut  (== elem) rest)

还有一个快排（不过借助了filter函数）的例子，也是短得不行

1
2
3
4
qsort (elem:rest) = (qsort lesser) ++ [elem] ++ (qsort greater)
  where
    lesser = filter (< elem) rest
    greater = filter (>= elem) rest

Haskell中还可以定义无穷列表，如[1..]表示所有正整数。这也是惰性求值特性带来的。[1,3..] !! 42将会返回85。

Monad

Monad其实就是自函子范畴上的一个幺半群而已

这节将展示一个图文并茂的说明但并不致力于解释清楚monad到底是个什么（因为我自己也不明白）。这篇对比functor，applicatives，monad的文章写得很透彻易懂，尽管这可能并不能描述一个100%的monad。要更深刻了解monad还是需要学习范畴论的内容。

参考

函数式编程.pdf
Functional Programming For The Rest of Us
Functors, Applicatives, And Monads In Pictures