2008年（3）
分类：
2008-09-13 17:14:45
我们已经在本教程中学了有一段时间了，然而我们还没有真正考虑过函数式编程（functional
programming）。目前文中讲述的一系列特点——丰富的数据类型、模式匹配、类型推断、嵌套函数——这些你只能想像存在于某种“超级C”语言中。
有了这些神奇特点之后，就能让你的代码更精炼、更容易阅读并且错误更少，但但实际上它们和函数式编程的关系却不是很大。事实上我要说的观点是函数式语言如
此神奇并非是因为其函数式编程，而是因为我们长时间局限于类C语言之中，而同时编程的界限却在不断地继续扩展。所以当我们在第N次重复写struct { int type; union { ... } }的时候，ML和Haskell程序员已经可以对数据类型使用安全变体和模式匹配了。当我们还在小心翼翼地free每个我们所malloc的东西时，自从80年代就已经有能比手工编码更好的垃圾收集器了。
好吧，说完这些之后，我就可以告诉你什么是函数式编程了。
最基本的定义为（不过不是很让人明白的）：在函数式语言中，函数是第一等公民。
光说不练，难以令人理解，所以先看一个例子：
# 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则有种叫做匿名类的讨厌东西，类似于一种迟钝的、冗长的闭包。如果你了解Perl，那么你可能已经知道并正在使用Perl的闭包以及Perl的map函数，它就是我们正在讨论的东西。实际上Perl也是一个很好的函数式语言。
闭包（Closure）指携带着它们被定义所处的“环境”的函数。特别地说，一个闭包可以引用在它定义时可用的那些变量。下面我们来泛化前面的函数，使得函数可以输入任何整数列表并将每个元素乘以一个任意值n：
let multiply n list =
let f x =
n * x
in
List.map f list
;;
因此：
# multiply 2 [1; 2; 3];;
- : int list = [2; 4; 6]
# multiply 5 [1; 2; 3];;
- : int list = [5; 10; 15]
multiply中需要注意的重点是嵌套函数f。这是一个闭包。看一下f是如何使用n的值的，它并未实际作为一个明确的传递给f，f而是直接从它的环境中获取了n的值——它是multiply函数的参数，因此在其中是可用的。
听起来可能很直观，不过让我们再仔细看一下对映射的调用：List.map f list。
map是定义在List模块中的，和当前的代码并不在一起。换句话说，我们将f传递到一个“很久很久以前，在一个遥远的星系中”定义的模块。就我们所知而言，代码可以将f传递到其他模块，或者将f的引用保存在某处等待以后调用。无论怎么做，闭包都会确保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
首先，你要知道在这个方法最后调用的save函数，其第二个参数是一个函数（receiver_fn）。它再重复调用receiver_fn，将来自部件的文本片断储存起来。
现在看一下recevier_fn的定义。这个函数正是一个闭包因为它保存了一个从其环境中引入的chan的引用。
让我们定义一个将两数相加的加法函数：
let plus a b =
a + b
;;
下面给在教室后面睡觉的家伙们一些问题：
plus是什么？plus 2 3是什么？plus 2是什么？问题 1 很简单。plus是一个函数，它接受两个整数参数并返回一个整数。类型是这么写的：
plus : int -> int -> int
问题 2 就更简单了。plus 2 3是一个数字，整数5。类型是这么写的：
5 : int
但问题 3 怎么回答呢？貌似plus 2是一个错误。然而，实际上，并非如此。如果我们在OCaml的顶层输入这个表达式，那么它会告诉我们：
# plus 2;;
- : int -> int =
这不是一个错误。它告诉我们plus 2实际上是一个函数，它接受一个int并返回一个int。这是怎样的一个函数呢？首先我们给这个函数起个名字叫做（f），然后再进行一些实验，给它一些整数看看会发生什么：
# let f = plus 2;;
val f : int -> int =
# f 10;;
- : int = 12
# f 15;;
- : int = 17
# f 99;;
- : int = 101
在工程中，我们有说plus 2就是将2加上另一个数的函数。
回到原来的定义，让我们“填入”第一个参数（a）2，则获得了：
let plus 2 b = (* 这不是真正的OCaml代码! *)
2 + b
;;
我希望你可以了解为何plus 2就是一个函数。
看一下这些表达式的类型也许就能够一窥函数类型中用到的奇怪的->箭头记号的原理：
plus : int -> int -> int
plus 2 : int -> int
plus 2 3 : int
这个过程称之为currying（柯里化，也可能叫做uncurrying反 柯里化，我至今也搞不清哪个是哪个）。它之所以如此命名是为了纪念Haskell Curry，他对lambda算子做出了一些相关的重要贡献。由于我要尽可能回避在OCaml背后的数学原理——因为这十分冗长也不切主题——所以这个问 题上我就不深入了。如果你对此感兴趣，你可以通过Google搜索来查找更多关于柯里化的更多信息。
还记得我们前面的double和multiply函数吗？multiply的定义是这样的：
let multiply n list =
let f x =
n * x
in
List.map f list
;;
现在我们来定义double、triple，这些函数很好写，如下：
let double = multiply 2;;
let triple = multiply 3;;
它们其实都是函数，看：
# double [1; 2; 3];;
- : int list = [2; 4; 6]
# triple [1; 2; 3];;
- : int list = [3; 6; 9]
你也可以像这样直接使用部分应用（无需中间的f函数）
# let multiply n = List.map (( * ) n);;
val multiply : int -> int list -> int list =
# let double = multiply 2;;
val double : int list -> int list =
# let triple = multiply 3;;
val triple : int list -> int list =
# 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 =
# plus 2 3;;
- : int = 5
下面还有一些有趣的柯理化：
# 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 = [; ; ]
函数式编程，和其他的优秀编程技术一样，它也是你的锦囊中用于解决某几类问题的有效工具。对于设计回调函数——它用多种用户，从GUI到事件驱动的循环——十分方便。对于表达泛型算法也十分好用。List.map就是一个泛型算法，用于将函数应用于任何类型的列表。类似的，你还可以定义处理树的泛型函数。某几种类型的数字问题也可以利用函数式编程更快地解决（例如，用数字计算数学函数派生出来的东西）。
一个纯粹的函数是指没有任何副作用的函数。副作用其实是指函数在其内部保存某种隐藏的状态。C中，strlen是一个纯函数的很好的例子。如果你对同样的字符串多次调用strlen，它总是返回同样的长度值。strlen的输出（长度）仅由其输入（字符串）决定，不依赖于任何其他东西。但不幸的是，C中很多函数都是不纯的。例如，malloc——如果你用同样的数字对其进行调用，它肯定都不会返回同样的指针给你。malloc当然还依赖于很多隐藏的内部状态（堆上分配的对象、使用的分配方法、从操作系统抓取页，等等）。
ML派生的语言，如OCaml，是“近乎纯粹的”。它们允许通过像引用和数组这类的东西产生一些副作用，但是大部分你写出来的代码都会是纯函数式的 因为它们鼓励这种思考方式。Haskell——另一种函数式语言——则是完全纯函数式的。因为写不纯的函数有时候更加有用和有效，所以OCaml更加实用 的。
使用纯函数还有一些理论上的好处。其中一个好处是，如果某个函数是纯粹的，那么如果使用同样的参数对其调用多次的话，编译器就只需要调用该函数一次。在C中有一个很好的例子：
如果就这样编译了，那么这个循环是O(n2)因为每次都要调用strlen (s)然后strlen又需要迭代整个s。如果编译器足够聪明可以推断出strlen是一个纯函数同时s又没有在循环中更新过，那么它就可以删除冗余的strlen的调用，就能使函数变为O(n)复杂度。那么编译器真的能这么做吗？在strlen的情况下，可以，而在其他情况下，可能就不行了。
集中于写短小的纯函数可以让你使用一种自地向上的方式来构建可复用的代码，同时边继续边测试每个小函数。而当前时尚的方式是使用一种自顶向下的方式来仔细设计你的程序，不过在作者的经历中，这往往会导致项目失败。
C派生的和ML派生的语言都是严格的。Haskell和Miranda则是非严格的，或者说是惰性的。OCaml默认是严格的，不过当必须时也可以进行惰性风格的编程。
在严格语言中，给函数传递参数的时候都是先计算好的，然后把结果传递给函数。例如，在严格语言中，下面的调用肯定会导致“被零除”的错误：
give_me_a_three (1/0);;
如果你用一些常见的语言编程的话，这就是其工作的方式，如果它能以任何方式运行起来的话，你一定十分惊讶。
在一个惰性语言中，就会有一些其他奇怪的事情发生。传递给函数的参数只有当函数实际用到它们的时候才会进行计算。还记得前面give_me_a_three函数会抛弃它的参数，总是返回3么？在惰性语言中，上面的调用并不会失败，因为give_me_a_three从不会看它第一个参数，所以第一个参数并不会被计算，所以被零除并不会发生。
惰性语言还能让你做一些很古怪的事情，比如定义一个无限长的列表。前提是你不会真的去迭代整个列表，这就没问题（换句话说，比如你只要获取前10个元素）。
OCaml是一个严格语言，不过它有一个Lazy模块可以让你写一些惰性表达式。下面有一个例子。首先我们给1/0创建一个惰性表达式：
# let lazy_expr = lazy (1/0);;
val lazy_expr : int lazy_t =
注意这种惰性表达式的类型是int lazy_t。
因为give_me_a_three接受'a（任何类型）作为参数，所以我们可以将惰性表达式传递给该函数：
# give_me_a_three lazy_expr;;
- : int = 3
如果要计算一个惰性表达式，必须使用Lazy.force函数：
# Lazy.force lazy_expr;;
Exception: Division_by_zero.
装箱类型和拆箱类型
当讨论函数式语言的时候，有一个术语你会经常听到，这就是“装箱”。当我第一次听到这个术语的时候，我也很困惑，其实如果你以前用过C/C++或者Java，那么对你来说装箱类型和拆箱类型之间的区别是相当简单的（在Perl中，一切东西都是被装箱过的）。
如何去思考一个被装箱的对象呢，在C中这种对象就是使用malloc在堆上分配的（或者在C++中等同于new），同时/或者通过一个指针来引用的对象。看一下这个C程序的例子：
- #include
-
- void
- printit (int *ptr)
- {
- printf ("the number is %d\n", *ptr);
- }
-
- void
- main ()
- {
- int a = 3;
- int *p = &a;
-
- printit (p);
- }
变量a是分配在栈上的，所以肯定是被拆箱过的。
函数printit接受一个装箱过的整数并将其打印出来。
下面的图像是了一组拆箱（上部）和装箱（下部）整数之间的对比：
拆箱了的整数要比装箱了的快很多。另外，因为单独分配更少，所以对于拆箱的对象的类型垃圾收集更加快速也更加简单。
在C/C++中，你应该对构造以上两种类型的数组是没有问题的。在Java中，有两种类型，int是拆箱型的，而Integer是装箱型的，因此相对不如前者有效。在OCaml中，所有的基本类型都是拆箱型的。
