函数式编程扫盲篇

问题导读

1.什么是函数式编程?
2.函数式编程的本质是什么？
3.你所了解的函数式编程有哪些语言？

1. 概论

在过去的近十年的时间里，面向对象编程大行其道。以至于在大学的教育里，老师也只会教给我们两种编程模型，面向过程和面向对象。

孰不知，在面向对象产生之前，在面向对象思想产生之前，函数式编程已经有了数十年的历史。

那么，接下来，就让我们回顾这个古老又现代的编程模型，让我们看看究竟是什么魔力将这个概念，将这个古老的概念，在21世纪的今天再次拉入了我们的视野。

2. 什么是函数式编程

在维基百科中，已经对函数式编程有了很详细的介绍。

那我们就来摘取一下Wiki上对Functional Programming的定义：

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

简单地翻译一下，也就是说函数式编程是一种编程模型，他将计算机运算看做是数学中函数的计算，并且避免了状态以及变量的概念。

接下来，我们就来剖析下函数式编程的一些特征。

3. 从并发说开来

说来惭愧，我第一个真正接触到函数式编程，要追溯到两年以前的《Erlang程序设计》，我们知道Erlang是一个支持高并发，有着强大容错性的函数式编程语言。

因为时间太久了，而且一直没有过真正地应用，所以对Erlang也只是停留在一些感性认识上。在我眼里，Erlang对高并发的支持体现在两方面，第一，Erlang对轻量级进程的支持（请注意此处进程并不等于操作系统的进程，而只是Erlang内部的一个单位单元），第二，就是变量的不变性。

4. 变量的不变性

在《Erlang程序设计》一书中，对变量的不变性是这样说的，Erlang是目前唯一变量不变性的语言。具体的话我记不清了，我不知道是老爷子就是这么写的，还是译者的问题。我在给这本书写书评的时候吹毛求疵地说：

我对这句话有异议，切不说曾经的Lisp，再到如今的F#都对赋值操作另眼相看，低人一等。单说如今的Java和C#，提供的final和readonly一样可以支持变量的不变性，而这个唯一未免显得有点太孤傲了些。

让我们先来看两段程序，首先是我们常见的一种包含赋值的程序：

[mw_shl_code=python,true]class Account:
    def __init__(self,balance):
        self.balance = balance
    def desposit(self,amount):
        self.balance = self.balance + amount
        return self.balance
    def despositTwice(self):
        self.balance = self.balance * 2
        return self.balance
if __name__ == '__main__':
    account = Account(100)
    print(account.desposit(10))
    print(account.despositTwice())[/mw_shl_code]

这段程序本身是没有问题的，但是我们考虑这样一种情况，现在有多个进程在同时跑这一个程序，那么程序就会被先desposit 还是先 despositTwice所影响。

但是如果我们采用这样的方式：

[mw_shl_code=python,true]def makeAccount(balance):
    global desposit
    global despositTwice
    def desposit(amount):
        result = balance + amount
        return result
    def despositTwice():
        result = balance * 2
        return result
    def dispatch(method):
        return eval(method)
    return dispatch
if __name__ == '__main__':
    handler = makeAccount(100)
    print(handler('desposit')(10))
    print(handler('despositTwice')())[/mw_shl_code]

这时我们就会发现，无论多少个进程在跑，因为我们本身没有赋值操作，所以都不会影响到我们的最终结果。

但是这样也像大家看到的一样，采用这样的方式没有办法保持状态。

这也就是我们在之前概念中看到的无状态性。

5. 再看函数式编程的崛起

既然已经看完了函数式编程的基本特征，那就让我们来想想数十年后函数式编程再次崛起的幕后原因。

一直以来，作为函数式编程代表的Lisp，还是Haskell，更多地都是在大学中，在实验室中应用，而很少真的应用到真实的生产环境。

先让我们再来回顾一下伟大的摩尔定律：

1、集成电路芯片上所集成的电路的数目，每隔18个月就翻一番。

2、微处理器的性能每隔18个月提高一倍，而价格下降一半。

3、用一个美元所能买到的电脑性能，每隔18个月翻两番。

一如摩尔的预测，整个信息产业就这样飞速地向前发展着，但是在近年，我们却可以发现摩尔定律逐渐地失效了，芯片上元件的尺寸是不可能无限地缩小的，这就意味着芯片上所能集成的电子元件的数量一定会在某个时刻达到一个极限。那么当技术达到这个极限时，我们又该如何适应日益增长的计算需求，电子元件厂商给出了答案，就是多核。

多核并行程序设计就这样被推到了前线，而命令式编程天生的缺陷却使并行编程模型变得非常复杂，无论是信号量，还是锁的概念，都使程序员不堪其重。

就这样，函数式编程终于在数十年后，终于走出实验室，来到了真实的生产环境中，无论是冷门的Haskell，Erlang，还是Scala，F#，都是函数式编程成功的典型。

6. 函数式编程的第一型

我们知道，对象是面向对象的第一型，那么函数式编程也是一样，函数是函数式编程的第一型。

我们在函数式编程中努力用函数来表达所有的概念，完成所有的操作。

在面向对象编程中，我们把对象传来传去，那在函数式编程中，我们要做的是把函数传来传去，而这个，说成术语，我们把他叫做高阶函数。

那我们就来看一个高阶函数的应用，熟悉js的同学应该对下面的代码很熟悉，让哦我们来写一个在电子电路中常用的滤波器的示例代码。

[mw_shl_code=python,true]def Filt(arr,func):
    result = []
    for item in arr:
        result.append(func(item))
    return result
def MyFilter(ele):
    if ele < 0 :
        return 0
    return ele
if __name__ == '__main__':
    arr = [-5,3,5,11,-45,32]
    print('%s' % (Filt(arr,MyFilter)))[/mw_shl_code]

哦，之前忘记了说，什么叫做高阶函数，我们给出定义：

在数学和计算机科学中，高阶函数是至少满足下列一个条件的函数:

接受一个或多个函数作为输入
输出一个函数

那么，毫无疑问上面的滤波器，就是高阶函数的一种应用。

在函数式编程中，函数是基本单位，是第一型，他几乎被用作一切，包括最简单的计算，甚至连变量都被计算所取代。在函数式编程中，变量只是一个名称，而不是一个存储单元，这是函数式编程与传统的命令式编程最典型的不同之处。

让我们看看，变量只是一个名称，在上面的代码中，我们可以这样重写主函数：

[mw_shl_code=python,true]if __name__ == '__main__':
    arr = [-5,3,5,11,-45,32]
    func = MyFilter
    print('%s' % (Filt(arr,func)))[/mw_shl_code]

当然，我们还可以把程序更精简一些，利用函数式编程中的利器，map,filter和reduce :

[mw_shl_code=python,true]if __name__ == '__main__':
    arr = [-5,3,5,11,-45,32]
    print('%s' % (map(lambda x : 0 if x<0 else x ,arr)))[/mw_shl_code]

这样看上去是不是更赏心悦目呢？

这样我们就看到了，函数是我们编程的基本单位。

7. 函数式编程的数学本质

忘了是谁说过：一切问题，归根结底到最后都是数学问题。

编程从来都不是难事儿，无非是细心，加上一些函数类库的熟悉程度，加上经验的堆积，而真正困难的，是如何把一个实际问题，转换成一个数学模型。这也是为什么微软，Google之类的公司重视算法，这也是为什么数学建模大赛在大学计算机系如此被看重的原因。

先假设我们已经凭借我们良好的数学思维和逻辑思维建立好了数学模型，那么接下来要做的是如何把数学语言来表达成计算机能看懂的程序语言。

这里我们再看在第四节中，我们提到的赋值模型，同一个函数，同一个参数，却会在不同的场景下计算出不同的结果，这是在数学函数中完全不可能出现的情况，f(x) = y ，那么这个函数无论在什么场景下，都会得到同样的结果，这个我们称之为函数的确定性。

这也是赋值模型与数学模型的不兼容之处。而函数式编程取消了赋值模型，则使数学模型与编程模型完美地达成了统一。

8. 函数式编程的抽象本质

相信每个程序员都对抽象这个概念不陌生。

在面向对象编程中，我们说，类是现实事物的一种抽象表示。那么抽象的最大作用在我看来就在于抽象事物的重用性，一个事物越具体，那么他的可重用性就越低，因此，我们再打造可重用性代码，类，类库时，其实在做的本质工作就在于提高代码的抽象性。而再往大了说开来，程序员做的工作，就是把一系列过程抽象开来，反映成一个通用过程，然后用代码表示出来。

在面向对象中，我们把事物抽象。而在函数式编程中，我们则是在将函数方法抽象，第六节的滤波器已经让我们知道，函数一样是可重用，可置换的抽象单位。

那么我们说函数式编程的抽象本质则是将函数也作为一个抽象单位，而反映成代码形式，则是高阶函数。

9.状态到底怎么办

我们说了一大堆函数式编程的特点，但是我们忽略了，这些都是在理想的层面，我们回头想想第四节的变量不变性，确实，我们说，函数式编程是无状态的，可是在我们现实情况中，状态不可能一直保持不变，而状态必然需要改变，传递，那么我们在函数式编程中的则是将其保存在函数的参数中，作为函数的附属品来传递。

ps：在Erlang中，进程之间的交互传递变量是靠“信箱”的收发信件来实现，其实我们想一想，从本质而言，也是将变量作为一个附属品来传递么！

我们来看个例子，我们在这里举一个求x的n次方的例子，我们用传统的命令式编程来写一下：

[mw_shl_code=python,true]def expr(x,n):
    result = 1
    for i in range(1,n+1):
        result = result * x
    return result
if __name__ == '__main__':
    print(expr(2,5))[/mw_shl_code]

这里，我们一直在对result变量赋值，但是我们知道，在函数式编程中的变量是具有不变性的，那么我们为了保持result的状态，就需要将result作为函数参数来传递以保持状态：

[mw_shl_code=python,true]def expr(num,n):
    if n==0:
        return 1
    return num*expr(num,n-1)
if __name__ == '__main__':
    print(expr(2,5))[/mw_shl_code]

呦，这不是递归么！

10. 函数式编程和递归

递归是函数式编程的一个重要的概念，循环可以没有，但是递归对于函数式编程却是不可或缺的。

在这里，我得承认，我确实不知道我该怎么解释递归为什么对函数式编程那么重要。我能想到的只是递归充分地发挥了函数的威力，也解决了函数式编程无状态的问题。（如果大家有其他的意见，请赐教）

递归其实就是将大问题无限地分解，直到问题足够小。

而递归与循环在编程模型和思维模型上最大的区别则在于：

循环是在描述我们该如何地去解决问题。

递归是在描述这个问题的定义。

那么就让我们以斐波那契数列为例来看下这两种编程模型。

先说我们最常见的递归模型，这里，我不采用动态规划来做临时状态的缓存，只是说这种思路：

[mw_shl_code=python,true]def Fib(a):
    if a==0 or a==1:
        return 1
    else:
        return Fib(a-2)+Fib(a-1)[/mw_shl_code]

递归是在描述什么是斐波那契数列，这个数列的定义就是一个数等于他的前两项的和，并且已知Fib(0)和Fib(1)等于1。而程序则是用计算机语言来把这个定义重新描述了一次。

那接下来，我们看下循环模型：

[mw_shl_code=python,true]def Fib(n):
    a=1
    b=1
    n = n - 1
    while n>0:
        temp=a
        a=a+b
        b=temp
        n = n-1
    return b
[/mw_shl_code]

这里则是在描述我们该如何求解斐波那契数列，应该先怎么样再怎么样。

而我们明显可以看到，递归相比于循环，具有着更加良好的可读性。

但是，我们也不能忽略，递归而产生的StackOverflow，而赋值模型呢？我们懂的，函数式编程不能赋值，那么怎么办？

11.  尾递归，伪递归

我们之前说到了递归和循环各自的问题，那怎么来解决这个问题，函数式编程为我们抛出了答案，尾递归。

什么是尾递归，用最通俗的话说：就是在最后一部单纯地去调用递归函数，这里我们要注意“单纯”这个字眼。

那么我们说下尾递归的原理，其实尾递归就是不要保持当前递归函数的状态，而把需要保持的东西全部用参数给传到下一个函数里，这样就可以自动清空本次调用的栈空间。这样的话，占用的栈空间就是常数阶的了。

在看尾递归代码之前，我们还是先来明确一下递归的分类，我们将递归分成“树形递归”和“尾递归”，什么是树形递归，就是把计算过程逐一展开，最后形成的是一棵树状的结构，比如之前的斐波那契数列的递归解法。

那么我们来看下斐波那契尾递归的写法：

[mw_shl_code=python,true]def Fib(a,b,n):
    if n==0:
        return b
    else:
        return Fib(b,a+b,n-1)[/mw_shl_code]

这里看上去有些难以理解，我们来解释一下：传入的a和b分别是前两个数，那么每次我都推进一位，那么b就变成了第一个数，而a+b就变成的第二个数。

这就是尾递归。其实我们想一想，这不是在描述问题，而是在寻找一种问题的解决方案，和上面的循环有什么区别呢？我们来做一个从尾递归到循环的转换把！

最后返回b是把，那我就先声明了，b=0

要传入a是把，我也声明了，a=1

要计算到n==0是把，还是循环while n!=0

每一次都要做一个那样的计算是吧，我用临时变量交换一下。temp=b ; b=a+b;a=temp。

那么按照这个思路一步步转换下去，是不是就是我们在上面写的那段循环代码呢？

那么这个尾递归，其实本质上就是个“伪递归”，您说呢？

既然我们可以优化，对于大多数的函数式编程语言的编译器来说，他们对尾递归同样提供了优化，使尾递归可以优化成循环迭代的形式，使其不会造成堆栈溢出的情况。

12. 惰性求值与并行

第一次接触到惰性求值这个概念应该是在Haskell语言中，看一个最简单的惰性求值，我觉得也是最经典的例子：

在Haskell里，有个repeat关键字，他的作用是返回一个无限长的List，那么我们来看下：

take 10 (repeat 1)  

就是这句代码，如果没有了惰性求值，我想这个进程一定会死在那里，可是结果却是很正常，返回了长度为10的List，List里的值都是1。这就是惰性求值的典型案例。

我们看这样一段简单的代码：

[mw_shl_code=python,true]def getResult():
    a = getA()   //Take a long time
    b = getB()   //Take a long time
    c = a + b[/mw_shl_code]

这段代码本身很简单，在命令式程序设计中，编译器（或解释器）会做的就是逐一解释代码，按顺序求出a和b的值，然后再求出c。

可是我们从并行的角度考虑，求a的值是不是可以和求b的值并行呢？也就是说，直到执行到a+b的时候我们编译器才意识到a和b直到现在才需要，那么我们双核处理器就自然去发挥去最大的功效去计算了呢！

这才是惰性求值的最大威力。

当然，惰性求值有着这样的优点也必然有着缺点，我记得我看过一个例子是最经典的：

[mw_shl_code=python,true]def Test():
    print('Please enter a number:')
    a = raw_input()[/mw_shl_code]

可是这段代码如果惰性求值的话，第一句话就不见得会在第二句话之前执行了。

13. 函数式编程总览

我们看完了函数式编程的特点，我们想想函数式编程的应用场合。

1. 数学推理

2. 并行程序

那么我们总体地说，其实函数式编程最适合地还是解决局部性的数学小问题，要让函数式编程来做CRUD，来做我们传统的逻辑性很强的Web编程，就有些免为其难了。

就像如果要用Scala完全取代今天的Java的工作，我想恐怕效果会很糟糕。而让Scala来负责底层服务的编写，恐怕再合适不过了。

而在一种语言中融入多种语言范式，最典型的C#。在C# 3.0中引入Lambda表达式，在C# 4.0中引入声明式编程，我们某些人在嘲笑C#越来越臃肿的同时，却忽略了，这样的语法糖，带给我们的不仅仅是代码书写上的遍历，更重要的是编程思维的一种进步。

好吧，那就让我们忘记那些C#中Lambda背后的实现机制，在C#中，还是在那些更纯粹地支持函数式编程的语言中，尽情地去体验函数式编程带给我们的快乐把！

函数式编程，其实是吸取的我们小学数学中的函数表达式，可以连续的表达
比如（1+1）×2=4
面向对象和过程是这样的
1+1=2
2×2=4

给楼主补充一些：

诞生50多年之后，函数式编程（functional programming）开始获得越来越多的关注。

不仅最古老的函数式语言Lisp重获青春，而且新的函数式语言层出不穷，比如Erlang、clojure、Scala、F#等等。目前最当红的Python、Ruby、Javascript，对函数式编程的支持都很强，就连老牌的面向对象的Java、面向过程的PHP，都忙不迭地加入对匿名函数的支持。越来越多的迹象表明，函数式编程已经不再是学术界的最爱，开始大踏步地在业界投入实用。

也许继"面向对象编程"之后，"函数式编程"会成为下一个编程的主流范式（paradigm）。未来的程序员恐怕或多或少都必须懂一点。

但是，"函数式编程"看上去比较难，缺乏通俗的入门教程，各种介绍文章都充斥着数学符号和专用术语，让人读了如坠云雾。就连最基本的问题"什么是函数式编程"，网上都搜不到易懂的回答。

下面是我的"函数式编程"学习笔记，分享出来，与大家一起探讨。内容不涉及数学（我也不懂Lambda Calculus），也不涉及高级特性（比如lazy evaluation和currying），只求尽量简单通俗地整理和表达，我现在所理解的"函数式编程"以及它的意义。

我主要参考了Slava Akhmechet的"Functional Programming For The Rest of Us"。

一、定义

简单说，"函数式编程"是一种"编程范式"（programming paradigm），也就是如何编写程序的方法论。

它属于"结构化编程"的一种，主要思想是把运算过程尽量写成一系列嵌套的函数调用。举例来说，现在有这样一个数学表达式：

　　(1 + 2) * 3 - 4

传统的过程式编程，可能这样写：

　　var a = 1 + 2;

　　var b = a * 3;

　　var c = b - 4;

函数式编程要求使用函数，我们可以把运算过程定义为不同的函数，然后写成下面这样：

　　var result = subtract(multiply(add(1,2), 3), 4);

这就是函数式编程。

二、特点

函数式编程具有五个鲜明的特点。

1. 函数是"第一等公民"

所谓"第一等公民"（first class），指的是函数与其他数据类型一样，处于平等地位，可以赋值给其他变量，也可以作为参数，传入另一个函数，或者作为别的函数的返回值。

举例来说，下面代码中的print变量就是一个函数，可以作为另一个函数的参数。

　　var print = function(i){ console.log(i);};

　　[1,2,3].forEach(print);

2. 只用"表达式"，不用"语句"

"表达式"（expression）是一个单纯的运算过程，总是有返回值；"语句"（statement）是执行某种操作，没有返回值。函数式编程要求，只使用表达式，不使用语句。也就是说，每一步都是单纯的运算，而且都有返回值。

原因是函数式编程的开发动机，一开始就是为了处理运算（computation），不考虑系统的读写（I/O）。"语句"属于对系统的读写操作，所以就被排斥在外。

当然，实际应用中，不做I/O是不可能的。因此，编程过程中，函数式编程只要求把I/O限制到最小，不要有不必要的读写行为，保持计算过程的单纯性。

3. 没有"副作用"

所谓"副作用"（side effect），指的是函数内部与外部互动（最典型的情况，就是修改全局变量的值），产生运算以外的其他结果。

函数式编程强调没有"副作用"，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。

4. 不修改状态

上一点已经提到，函数式编程只是返回新的值，不修改系统变量。因此，不修改变量，也是它的一个重要特点。

在其他类型的语言中，变量往往用来保存"状态"（state）。不修改变量，意味着状态不能保存在变量中。函数式编程使用参数保存状态，最好的例子就是递归。下面的代码是一个将字符串逆序排列的函数，它演示了不同的参数如何决定了运算所处的"状态"。

　　function reverse(string) {

　　　　if(string.length == 0) {

　　　　　　return string;

　　　　} else {

　　　　　　return reverse(string.substring(1, string.length)) + string.substring(0, 1);

　　　　}

　　}

由于使用了递归，函数式语言的运行速度比较慢，这是它长期不能在业界推广的主要原因。

5. 引用透明

引用透明（Referential transparency），指的是函数的运行不依赖于外部变量或"状态"，只依赖于输入的参数，任何时候只要参数相同，引用函数所得到的返回值总是相同的。

有了前面的第三点和第四点，这点是很显然的。其他类型的语言，函数的返回值往往与系统状态有关，不同的状态之下，返回值是不一样的。这就叫"引用不透明"，很不利于观察和理解程序的行为。

三、意义

函数式编程到底有什么好处，为什么会变得越来越流行？

1. 代码简洁，开发快速

函数式编程大量使用函数，减少了代码的重复，因此程序比较短，开发速度较快。

Paul Graham在《黑客与画家》一书中写道：同样功能的程序，极端情况下，Lisp代码的长度可能是C代码的二十分之一。

如果程序员每天所写的代码行数基本相同，这就意味着，"C语言需要一年时间完成开发某个功能，Lisp语言只需要不到三星期。反过来说，如果某个新功能，Lisp语言完成开发需要三个月，C语言需要写五年。"当然，这样的对比故意夸大了差异，但是"在一个高度竞争的市场中，即使开发速度只相差两三倍，也足以使得你永远处在落后的位置。"

2. 接近自然语言，易于理解

函数式编程的自由度很高，可以写出很接近自然语言的代码。

前文曾经将表达式(1 + 2) * 3 - 4，写成函数式语言：

　　subtract(multiply(add(1,2), 3), 4)

对它进行变形，不难得到另一种写法：

　　add(1,2).multiply(3).subtract(4)

这基本就是自然语言的表达了。再看下面的代码，大家应该一眼就能明白它的意思吧：

　　merge([1,2],[3,4]).sort().search("2")

因此，函数式编程的代码更容易理解。

3. 更方便的代码管理

函数式编程不依赖、也不会改变外界的状态，只要给定输入参数，返回的结果必定相同。因此，每一个函数都可以被看做独立单元，很有利于进行单元测试（unit testing）和除错（debugging），以及模块化组合。

4. 易于"并发编程"

函数式编程不需要考虑"死锁"（deadlock），因为它不修改变量，所以根本不存在"锁"线程的问题。不必担心一个线程的数据，被另一个线程修改，所以可以很放心地把工作分摊到多个线程，部署"并发编程"（concurrency）。

请看下面的代码：

　　var s1 = Op1();

　　var s2 = Op2();

　　var s3 = concat(s1, s2);

由于s1和s2互不干扰，不会修改变量，谁先执行是无所谓的，所以可以放心地增加线程，把它们分配在两个线程上完成。其他类型的语言就做不到这一点，因为s1可能会修改系统状态，而s2可能会用到这些状态，所以必须保证s2在s1之后运行，自然也就不能部署到其他线程上了。

多核CPU是将来的潮流，所以函数式编程的这个特性非常重要。

5. 代码的热升级

函数式编程没有副作用，只要保证接口不变，内部实现是外部无关的。所以，可以在运行状态下直接升级代码，不需要重启，也不需要停机。Erlang语言早就证明了这一点，它是瑞典爱立信公司为了管理电话系统而开发的，电话系统的升级当然是不能停机的。

赞一个……

nice 感谢分享

深入浅出的典范

写的很好，谢谢楼主分享。      

楼主好人