函数式编程

什么是函数式编程

到现在我们已经讲了很多了，但还没有真正涉及到函数式编程。 目前所讲的所有特性 - 丰富的数据类型（rich data types）， 模式匹配（pattern matching）， 类型推导（type inference）， 嵌套函数（nested functions） - 可以想象它们都可以在一种”超级C“语言中存在。这些特性当然很酷，它们使得代码简洁易读，减少bug，但是它们实际和函数式编程没什么关系。实际上我的 观点是函数式编程语言的妙处不是在于函数式编程，而是因为在我们长年习惯于类C语言编程的时候，编程技术已经提高很多了。因此当我们一次又一次地写struct { int type; union { ... } }的时候，ML和Haskell程序员却有着很多安全的变量和数据类型的模式匹配。当我们小心翼翼地 free所有的malloc时候，很多语言在上世纪八十年代就有了超越手工管理的内存垃圾收集器。

好了，现在是时候告诉你们什么是函数式编程了。

基本的但不是很能说明问题的定义是在函数式语言中, 函数（functions）是一等公民。

听上去不是很有用，让我们来看个例子。

# let double x = x * 2 in
  List.map double [ 1; 2; 3 ];;
- : int list = [2; 4; 6]

在这个例子中，我首先定义了一个嵌套函数double，它读入一个参数x后返回x * 2。然后map在给定的列表([1; 2; 3])的每个元素上调用double来生成结果：一个每个数都扩大一倍的新的列表。

map被称为高阶函数（higher-order function） (HOF)。高阶函数是指一个把其他函数作为参数之一的函数。

到现在为止还算简单。如果你对C/C++熟悉的，这就象传递一个函数指针作为参数。Java中有匿名类(anonymous class)就像一个低速的闭包（closure）。如果你知道Perl那么你可能已经知道和使用了Perl中的闭包和Perl的map函数，这和我们现在所说的完全相同。事实上Perl很大程度上也是一个函数式语言。

闭包是那些带着它们被定义时的环境的函数。特别的，一个闭包可以引用它定义时存在的变量。让我们把上面那个函数变得更通用一些，以便我们可以对任何整数列表乘以一个任意值n:

# let multiply n list =
    let f x =
      n * x in
    List.map f list;;
val multiply : int -> int list -> int list = <fun>

因此:

# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]

关于multiply函数有一点值得注意的是嵌套函数f. 这是一个闭包。我们注意一下f怎样使用变量n的值，我们并没有把n作为显式的参数传递给它。f是从它的环境中找到它的。n是传递给函数multiply的参数，所以在这个函数中都是有效的。

这可能听上去很简单，但让我们更进一步的仔细观察下那个对map的调用List.map f list.

map 的定义在List模块中，离当前的代码很远。也就是说，我们把f 传递到一个”很久很久以前，在一个很遥远很遥远的星系“（译者：星球大战片头）中的一个模块。 代码可以传递f给其他模块，或者把它的引用（reference）在某个地方以便之后 再调用它。不管怎样，这个闭包保证f总是可以获取它定义时的环境，比如n。

这里是一个来自lablgtk的真实的例子。实际上这是一个类方法（我们还没有谈到类和对象，暂时 可以把它看作一个函数定义。）

class html_skel obj = object (self)
  ...
  ...
  method save_to_channel chan =
    let receiver_fn content =
      output_string chan content;
      true in
    save obj receiver_fn
  ...
end

首先你要知道的是方法最后调用的save函数的第二个参数是一个函数(receiver_fn)。它带着从widget获取的文字重复调用receiver_fn函数。

现在来看receiver_fn的定义。这个函数是一个闭包，因为它含有一个引用, 这个引用指向它的环境中的chan。

偏函数应用（Partial function applications）和 currying（科里化）

让我们定义一个加法函数用来相加两个整数。

# let plus a b =
    a + b;;
val plus : int -> int -> int = <fun>

这里是给前面上课时睡着的朋友的几个问题。

1. 什么是plus?
2. 什么是plus 2 3?
3. 什么是plus 2?

问题一很简单。plus是一个函数。它有两个整数型参数并返回一个整数。我们这样来表示这个函数的类型：

plus : int -> int -> int

问题二就更简单了。plus 2 3是一个数，整数5。我们这样来表示它的类型：

5 : int

但是问题三呢？看上去plus 2是一个错误。但是实际上却不是的。如果我们在OCaml的 toplevel中输入上述代码，toplevel会显示：

# plus 2;;
- : int -> int = <fun>

这不是一个错误。它告诉我们plus 2事实上也是一个函数。它以一个整数为参数并返回一个整数。这是一个什么样的函数呢？让我们给这种神秘的函数起名为f,然后尝试把它作用在几个整数上来看它到底做什么。

# let f = plus 2;;
val f : int -> int = <fun>
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101

在工程上这已经足够proof by example让我们声明plus 2是一个给整数加2的函数。

回到原始的定义，让我们把第一个参数(a)换成2:

let plus 2 b =       (* 这不是真正的OCaml代码！ *)
  2 + b

这样我希望你或多或少的开始理解为什么plus 2是给整数加2的函数了吧。

现在来看这些表达式的类别，我们可以领悟到在函数类型中用奇怪的箭头符号->的原因了。

    plus : int -> int -> int
  plus 2 : int -> int
plus 2 3 : int

这个过程叫做currying（科里化） (或者应该叫 uncurrying（去科里化）, 我一直搞不清这两个定义).这个名字来源与Haskell Curry的与lambda calculus有关的重要发现。为了避免进入OCaml背后的数学世界而使这个教程变得过于繁琐，我将不会再进一步地说明这个主题。如果感兴趣，你可以从用 Google （译注：国内的小伙伴们可能要自行百度了）来获得更多关于currying的信息。

还记得开始时候我们的double和multiply函数吗？ multiply是这样定义的:

# let multiply n list =
    let f x =
      n * x in
    List.map f list;;
val multiply : int -> int list -> int list = <fun>

现在我们可以象这样来更简单地定义double, triple函数：

# let double = multiply 2;;
val double : int list -> int list = <fun>
# let triple = multiply 3;;
val triple : int list -> int list = <fun>

它们确实是函数, 不信你看:

# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]

你也可以不用中间函数f，而象这样来直接用部分应用（partial application）：

# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list = <fun>
# let double = multiply 2;;
val double : int list -> int list = <fun>
# let triple = multiply 3;;
val triple : int list -> int list = <fun>
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]

在上面的例子中，((*) n)是一个(*) (乘)函数的部分应用。 注意这里额外的空格，它使得OCaml不会认为(*是注释的开始。

你可以把中序操作符放在括号中而形成一个函数。这里是一个和以前plus函数等价的一个定义：

# let plus = ( + );;
val plus : int -> int -> int = <fun>
# plus 2 3;;
- : int = 5

这里是更多的一些有趣的curring：

# List.map (plus 2) [1; 2; 3];;
- : int list = [3; 4; 5]
# let list_of_functions = List.map plus [1; 2; 3];;
val list_of_functions : (int -> int) list = [<fun>; <fun>; <fun>]

函数式编程的优点

函数式编程，像其他任何优秀的编程技术一样，是你的工具箱中解决某些问题的利器。它使得callback函 数变得非常方便，可以用于从GUI编程到事件驱动循环等多种场合。它也很适合编写通用算法。List.map 就是一个把函数应用到链表中每个元素的通用算法。类似的，你也可以定义树的通用算法。另外，某些类型的 数值运算可以用函数式编程更加迅速地解决（比方说求导）。

纯函数式和非纯函数式编程

一个纯函数是没有副作用的。副作用的意思是这个函数保留了某些隐藏的状态。strlen就是 一个C的纯函数的例子。如果你调用strlen到相同的字符串，它总会返回相同的结果。strlen的输出 只依赖于输入而没有任何其他。很多C的函数是非纯的。比方说malloc，显然它不会对相同的输入返回相同的结果。 malloc内部有一个很大的数据结构记录状态，如堆的分配情况，用户接口调用情况，OS相关信息等。

ML衍生的语言，如OCaml是“几乎纯”的。它们允许引用和数组引入一定的副作用，但很大程度上 你会写纯函数，而语言本身也鼓励你这么做。另一个函数式语言Haskell是纯的（如果不考虑IO模块）。 相比，OCaml更加实用，因为非纯的函数有时候还是很有用的。

在理论上，纯函数有很多好处。其中一个就是如果一个函数是纯的，那么编译器可以把以 同样参数对该函数的多次调用消除至只剩一个（译注：gcc对其有支持，分别是attribute((pure)) 和attribute((const))，具体参见info page）。一个C的例子是:

for (i = 0; i < strlen (s); ++i)
  {
    // Do something which doesn't affect s.
  }

如果是就代码原样编译，那么这个循环的复杂度是O(n^2^)，因为strlen(s)在每个 循环都会被调用，而该调用会把s遍历一遍。如果编译器知道strlen是一个纯函数， 并且s不会被更新，它可以简单地把每个循环中的strlen调用替换成常数， 使得这个循环变成O(n)。那么编译器是否真的这么做了呢？对于strlen，是的， 对于其他函数，不见得（译注：如我之前所述，gcc的扩展可以让编译器认识纯函数， 并且做这样的优化。但是这种优化不是必然会做的，你可以通过参数-O0使得编译器 不做任何优化）。

集中注意，由底至上地写小的纯函数有助于构建可重用的代码，并且也可以随着测试。 现在流行的做法是由顶至下地计划程序，但是作者的意见是这往往会让整个项目崩盘 （译注人话：计划赶不上变化，怎么做评估都没用）。

非懒惰和懒惰

C类和ML类的语言都是非懒惰的（饥饿求值），而Haskell和Miranda都是懒惰的。OCaml是缺省非懒惰， 但是在需要的时候支持懒惰的风格。

对于一个非懒惰的语言，参数和函数总是在使用前被求值，然后再传入到函数中。比如 下面的代码会引起除零错误：

# let give_me_a_three _ = 3;;
val give_me_a_three : 'a -> int = <fun>
# give_me_a_three (1/0);;
Exception: Division_by_zero.

如果你用一些传统的语言编程，这就是这么回事，但是你可能会为事情还可以 以另一个方式发生而惊讶。

在懒惰语言中，一些奇怪的事情会发生。函数的参数只有在被使用的时候才会被求值。 give_me_a_three没有使用参数而直接返回3，因而在一个懒惰语言中，这个函数调用 不会失败，因为这个参数根本没有被求值！因此，也不会引起除零错误。

懒惰语言允许你定义无限长的链表，只要你不会真的要遍历整个链表（比方说你只要前10个元素）。

OCaml是一个非懒惰的语言，但是Lazy模块允许你写懒惰的表达式，下面就是这样一个例子：

# let lazy_expr = lazy (1/0);;
val lazy_expr : int lazy_t = <lazy>

注意到其类型是 int lazy_t。

因为give_me_a_three的输入是任何类型，所以我们也可以把这个懒惰表达式传入：

# give_me_a_three lazy_expr;;
- : int = 3

如果要求值，我们要用Lazy.force函数：

# Lazy.force lazy_expr;;
Exception: Division_by_zero.

box和unbox类型

译注：这个box实在不好翻，有人会翻作“装箱”，但这实在辞不达意。这个词的意思只可意会，因此不做翻译。 box的意思是，把一些标准数据类型，如int，用一个对象封装，而这个对象的行为如int本身无异。但是 这会损耗一定效率。

你可能会经常听到函数式语言是boxed的。我经常会混淆这个词，但实际上在C/C++, Java中， 这里的区别还是很明显的（Perl总是box的）。

一个boxed的对象就像用C中用malloc分配在了堆上（C++中则是new），并且被指针引用， 下面是一个C的例子：

#include <stdio.h>

void
printit (int *ptr)
{
  printf ("the number is %d\n", *ptr);
}

void
main ()
{
  int a = 3;
  int *p = &a;

  printit (p);
}

a是在栈上的，显然是unboxed的。

而函数printit打印一个boxed的整数。

下面的图展示了一个unboxed（上）和boxed（下）的整数：

显然操作一个unboxed的整数数组是比操作一个boxed的要快很多。并且由于上了很多 小的分块，垃圾收集也要快很多。

在C/C++，这应该不成问题，在Java中，int是unboxed而Integer是boxed的。Ocaml中， 基本类型是unboxed的。