跨越边界: 用 Haskell 研究函数性编程

过去 50 年中，企业所使用的语言 —— COBOL、C、C++ 和 Java 语言，都是命令式 语言；它们让您告诉您的程序如何 去完成其任务。函数性 编程语言让您告诉程序去做什么。这篇文章通过介绍 Haskell 来研究函数性编程。（如果您阅读过我的跨越边界 系列中 关于使用另外一种函数性语言 Erlang 进行并发性编程的文章，可能已经有了一定的基础。）

在我研究超越 Java（请参阅 参考资料）时，我采访的三位专家提到了 Haskell，他们认为我应该探索一下这种语言。当时，我并不认为市场已经为函数性编程做好了准备，因为这一范式对于大多数程序员来说都太陌生了。我现在仍然不认为我们已经做好了准备。但是我开始欣赏函数性语言带来的生产力和强大力量。我只是刚刚接触 Haskell，但这种语言已经影响了我使用 Java 和 Ruby 语言解决问题的方式。

命令式语言及其不足

关于本系列 在 跨越边界 系列中，作者 Bruce Tate 推动了这样一个概念：今天的 Java 程序员可以通过学习其他方式和语言受益。Java 技术曾经是编程阵营中所有开发项目的最佳选择，但这种情况已经发生了变化。其他框架正在塑造 Java 框架的构建方式，从其他语言中学到的概念有助于 Java 编程。所编写的 Python（或 Ruby、Smalltalk 或 ... 请自由填空）代码可以改变您编写 Java 代码的方式。 本系列介绍了完全不同于 Java 开发，但又直接适用于 Java 开发的编程概念和技术。在某些情况下，需要集成之后才能利用这些技术。在其他情况下，则可以直接应用这些概念。单独的工具不如其他语言和框架影响 Java 社区的开发人员、框架、甚至基本手段的这个概念重要。

命令式编程由一系列带有明确顺序的语句构成，它们的算法和编程构造严重依赖于应用程序的状态。很难想像没有这些特征的编程语言，因为命令式语言 “告诉我如何做” 的方式是如此深刻地确立在我们的日常编程哲学中。命令式编程明确塑造了您的思维方式。但通过学习替代的函数性编程工具，可以扩展您思考问题的方式。请考虑以下这些命令式结构：

• 赋值。命令式编程的用户对赋值的依赖要超过其他编程技术。函数性编程最多允许为每个变量赋值一次。改变值的赋值被叫做 破坏性赋值，是不允许的。例如，多数函数性语言不允许 x = x + 1。
  
  
• 迭代。命令式编程利用迭代来处理许多不同类型的数据结构。许多命令式控制依赖破坏性赋值进行迭代。
  
  
• 副作用。在命令式语言中，输入相同而可能返回不同值的方法，都有副作用。而对应用程序的状态变量有影响的方法也有副作用。函数性编程没有副作用。

如果以前没用过函数性语言，那么就很难想像如何编写没有破坏性赋值和副作用的应用程序。但是这些基本特征给命令性语言带来了一些更严重的问题：

• 正确性问题。有副作用的方法可能返回一个值，但同时也修改了应用程序的状态。副作用把验证程序正确的数学问题复杂化。但是复杂不仅仅是数学问题：副作用还使得测试、理解、分析和记录程序的行为更加困难。
  
  
• 基于顺序的 bug。许多优化依赖于对关键编程指令重新排序来提高性能。当依赖特定顺序的程序被重新排序时，错误就发生了。
  
  
• 并发性问题。可变状态消失时，差不多所有的并发性问题也随之消失。Brian Goetz 在 Java Concurrency in Practice（请参阅 参考资料）中，用 “这是愚蠢的可变状态“ 规则结束了第一章。

不管信还是不信，不必强行规定操作的顺序或承担副作用，也可以有效地编程。

回页首

函数性编程简介

在数学中，函数把每个输入映射到一个特定的输出。函数性编程范式使用数学函数表达程序。函数性语言并不执行命令，而是通过表示、计算数学函数来解决问题。函数性语言通常有以下两个特征：

• 不可变的数据。纯粹的函数性语言不依赖保存或检索状态的操作，因此不允许破坏性赋值。
• 无副作用。用相同的输入调用函数，总是返回相同的值。

对大多数函数性语言来说，这有点过于简化，但是只是过了一点点。函数叫做单体（monad），被用来以数学方式表达状态的变化，而 Haskell 这样的函数性语言则用单体来处理输入/输出并管理状态中的变化。

看到函数性编程的一些局限性后，您可能认为这种编程范式是一种倒退，但请继续往下阅读。函数性语言不是软弱无力的。实际上，语言专家们通常相信函数性语言操作的抽象级别要比面向对象语言高。它们提供了命令式语言通常不提供的一些工具。在这篇文章中，将看到一些工具的工作效果。

回页首

使用 Haskell

有两个 Haskell 实现值得注意：Hugs 和 Glasgow Haskell Compiler（GHC）（请参阅 参考资料）。还有许多其他 Haskell 编译器和解释器，包括 Hugs 和 GHC 的分支，但是它们是主要的两个。如果刚接触 Haskell，那么 Hugs 解释器是个不错的选择，因为它安装和理解起来都比较容易。Hugs 有两方面严重的限制：它缺乏编译器，不能使用独立函数；必须从文件装入全部函数。更严谨的程序员会采用 GHC。它的解释器略慢一些，但是它有编译器模式，还允许独立函数。在这篇文章中，我使用 Hugs，所以如果您想根据本文编写代码，也应当使用它，因为这两套软件使用的术语略有不同。

用 Hugs 编码

请下载适合您操作系统的 Hugs （请参阅 参考资料）并启动它。我把我信任的 Macbook Pro 放在一边，而用我的 Windows 机器，这是为了得到一个可以快速安装的环境。WinHugs 这个 Hugs 实现在 Windows 平台上有一个简单的一按即可的安装程序。

将看到一个带有 Hugs 提示符的解释器窗口。启动即可。输入一些数字和数学表达式，如清单 1 所示。将看到 Hugs 返回数学表达式的结果。这正是在函数性语言中期待的行为。

Haskell 98 mode: Restart with command line option -98 to enable extensions
            Type :? for help
            Hugs>5
            5
            Hugs>5+4
            9
            

Haskell 拥有强大的类型模型。语言是强类型的，这意味着您只能在类型的某个实例上完成允许的操作。（例如，如果想把数字添加到字符串上，Hugs 会报错。）Haskell 是静态类型化的，所以一旦给变量分配了值，那么变量就会一直维持相同的类型。Haskell 会做一些类型推断，这意味着它会根据程序中的语义线索来推断元素的类型，所以您会看到我在使用 有些函数时没有声明相关的类型。如果使用类型模糊不清或者在函数中使用不支持的类型，Haskell 会报错。Haskell 还有子类型，而且完全是多态的；这些特性超出了本文的范围，但如果您对此感兴趣，它们也值得研究。

既然已经看到了一些原语类型，例如整型，现在可以继续了解一些更为复杂的类型了。通常，一个语言中可用的数据结构定义了语言的使用方式。C 使用 struct、Java 使用 class。Haskell 不使用这两种数据结构。

Haskell 中最突出的三种数据结构是：tuple、列表（list） 和用户定义的类型。我将着重介绍前两种。tuple 要包含于括号 ( ) 之中，它有固定长度。tuple 包含固定类型的原语元素，甚至可以包含其他 tuple 或列表。相比之下，列表的长度可变，由同类元素构成。用 [ ] 包含列表。您可使用 Hugs 来体会 tuple 和列表，如清单 2 所示：

Hugs> [1,2]
            [1,2]
            Hugs> [1,"a"]
            ERROR - Cannot infer instance
            *** Instance   : Num [Char]
            *** Expression : [1,"a"]
            Hugs> (1,2,3)
            (1,2,3)
            Hugs> (1,"a")
            (1,"a")
            Hugs> [(1,2),(3,4)]
            [(1,2),(3,4)]
            Hugs> [(1,2),(3,4),(5,6,7)]
            ERROR - Type error in list
            *** Expression     : [(1,2),(3,4),(5,6,7)]
            *** Term           : (5,6,7)
            *** Type           : (c,d,e)
            *** Does not match : (a,b)
            

在清单 2 中，可以看到 tuple 中的每个元素可以是不同类型的，但列表中的元素必须是相同类型的。而且，如果您使用一个 tuple 列表，那么每个 tuple 的长度必须相同，每个 tuple 中的第 n 个元素必须与列表中所有其他 tuple 中的第 n 个元素匹配。

如您所料，Haskell 有许多在列表上操作的函数。最简单的就是 head 和 tail。 head 返回列表的第一个元素，tail 返回其他的元素。清单 3 显示了一些简单的列表函数：

Hugs> [1,2,3,4,5]
            [1,2,3,4,5]
            Hugs> length [1,2,3,4,5]
            5
            Hugs> head [1,2,3,4,5]
            1
            Hugs> tail [1,2,3,4,5]
            [2,3,4,5]
            

在清单 3 中，可以看到 head 返回了一个元素，tail 返回了一列元素。稍后还会看到（在 编写函数 中）这些函数如何构成了 Haskell 中众多递归函数的基础。

在构建列表时，使用 : 操作符，叫做构造（cons） 操作符（用来构造）。构建列表时，只是把元素传递给另一个列表。可以把许多构建操作串在一起。

字符串只是字符列表的语法代称而已，像 [1,2,3] 这样的列表则是 1:2:3:[] 的语法代称。这个特性使得字符串操作更容易实现。清单 4 显示了构造操作符的的工作方式以及如何用一个字符序列构建一个字符串：

Hugs> 6:[]
            [6]
            Hugs> 6:[7]
            [6,7]
            Hugs> 6:7:[]
            [6,7]
            Hugs> 'd':'o':'g':' ':'h':'a':'s':' ':'f':'l':'e':'a':'s':[]
            "dog has fleas"
            

在 Haskell 中，您会发现在字符串和列表中这种语法代称非常普遍。 但是只要记住：一切都是函数。

把函数当成数据

Haskell 允许把函数当成数据。这项重要的功能让众多的 Haskell 函数可以接受函数作为参数。这个策略让您能够用不同的方式把函数应用到函数的每个元素。清单 5 显示了一系列函数，它们把函数应用到列表的每个元素：

Hugs> :l Char
            Char> map toUpper "Hello"
            "HELLO"
            Char> filter isUpper "To Be or Not to Be"
            "TBNB"
            Char> foldr (max) 0 [1,2,3,2,1]
            3
            Char> foldr (+) 0 [1,2,3,2,1]
            9
            

:l 命令装入模块。然后可以调用 Char 模块中的函数。（其他版本的 Haskell 支持 Char.toUpper，但是 Hugs 不支持，所以要先装入模块，然后再利用模块中的函数。）第一个语句在列表的每个元素上调用函数（本例中为 toUpper，用于把字符转成大写）。因为 Haskell 的字符串就是字符列表，所以得到的是 "HELLO" 字符串。filter 函数为列表的每个元素调用一个测试函数，测试函数返回布尔值，当测试函数返回 True 时，还包含列表的元素。

fold 函数要略微复杂一些。它有两种形式：foldl 和 foldr。fold 函数接受一个函数、一个元素和一个列表。可以这样来看待 fold 函数：

1. 从列表的左侧（foldl）右侧（foldr）开始放置元素。
2. 把操作符放在列表的所有元素之间。
3. 从列表的一侧到另一侧应用操作符，对于 foldl 是从左侧开始，对于 foldr 是从右侧开始。

例如，foldr (+) 0 [1,2,3] 可归纳为 1 + (2 + (3 + 0)) 也就是 6。有些时候，顺序会有影响，这就是为什么 Haskell 既提供了 foldr（右联，从右至左构建）又提供了 foldl （左联，从左至右构建）的原因。在处理列表时，fold 函数提供了累积任何二进制计算结果的好方法。

把函数组合起来

在 Haskell 程序中，可以用许多不同的方式组合函数。用复杂的方式组合函数，是函数性语言生产力的关键，这是因为这可不断提高抽象的层次。

用复杂的方式组合函数，是函数性语言生产力的关键，这是因为这可不断提高抽象的层次。

例如，假设有一个 Java 应用程序，它计算句子中大写字母的数量。需要对列表进行迭代，每遇到一个大写字母，就要将一个本地变量加 1。在 Haskell 中，只需用 length (filter (isUpper) "To Be or Not to Be") 取得过滤列表的长度即可。Haskell 程序员就是这样避免了使用破坏性更新。每个函数都在内部保存中间结果，程序员不必考虑这类细节。

回页首

编写函数

如果您使用的是 Hugs，那么需要在独立的源文件中编写函数。WinHugs 可以很好的集成我的编辑器，所以不会造成太大的负担。应当把函数放在模块中，然后用 :l 命令装入模块。在清单 5 中已经看到，我装入了系统模块 Char。模块名称以及包含模块的文件，要用大写字母开始.函数名用小写字母开始。Haskell 程序文件的扩展名是 .hs。

可以注意到：Haskell 程序频繁地用递归来解决问题。Java 开发人员由于性能的原因和堆栈深度的限制，通常会避免递归。在处理递归时，Haskell 有两大优势：Haskell 优化了尾部递归，Haskell 是惰性的。

尾部递归优化意味着当递归发生在函数末尾时，编译器或解释器可以把递归表示成迭代。尾部递归优化没有堆栈开销，所以这个策略降低了把递归处理成简单迭代的成本。为了理解 “惰性” 的含义，请把以下函数输入名为 Generate.hs 的文件：

generate = 1:generate
            

这个函数是 1 的无穷列表。更精确地说，generate 通过构造操作符，把 1 添加到 generate —— 最初是个空列表。如果装入并执行这个函数，就会进入无穷递归循环，因为没有什么能够停止递归。但奇怪的是，可以在应用程序中使用 generate 的结果，如清单 6 所示：

Hugs> :l Generate
            Main> head generate
            1
            Main> head (tail generate)
            1
            

虽然 generate 代表 1 的无穷列表，但 Haskell 只计算列表中自己需要的部分。在清单 6 中，第一个命令装入函数，第二个得到头（或第一个）元素，第三个命令得到末尾的头（或第二个）元素。Haskell 只计算列表的头两个元素。剩下的被延迟，只在需要的时候计算。这种惰性处理的风格使得函数性语言的效率出人意料，而且支持其他编程语言中得不到的叫做无限流 的强大抽象（请参阅 参考资料）。

在大多数教程中可以发现的大多数经典 Haskell 函数都是递归的数学函数，例如 Fibonaclearcase/" target="_blank" >cci 函数和阶乘。Fibonacci 序列的定义是：由 1 和 1 开始的序列前两个数字的和。所以，Fibonacci 序列的前五个数字是 1、1、(1+1) = 2、(1+2) = 3 和 (2+3) = 5。Haskell 实现的这个序列与它的数学定义非常相似，如清单 7 所示：

fib 1 = 1
            fib 2 = 1
            fib x = fib(x-1) + fib(x-2)
            

可以把清单 7 中的代码输入到名为 Fib.hs 的文件中，用 :l fib 装入它，并输入 fib(4) 来运行它，生成序列的第四个数字。请注意，我不需要声明保存中间结果的变量。在这个示例中，可以看到更高级别抽象的示例。如果您的问题集恰好适合 Haskell，那么更高级别的抽象就适合您。如果不适合，这种更高级别的抽象将使您陷入麻烦。

可以用与 Fibonacci 序列基本相同的方式对待阶乘。x 的阶乘就是从 1 到 x 的所有数字的乘积。在 Haskell 中，可以定义一个计算阶乘的函数，如清单 8 所示：

factorial 1 = 1
            factorial x = x * factorial(x-1)
            

对列表的遍历也采用同样的工作方式。处理列表时，要处理第一个节点，然后处理列表剩下的部分（剩下的也是列表）。清单 9 显示了计算列表中所有元素之和的一个递归函数：

sum [] = 0
            sum (h:t) = h + sum(t)
            

如果您以前没见过这种模式，那么可能需要一点时间来习惯它。第一行说明空列表的和是 0。第二行代表的概念在几乎所有函数性语言中都很普遍。(h:t) 把列表表示成 tuple，列表的头（包含第一个元素）在 h 内，列表剩余的元素包含在 t 中。由于尾部递归优化，这种方式是对列表进行迭代的一种非常简单的方式。思维过程与代码的匹配非常好：做第一件事，剩下的事后面再做；什么都不剩时，就完成了。

用同样的方式也可以遍历非常复杂的数据结构。只要多付出一点功夫，就能表达 B 树 —— B 树的每个节点都容纳一个值和两个分支。用 Haskell 表示的简单 B 树形式如下：

data Tree a = Null | Node (Tree a) a (Tree a)
            

在这个示例中，data 是构建抽象类型的手段。a 是类型。它告诉 Haskell：树可以可以什么都不包含，也可以是由树构成的，树后面跟着值，后面又跟着另一个树。树中的每个节点都有一个值、一个左子节点和一个右子节点。（子节点可以是 null，也可以不为 null。）

遍历树的代码看起来与遍历列表的代码非常像。如果想要 null 树的汇总为 null，典型节点的汇总是左树的汇总加上值的汇总和右树的汇总，请看清单 10：

sum_tree :: Tree Integer -> Integer
            sum_tree Null = 0
            sum_tree (Node left val right) = sum_tree left + val + sum_tree right
            

在清单 10 中，第一行定义了函数使用的类型。 sum_tree :: Tree Integer -> Integer 意味着函数 sum_tree 要接受一个 Integer 的 Tree 作为参数，并返回 Integer。下两行代码指定函数。空树的汇总是零，其他树的汇总是左树加上 Integer 的值再加上右树的值。

现在可以把它放在 Tree.hs 中，如清单 11 所示：

data Tree a = Null | Node (Tree a) a (Tree a)
            sum_tree :: Tree Integer -> Integer
            sum_tree Null = 0
            sum_tree (Node left val right) = sum_tree left + val + sum_tree right
            t::Tree Integer
            t=Node Null 4 Null
            

在这个示例中，t::Tree Integer 把 Tree 绑定到一个类型，下一行把 t 绑定到一个值。可以用 :l Tree 把清单 11 装入 Hugs，并输入 sum_tree t。也可以表示更复杂的树，例如 Node Null 6 (Node Null 7 Null) 表示代码一个右节点的树。可以把不同的树放在 t 中，然后再次运行 sum_tree 来感受一下。（请记住，每次试验时都需要重新装入函数。）

回页首

回顾函数性 “限制”

Haskell 能够很好地处理数据结构。因为把字符串看成是字符的简单列表，所以 Haskell 不仅能很好地处理各种形式的文本，您还可以有效地处理树、复杂的数学问题以及嵌套结构。函数性语言被频繁地用来构建编译器或者解析语言的工具，因为语言通常是用语法树表示的。因为可以在数据结构中包含函数，所以函数性语言构成了元编程的优秀平台。

现在已经看到了函数性语言的基础，接下来可以开始了解，您要如何在没有副作用和对状态只有有限支持的环境下生活。正如我在前面提到过的，单体可以表示状态的变化。但是即使用了单体，管理状态也是困难的 —— 所以不要尝试这样做。相反，可以考虑通过定义不需要中间状态的复合函数来解决问题的方式。不要考虑迭代，而应使用递归或以下某个函数 —— map、filter 或 fold，它们会把表达式应用到列表的每个元素。要使用函数性语言，只需要放弃命令式编程的风格。学习用更加函数性的风格进行编程，有以下好处：

• 可以用更紧凑的方式表示思想。
• 通过避免副作用，可以限制应用程序某些类型的 bug 的影响。
• 通过减少本地变量，可以让代码更具伸缩性。

函数性语言极大地影响了编程的思考方式。多年以来，MIT 的程序员最初使用了 Lisp，因为这种语言能够有力地帮助程序员学习如何在更高层次的抽象上工作。

本文仅仅触及到了函数性语言的皮毛。我鼓励您下载 Haskell 或其他函数性语言，亲自动手去体验它。我猜，它会改造您对编程的思考方式。