函数式编程笔记

澄清概念

面向对象编程(OOP)对应的是面向过程编程(POP)。其区别在于模块化和如何对事物进行抽象：

POP中程序可被分解成函数，OOP中程序可被分解成对象；
POP侧重于过程及其执行顺序，OOP侧重于数据而不是过程；
POP自顶向下解决问题，OOP自底向上解决问题；
POP可以自由地在函数之间传递数据，OOP中对象需要通过成员方法传递数据和彼此通信；
OOP更容易添加新数据和函数，有POP所没有的（public、private、protected等）访问修饰符、数据隐藏、方法覆写等特性。

函数式编程(Functional Programming)对应的是命令式编程(Imperativeprogramming)。

普林斯顿的科学家阿隆左·丘奇（Alonzo Church）、阿兰·图灵（Alan Turing）、约翰·冯·诺依曼（Johnvon Neumann）和库尔特·冈特（KurtGodel）都对形式系统很感兴趣，致力于解决抽象的数学难题。这些难题的共同之处就是计算：如果计算机能有无限的计算能力，哪些问题可以被解决？哪些问题可以被自动解决？哪些问题依旧无法解决？为什么不能被解决？基于不同设计的各种计算机是否具有相同的计算能力？阿隆左·丘奇提出了一个被称为lambda演算的形式系统。这个系统本质上是一种程序设计语言。它可以运行在具有无限计算能力的机器上。lambda演算由一些函数构成，这些函数的输入输出也是函数。函数用希腊字母lambda标识，因此整个形式系统也叫lambda。通过这一形式系统，阿隆左就可以对上述诸多问题进行推理并给出结论性的答案。在同一时间，阿兰·图灵也在进行着相似的工作。他提出了一个完全不同的形式系统（现在被称为图灵机），并使用这一系统得出了和阿隆左相似的结论。事后证明，图灵机和lambda的演算能力是等价的。 1949年，第一台电子计算机EDVAC被推出并获得了巨大的成功。这是冯·诺依曼架构的第一个具体实现，实际上也是图灵机的第一个实现。而与此同时，阿隆左·丘奇则没有那么幸运。直到二十世纪五十年代，一位MIT的教授JohnMcCarthy对阿隆左·丘奇的工作产生了兴趣。1958年，他发布了Lisp语言。Lisp的不同之处在于，它在冯·诺依曼计算机上实现了阿隆左·丘奇的lambda演算！很多计算机科学家开始意识到Lisp的表达能力。1973年，MIT人工智能实验室的一帮程序员开发了被称为Lisp机器的硬件，于是阿隆左的lambda演算系统终于在硬件上实现了！函数式编程更加现代一些的例子包括scheme、Haskell、Clean、Erlang和Miranda等。1980年代末期，集函数式编程研究成果于大成的Haskell发布。命令式编程是图灵机思想的一种实现，对应地函数式编程则是lambda演算思想的一种实现。但并非所有的lambda演算都被实现了，因为lambda演算原本不是为有物理限制的计算机设计的。

定义

在维基百科中，已经对函数式编程有了很详细的介绍，其定义如下：

函数式编程或称函数程序设计，又称泛函编程，是一种编程范型，它将电脑运算视为数学上的函数计算，并且避免使用程序状态以及易变对象。函数编程语言最重要的基础是λ演算（lambda calculus）。而且λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。

概念

支持闭包和高阶函数

函数在函数式编程中是所谓的"头等公民"，函数与其他数据类型一样处于平等地位，有时称为闭包或者仿函数（functor）对象。实质上，闭包是起函数的作用并可以像对象一样操作的对象。与此类似，函数式编程语言支持高阶函数。高阶函数可以用另一个函数（间接地，用一个表达式）作为其输入参数，在某些情况下，它甚至返回一个函数作为其输出参数。这两种结构结合在一起使得可以用优雅的方式进行模块化编程，这是使用函数式编程的最大好处。

纯函数

所谓“纯”函数式(或表达式)就是实现了lambda演算并且不包含与Church范式矛盾的特性，它没有(内存或I/O)副作用。

变量的不可变性：函数式编程的变量都是不可变的，函数保持独立，不能修改外部变量的值，所有功能就是返回一个新的值。在命令式编程中，变量往往用来保存"状态"（state）,变量会影响函数的输出。在函数式编程中，不能修改变量，意味着状态不能保存在变量中。函数式编程使用函数参数保存状态，函数参数是影响函数返回值的唯一途径。如果一个编程语言中变量都是不可变的好处是：
- 可以去掉很多情况的锁操作, 并发处理速度会更快.
- 可以简化垃圾回收GC
函数的确定性或引用透明性（Referentialtransparency）：指的是函数的运行不依赖于外部变量或"状态"，只依赖于输入的参数，任何时候只要参数相同，引用函数所得到的返回值总是相同的。这使您可以从形式上推断程序行为，因为表达式的意义只取决于其子表达式而不是计算顺序或者其他表达式的副作用。这有助于验证正确性、简化算法，甚至有助于找出优化它的方法。

递归

函数式编程还有一个特点是用递归做为控制流程的机制。递归最大的好处就简化代码，他可以把一个复杂的问题用很简单的代码描述出来。注意：递归的精髓是描述问题，而这正是函数式编程的精髓。

懒惰计算

懒惰计算需要编译器的支持。表达式不是在绑定到变量时立即计算，而是在求值程序需要产生表达式的值时进行计算。延迟的计算使您可以编写可能潜在地生成无穷输出的函数。因为不会计算多于程序的其余部分所需要的值，所以不需要担心由无穷计算所导致的out-of-memory错误。一个懒惰计算的例子是生成无穷Fibonacci列表的函数，但是对第n个Fibonacci数的计算相当于只是从可能的无穷列表中提取一项。 C类和ML类的语言都是非懒惰的（饥饿求值），而Haskell和Miranda都是懒惰的。OCaml是缺省非懒惰，但是在需要的时候支持懒惰的风格。

模式匹配

模式匹配不是什么新特性。事实上它和函数式编程的关系不大。为什么总是把它当做函数式编程的一个特性呢？这是因为函数式语言已经支持模式匹配一段时间了，而现代命令式语言还不行。用一个例子来进一步了解模式匹配。下面是Java实现的斐波那契函数：

int fib(int n) {
 if(n == 0) return 1;
 if(n == 1) return 1;

 return fib(n - 2) + fib(n - 1);
}

如果用我们上文构造的并且支持模式匹配的Java来写，实现如下

int fib(0) {
 return 1;
}
 
int fib(1) {
 return 1;
}
 
int fib(int n) {
 return fib(n - 2) + fib(n - 1);
}

两者有什么区别？编译器为我们实现了分支。

科里化(currying)

把一个函数的多个参数分解成多个函数，然后把函数多层封装起来，每层函数都返回一个函数去接收下一个参数这样，可以简化函数的多个参数。这里有一个适配器模式的例子：

int pow(int i, int j);
int square(int i) {
 return pow(i, 2);
}

上面的代码把一个整数幂运算接口转换成为了一个平方接口。在学术圈中，这样的用法被称之为currying（得名于逻辑学家HaskellCurry，他曾将相关的数学理论形式化）。因为在函数式编程中，函数而不是类作为参数进行传递，因此可以用currying把函数适配到其他接口。又因为函数的接口就是其参数列表，所以currying可以减少参数的数量(如上例所示)。因为函数式语言内建了这一技术，所以不用手动地创建一个包装了原函数的类。函数式语言会为你代劳。和之前一样，我们来扩展一下我们的语言来支持这个技术：

square = int pow(int i, 2);

尾递归优化(tail call optimization)

传统地递归过程就是函数调用，涉及返回地址、函数参数、寄存器值等压栈（在x86-64上通常用寄存器保存函数参数），其缺点是

效率低，占内存
如果递归链过长，可能会堆栈溢出

与普通递归相比，由于尾递归的调用处于方法的最后，因此方法之前所积累下的各种状态对于递归调用结果已经没有任何意义，因此完全可以把本次方法中留在堆栈中的数据完全清除，把空间让给最后的递归调用。这样的优化便使得递归不会在调用堆栈上产生堆积，意味着即时是“无限”递归也不会让堆栈溢出”。这其实才是尾递归的“正统”优化方式。因为Python、Java等无法在语言中实现尾递归优化，所以采用了循环迭代等方式代替递归的表述。

总结

函数式编程在某些场景下比命令式编程具有优势。鼓吹函数式编程的人说函数式编程比命令式编程代码精简、表达直观，其实不能一概而论。此外要让函数式编程来做CRUD，来做我们传统的逻辑性很强的Web编程，就有些免为其难了。实用最好！

参考

WIKI：函数编程语言
 函数式程序设计的另类指南
 函数式编程初探
 IBM developerWorks：Java 语言中的函数编程
 MSDN: Functional Programming vs. Imperative Programming
函数式编程
 编程的宗派