函数式编程——Think differently（1）

2017-09-14 约 3005 字预计阅读 6 分钟

0. 写在最前面

很久之前就想写一个函数式编程（Functional Programming，下文简称FP）的文章了。

最早听说函数式编程是大一下开学，看C++11标准的时候看到了一段这样的代码：

1
2
3
4
5
auto f = [](int x) {
        return x + 5;
};

f(5); // => 10

感觉很神奇，没有见过这种表达式，于是深入了解了一波。

这便一发不可收拾。

FP是一个很大的话题，内容非常深，涉及到很多计算机的底层知识，实在是大开眼界。

闭着眼睛，硬着头皮学了这么久，也觉得能得出一点东西。就写一个简短的系列，力求能简单了解FP吧。

在这个过程中，也受到了很多人的帮助，很抱歉不能一一列出，如有遗漏，请告诉我。

对了，本文可能使用很多语言来描述，但是主要的还是Python、Haskell、C++和Java。我会解释清楚必要的前置知识，力求不影响代码理解。

那么，FP之旅开始了。

1. 何为函数式？

在讨论这个问题之前，我们先看两段代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// Example 1: Recursion, Functional
int sum(int n)
{
    if (n == 1)
        return 1;
    else
        return n + sum(n - 1);
}

// Example 2: Loop, Imperative
int sum(int n)
{
    int res = 0;
    for (int i = 1; i <= n; i++)
        res += i;
    return res;
}

这两段代码干了什么呢？很简单，就是计算$S(n)=1+2+…+n$。

那么，这两段代码区别在哪儿？也很简单，就是一个是递归，一个是循环。

这里我能告诉你，第一段代码是更加函数式的写法，第二段代码是更加命令式的写法。

“这不都是C++代码吗？哪儿有函数式？你说那个什么Lambda Expession也没有啊？”

别急，让我们先来看看这二者的区别。

i.命令式编程

让我们先复习一下什么是图灵机。

图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种抽象计算模型，其更抽象的意义为一种数学逻辑机，可以看作等价于任何有限逻辑数学过程的终极强大逻辑机器。
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：
一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依次被编号为0, 1, 2, …，纸带的右端可以无限伸展。
一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。
注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

上面这一段来自维基百科。其实，说了这么多，我们可以知道，图灵机所描述的是这么一个机器：有一条纸带和一系列规则，我们根据规则读写和修改纸带上的数据。

根据图灵机，从Fortran开始，然后是Algol 60，慢慢发展到现在经久不衰的C语言等等。这一类语言我们叫做命令式语言，它们最大的特点就是描述状态的改变。

什么叫状态的改变？考虑一种最常见的数据结构，数组。假如说，我们有一个字符串，要多次修改它，我们应该怎么办？很简单，使用数组存储，然后找出对应部分进行修改。那我们把这一过程如下抽象：

定义字符串$s$，其中$s[i]$意味着访问第$i$个元素

那当我们定义出来一个字符串之后，我们执行如下操作：

读入原字符$p$以及需要修改成的目标字符$q$。
遍历字符串，若$s[i]=p$，则修改$s[i]$为$q$。

循环以上过程$k$次之后，我们得到最终的字符串$s’$。

那我问一个问题，$s’=s$成立吗？

几乎是一瞬间就能知道成立。因为我们每次都是在修改$s$，实际上的$s’$就是$s$基础上修改得到，所以$s’$和$s$就是一个字符串。

那你看，我们每一次就是把这个字符串$s$从一个状态转换到另一个状态，并在多次转换后得到最终状态$s’$。

这就是命令式编程。那么，函数式呢？

ii. 函数式编程

我们先来想一个东西。考虑如下函数应用过程： $$ y = f(x) = x + 5 $$ 当我们输入$x=7$，得到$y=f(5)=12$。在这个过程中考虑如下问题：

$x$发生了什么变化？

很直观就能看出，$x$并没有发生任何变化。

这是数学函数应用的两个重要特点：没有副作用和一一对应。所谓副作用，也就是说，不会产生外部影响，并不会因为我输入$x=2012$而引发世界毁灭。一一对应的意思是，无论在任何情况下，只要我输入$x=2012$，$y$就一定是$2017$，不会有任何变动。

那所谓函数式编程，就是在这种思想下诞生的。

什么是函数式编程呢？

函数式编程（英语：functional programming）或称函数程序设计，又称泛函编程，是一种程序设计典范，它将电脑运算视为数学上的函数计算，并且避免使用程序状态以及易变物件。函数式语言最重要的基础是λ演算（lambda演算），而λ演算的函数可以接受函数当作输入（引数）和输出（传出值）。
比起命令式程式设计，函数式程序设计更加强调程序的执行结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

你看，是不是明朗的多？其实很简单，我们可以这么考虑，还是利用上面的例子：

定义字符串$s$，其中$s[i]$意味着访问第$i$个元素

现在我们定义一个函数：

$f(s)=s_a$，其中，$s[i]=p$且$s_a[i]=q$。

那上面的过程我们可以如下描述：

读入原字符$p$以及需要修改成的目标字符$q$。
对字符串$s$应用函数$f(s)$，使用一个新字符串$s_a$接收当前结果并留作后用

那循环上述过程$k$次，可得到如下表达式： $$ s_k=f(f(…f(s)…)) $$ 那这里有一个问题，$s_k=s$成立吗？

从上面的讨论大家就知道，函数不会修改输入，每一次我们都是拿一个全新的字符串去接收应用结果，所以$s_k\ne s$。

那第二个问题很好解答，这么一个应用过程之后，我们产生了多少个新字符串？

$k$个，相信不用我再过多介绍了。

这就是函数式编程了。我们永远不修改输入，而是不断地对输出应用函数。

iii. 开头代码

那现在可以解释开头的代码了：

1
2
3
4
5
6
7
8
// Example 1: Recursion, Functional
int sum(int n)
{
    if (n == 1)
        return 1;
    else
        return n + sum(n - 1);
}

你看，对于这段代码来说，我们没有修改n，而是把n - 1作为参数传到下一个函数中，最后把所有函数的结果加起来。这其中没有任何变量修改。

而第二段：

1
2
3
4
5
6
7
8
// Example 2: Loop, Imperative
int sum(int n)
{
    int res = 0;
    for (int i = 1; i <= n; i++)
        res += i;
    return res;
}

我们用了一个变量res，每次都修改res的值，最后得到我们的结果。

下期预告

到现在，函数式和命令式的区别讲清楚了。

不过，这两段代码还能用好几节，为什么函数式我用了递归，而命令式用了循环呢？

另外，函数式这么神奇，是哪个大佬起了决定性作用？

函数式又解决了什么问题呢？

敬请期待下一期：邱奇和Lambda演算。

Changelog:
2017.9.16, V1.1: 修复排版错误，更换例子，修复示例代码

目录