Haskell 函数式编程体验

概述

本文通过完成一个简单的练习题（Exercise），对照在命令式编程（Imperative Programming）语言和函数式编程（Functional Programming）语言中的多种实现，在函数式编程的思维方式上给予大家一些直观的感受和体验。

前言

在学习和讨论函数式编程的时候，我曾经被问到这么一个问题：函数式编程有什么特别优秀的地方？或者说有什么事情是函数式编程可以做到而在传统命令式编程里做不到或者很难做到的？记得这个问题当时回答得很敷衍，以至于现在都想不起来那时是怎么说的。之后又经过了长时间的学习，练习和思考，到目前为止还是觉得这是一个很难回答的问题。在此我愿意记录一下现在的理解，相信这个不会是最终的答案，随着学习的深入和经验的积累，甚至于将来会有比较大的变化。首先，流行的编程语言，不管是命令式的还是函数式的都已经被证实具有非凡的表现能力，千变万化的软件系统和应用就是证据。仅仅只有几条规则的lambda演算被证明是图灵完整的（https://en.wikipedia.org/wiki...），也就是说理论上仅仅基于lambda演算就可以实现所有的智能和逻辑。有一门研究性质的编程语言叫Brain F*ck，验证了只需要6个算符（或者可以称作编程原语）就可以实现一门图灵完整的编程语言，虽然它的Hello world简直就是天书（https://en.wikipedia.org/wiki...）。因此我相信我们不可能找到什么东西是在命令式编程语言中不能实现的。区别仅在于一些问题域或是思维方式与函数式编程的方式和风格特别地契合，从而演化出直接，简明，高效的表述，显得特别有表现力。但如果我们试图在函数式编程语言里沿用命令式编程的思维方式，就会遇到很多的困难，出来的结果也将会晦涩难懂，低效易错，难于修改或扩展。

练习题目

有一种植物，一年有两个生长周期，春天高度加倍，夏天高度增加1米，秋冬季休眠。给出该植物在某个冬季的初始高度 i（米），请计算给出在 n 个生长周期后的高度。编码实现函数 f(i, n)
这是一个来自某个在线解题（Online Judge）网站的题目。题目本身非常的简单直接。使得我们不必关注于精巧的数据结构和高深的算法，从而专注于不同的思维方式。

Python 实现

def f(i, n):
    l = i
    for c in range(n):
        l = l + 1 if (c % 2) else l * 2
    return l

这里我们选择了Python来作为命令式语言的代表。Python的实现直接明了。大家可以打开Python的交互式命令环境，键入并测试这段代码。一些可能的测试结果如下：

>>> f (1, 3)
6
>>> f (2, 7)
46
>>> f (2, 2)
5
>>> f (2, 3)
10
>>> f (2, 4)
11

让我们简单分析一下代码：

1. 创建一个局部变量 l 用于存放计算的中间和最终结果。其初始值就是给定的初始值。在计算过程中，该变量的值会发生变化，始终存放当前的计算结果。在计算完成之后，其中保持的值就是最终的结果，被直接返回。
2. 使用for循环配合range产生的n个元素的列表，分步骤地计算。
3. 使用(exp) if (bool) else (exp)条件表达式根据生长周期的不同运用不同的算式。这里的条件表达式相当于C/C++/Java中的三目条件运算符?:。也可以使用条件语句（Condition statement），表述同样简洁明了。

Haskell 实现（1）

Haskell是一门基于Lambda演算的“纯粹”的函数式编程语言。Haskell里没有语句（Statement）的概念，程序是由函数定义和表达式组成。函数和数值都是其中的一等公民（First Class Citizen），可以被方便地表述（Represent）,存储（Store），传递（Pass/Transfer），使用（Use/Apply）和操纵（Manipulate）。通常的函数都是纯粹的（Pure），无副作用的（Ineffective），简单地说就是传入相同的参数，只能返回相同的结果。
以下是Haskell的一个实现：

f :: Int -> Int -> Int
f i n = foldl (\acc c -> if (odd c) then acc + 1 else acc * 2) i (take n [0,1..])

大家可以将以上代码存成一个.hs文件（Haskell源代码文件的扩展名），然后加载到ghci中测试。Ghci是Haskell的一个交互式命令环境，关于ghci安装和使用不在本文的范围内，请参见网上的其它资料。也可以在ghci里直接键入以上内容，但是不要忘记先键入一行“:{”，然后在结尾添加一行“:}”, :{和:}是ghci中用于键入多行代码必须的标识。以下是在ghci中的函数定义和测试结果：

Prelude> :{
Prelude| f :: Int -> Int -> Int
Prelude| f i n = foldl (\acc c -> if (odd c) then acc + 1 else acc * 2) i (take n [0,1..])
Prelude| :}
Prelude> f 1 3
6
Prelude> f 2 7
46
Prelude> f 2 2
5
Prelude> f 2 3
10
Prelude> f 2 4
11

我们来一步一步地解释代码：

1. 第一句f :: Int -> Int -> Int是一个函数的类型申明。可以理解为申明了一个名为f的函数，它依次接受两个类型为Int的参数，计算并返回一个Int型的值作为结果。在Haskell的函数申明里，最后的那一个->XXX可以被理解为函数的返回值的类型定义。
2. Haskell里没有循环语句，我们使用foldl函数实现可控的循环。熟悉Python/Java的程序员应该知道Python里有reduce函数，Java（>=8）中有stream.reduce，跟这里的foldl是相同的函数。foldl接受一个带两个参数的函数，一个初始的累积值，从一个列表的最左边开始将当前的累积值和列表的一个元素作为参数喂给该函数，然后将结果作为新的累积值参加下一步计算。累积值的初始值就是传入的初始累积值，当列表迭代完成时的累积值就是foldl的最终结果。例如 foldl (+) 0 [1,2,3]可以将列表中的所有整数累加起来，而foldl (*) 1 [1,2,3]则计算出列表中所有整数的乘积。
3. [0,1..]是一个无穷的序列，依次包含从0开始的所有整数。take函数从一个给定的列表中从头取出n（take的第一个参数）个元素并以列表返回。可以看到take n [0,1..]事实上构造了一个和Python中range(n)相同的序列。Haskell的惰性求值（Lazy evaluation）允许我们方便的构造无穷序列并在适当的时候合理使用。
4. (\acc c ->...)是一个lambda函数，跟Python/Java中的lambda函数类似，可以理解为在申明/定义的地方一次性使用的匿名函数。定义中‘\’标识了lammbda函数定义的开始，之后紧跟函数的参数，多个参数间以空格隔开，之后有一个‘->’，然后就是函数的实现。lambda函数跟通常的函数一样，其实现都是一个表达式，在实现中可以访问所有的参数以及包含该lambda函数的表达式中定义和可访问的名字。在这里，我们仅访问该lambda函数自己的参数。
5. Haskell中没有类似if..then..else..的条件语句。这里看到的是条件表达式，类似于上面Python代码中的条件表达式和C/C++/Java中的?:运算符。在条件表达式中then和else子表达式都不可省略，而且必须具有相同的结果类型。在这里，条件表达式实现了根据生长周期的不同而调用不同的算式。
6. 那个odd函数是一个测试（Predict）函数，顾名思义，它接受一个整数，判断其奇偶性，当参数是奇数时返回True，否则返回False。

总结一下，我们使用foldl函数实现了可控循环，使用条件表达式实现了条件分发，odd函数判断生长周期的属性（奇偶），take函数配合无穷的自然数序列构造了一个有限的序列用于循环控制。这个解法虽然工作，但是显得比较笨拙，特别是那个包含条件表达式的lambda函数。其根本原因在于我们一路秉承的命令式编程的思路，然后在函数式语言中寻找相应的结构或函数。那么在函数式编程语言中我们可以怎样更好地思考并解决这个问题呢？

Haskell 实现（2）

记得我们提到过在函数式编程语言中函数是一等公民吗？我们可以方便地表述，存储，传递并且使用函数？下面我们来构造一个函数序列来解决这个问题：

f' :: Int -> Int -> Int
f' i n = foldl (flip ($)) i (take n $ cycle [(*2), (+1)])

foldl和take函数我们之前已经了解了。 让我们来看看别的新出现的东西。

1. 首先是函数名f'，在Haskell里单引号是合法的符号字符，可以用于任何名字中，不过不能被用于名字的开头。在Haskell代码中我们经常使用f'，f''甚至是f'''来表示和f有些关系又不完全一样的定义/申明。
2. Haskell里所有的运算符其实都只是普通的函数。当我们写2 + 4时，事实上和函数调用(+) 2 4完全等价。(+1)的意思可以理解为我们使用(+)这个接受两个参数的函数，并且传入数值1，使其绑定到(+)的第二个参数上，从而生成一个新的函数，该函数接受一个参数，并在该参数上加上数值1作为计算结果。这样的函数我们称之为部分应用（Partial Applied）函数，或者更加专业一点的中文说法：偏函数。在C/C++/Python/Java这种严格求值（Strict Evaluation）的编程语言里，我们很难做到调用一个函数，只传递给它部分的参数，使其“停”在这个中间状态，等待其它参数的传入（C++的模版库里有偏函数的实现，Python也有偏函数的库，都费了老劲了，使用又不方便，写出的代码难于理解，限制还多）。而Haskell是非严格求值(Non-strict evaluation）的或者说我们之前提到过，惰性求值，这使得我们很容易绑定部分的参数到一个函数，从而形成一个新的，接受更少参数的函数。事实上函数类型上的Int -> Int -> Int，我们说过可以理解为一个函数依次接受两个Int型的参数并返回一个Int型的值作为结果，“->”其实也是一个函数（运算符），它是右结合的， 那么Int -> Int -> Int就等价于Int -> (Int -> Int)，可以看到这其实是说该函数接受一个Int类型的参数并返回一个(Int -> Int)类型的函数。回到我们的主题，这里(*2)和(+1)均是这样的偏函数，当传入一个参数并求值时，分别将参数加倍和加一。
3. cycle函数接受一个列表，把它通过循环重复的方式扩展为一个无穷序列。因此cycle [(*2), (+1)]就是这样一个无穷序列[(*2),(+1),(*2),(+1),(*2),(+1)......]
4. $是一个二目算符，它接受一个函数f和一个参数a，把a作为参数喂给函数f。f $ a等价于($) f a也等价于f a。由于$是右结合的，而且优先级最低，我们常常用它来减少括号的使用。这里的(take n $ cycle [(*2), (+1)])就等价于(take n (cycle [(*2), (+1)]))
5. 函数(flip ($))是用在foldl中的累积函数，我们需要重点解释一下。我们已经知道($)是一个二目函数，也就是一个接受两个参数的函数，它认定第一个参数是一个函数，然后把第二个参数作为参数喂给该函数并将其计算结果作为自己的计算结果。flip函数可以简单地理解为改造一个多参数的函数，翻转其第一个和第二个参数的顺序。这样(flip ($))就等价于($)的参数翻转的版本，(flip ($))认定第二个参数是一个函数，把第一个参数作为参数喂给该函数而得到结果。我们知道foldl的累积函数有两个参数，第一个是累积值（开始时就是初始值），第二个是从后面的序列中取到的元素，在这里序列中的元素是函数(*2)或者(+1)，因此我们需要累积函数将第一个参数作为参数喂给第二个参数（函数）。说起来很绕口，不过请记得关于foldl的三条规则：A)foldl的结果，给定的累积函数的返回值和给定的初始值有相同的类型 B)累积函数的第一个参数和初始值类型相同 C)累积函数的第二个参数和给定的序列中的元素有相同的类型。

总结一下：我们通过cycle [(*2), (+1)]构造了一个加倍和加一函数交替出现的无穷序列。然后用take函数依据给定的生长周期数目得到一个有限的函数序列，该序列可以看作是一个数据加工的动作序列。之后我们使用foldl函数迭代该动作序列，依次将植物的高度作为参数喂给序列中的动作并把结果作为下次动作的参数。而将作为累积值的植物高度喂给动作函数的任务则由函数(flip ($))来完成。这个解题思路就比较符合函数式编程的思维方式和风格了。那么还有没有更加酷一点的方法呢？有的！至少我觉得下面的实现（3）就还要酷炫一点。

Haskell 实现（3）

在实现（2）中我们表述（Represent）了偏函数，并且将偏函数存储（Store）在列表中，之后将这些偏函数传递（Pass/Transfer）给高阶函数（高阶函数就是能处理函数的函数）foldl和(flip ($))，最后通过高阶函数把所需的参数喂给这些偏函数，应用（Apply）了它们并最终求值（Evaluation）成功。不过似乎少了一样，说好的操纵（Manipulate）函数呢？别急，这就来：

f'' :: Int -> Int -> Int
f'' n = foldl (flip (.)) id $ take n $ cycle [(*2), (+1)]

这里除了我们的老朋友foldl，take，cycle以及偏函数(*2)，(+1)之外，有这些新的内容：

1. 大家也许注意到f''函数类型申明没有发生变化，仍然是Int -> Int -> Int，可是它的实现为什么只有一个参数f'' n而不是像之前的f和f'那样有两个参数（f i n和f' i n）呢？这是函数的参数约简在起作用。在数学上，对于两个一元函数f和g，如果对所有可能的输入参数a都有f a = g a，那么我们就说函数f等价于函数g，记为f = g。在Haskell中这条规则完全成立，不管什么时候如果有f i = g i，只要f和g中没有包含i，我们都可以安全地把参数i约去而得到f = g。所以实际上f'' n = foldl ...是由f'' n i = (foldl ...) i通过两边约掉相同的i简化得来的。那为什么参数i和n的顺序变了呢？下面我们马上会说到。
2. 这个解法的思路是我们先使用动作偏函数序列以及给定的周期数目构造一个大的all-in-one的函数，然后把给定的初始高度传给这个函数，其结果就是我们需要的最终结果。因此我们很自然地把先用到的周期数目n放到参数的第一个。那么就要求f'' n构造并返回一个函数，该函数接受一个参数，就是初始高度，计算并返回最终结果。
3. 这里我们两次使用$来减少括号的使用，可以把$都换成左括号‘(’，然后在表达式的末尾加上相应数量的右括号‘)’,得到的表达式是等价的。大家可以自行验证。
4. 这里foldl用的累积函数是(flip (.))，我们已经知道flip是做什么的。而运算符(.)是组合函数的函数。在数学中函数的组合（或者叫复合函数）可以定义为，对于函数f和g，如果f可以操作g的结果集，定义函数组合f.g，对于任何g定义域中的元素a，有(f.g) a = f (g a)。在Haskell里这被完全直接地表述为f.g，对于任何a（可以作为g的参数）有(f.g) a = f (g a). 而我们知道Haskell语法上中缀运算符可以转换为函数调用，f.g等价于(.) f g。根据运算符(.)的定义，我们可以知道在把最终参数喂给组合函数并求值的时候，第二个函数会被先应用求值，然后结果再传给第一个函数计算出结果。而foldl是从序列的左端开始折叠，在我们的动作序列中左端的动作是需要先做的，就是说我们希望在组合函数中左端的（也就是第一个参数）函数先执行求值。这就是我们用到flip的原因了。
5. 我们之前说过foldl的累积初始值的类型和折叠的结果类型要一致，这里我们要得到一个函数，该函数接受植物的初始高度，计算并返回最终高度，它的类型应该是Int -> Int。那么我们就需要一个同样类型的函数作为foldl的累积初始值。注意到这个初始函数会被组合到最后的组合函数链的尾端（也就是最内层）。如果我们为这个函数命名h的话，最后的组合函数链看起来应该像这个样子.... (+1).(*2).(+1).(*2).h。而我们并不希望这个函数会对结果有任何影响或改变，很自然地我们认定这个函数应该直接返回传给它的参数而不做任何更改，该函数的定义应该是h=\x->x。在Haskell里，预定义的id正是这么一个函数。于是我们看到id被作为foldl的累积初始值。

可以在ghci中键入并验证这个实现，注意参数n和i的顺序不同于之前的f和f'，除非你使用(flip f'')。

Prelude> :{
Prelude| f'' :: Int -> Int -> Int
Prelude| f'' n = foldl (flip (.)) id $ take n $ cycle [(*2), (+1)]
Prelude| :}
Prelude> f'' 3 1
6
Prelude> f'' 7 2
46
Prelude> f'' 2 2
5
Prelude> f'' 3 2
10
Prelude> f'' 4 2
11

总结一下：我们如方法（2）中一样构建了一个由偏函数(*2)和(+1)交替出现的动作序列。然后使用foldl和组合函数(.)将序列中的前n个元素组合（函数操纵Manipulate的一种情形）成为一个大的函数。最后该函数接受到作为参数的植物的初始高度，求值计算出结果，也就是最后的植物高度。
或者我们可以这样理解：我们在方法（3）中构建了一套逻辑/理论架构，在给定生长周期数目的时候，该理论架构发生塌缩，生成一个Int -> Int的函数，我们可以理解为规模较小的理论架构。然后当传入植物的初始高度时，这个较小的理论架构再次发生塌缩，从而计算/得到最终的结果，也就是我们想要得到的植物的最终高度。
这个理解完美地契合了函数式建模/编程的一种世界观，那就是编程就是设计和建模一个理论架构，然后当接收到外来刺激的时候，该理论架构就会发生塌缩，从而形成/产生在该刺激条件下的大家所期待的完美结果。是的，完美！