第 4 章：函数式编程

使用 Haskell 思考

初学 Haskell 的人需要迈过两个难关：

首先，我们需要将自己的编程观念从命令式语言转换到函数式语言上面来。这样做的原因并不是因为命令式语言不好，而是因为比起命令式语言，函数式语言更胜一筹。

其次，我们需要熟悉 Haskell 的标准库。和其他语言一样，函数库可以像杠杆那样，极大地提升我们解决问题的能力。因为 Haskell 是一门层次非常高的语言，而 Haskell 的标准库也趋向于处理高层次的抽象，因此对 Haskell 标准库的学习也稍微更难一些，但这些努力最终都会物有所值。

这一章会介绍一些常用的函数式编程技术，以及一些 Haskell 特性。还会在命令式语言和函数式语言之间进行对比，帮助读者了解它们之间的区别，并且在这个过程中，陆续介绍一些基本的 Haskell 标准库。

一个简单的命令行程序

在本章的大部分时间里，我们都只和无副作用的代码打交道。为了将注意力集中在实际的代码上，我们需要开发一个接口程序，连接起带副作用的代码和无副作用的代码。

这个接口程序读入一个文件，将函数应用到文件，并且将结果写到另一个文件：

  1. -- file: ch04/InteractWith.hs
  2.  
  3. import System.Environment (getArgs)
  4.  
  5. interactWith function inputFile outputFile = do
  6.   input <- readFile inputFile
  7.   writeFile outputFile (function input)
  8.  
  9. main = mainWith myFunction
  10.   where mainWith function = do
  11.           args <- getArgs
  12.           case args of
  13.             [input,output] -> interactWith function input output
  14.             _ -> putStrLn "error: exactly two arguments needed"
  15.  
  16.         -- replace "id" with the name of our function below
  17.         myFunction = id

这是一个简单但完整的文件处理程序。其中 do 关键字引入一个块，标识那些带有副作用的代码，比如对文件进行读和写操作。被 do 包围的 <- 操作符效果等同于赋值。第七章还会介绍更多 I/O 方面的函数。

当我们需要测试其他函数的时候，我们就将程序中的 id 换成其他函数的名字。另外，这些被测试的函数的类型包含 String -> String ，也即是，这些函数应该都接受并返回字符串值。

[译注： id 函数接受一个值，并原封不动地返回这个值，比如 id "hello" 返回值 "hello" ，而 id 10 返回值 10 。]

[译注：这一段最后一句的原文是“ … need to have the type String -> String … ” ，因为 Haskell 是一种带有类型多态的语言，所以将“ have the type ” 翻译成 “ 包含 xx 类型 ”，而不是 “ 必须是 xx 类型 ”。

接下来编译这个程序：

  1. $ ghc --make InteractWith
  2. [1 of 1] Compiling Main             ( InteractWith.hs, InteractWith.o )
  3. Linking InteractWith ...

通过命令行运行这个程序。它接受两个文件名作为参数输入，一个用于读取，一个用于写入：

  1. $ echo "hello world" > hello-in.txt
  2.  
  3. $ ./InteractWith hello-in.txt hello-out.txt
  4.  
  5. $ cat hello-in.txt
  6. hello world
  7.  
  8. $ cat hello-out.txt
  9. hello world

[译注：原书这里的执行过程少了写入内容到 hello-in.txt 的一步，导致执行会出错，所以这里加上 echo … 这一步。另外原书执行的是 Interact 过程，也是错误的，正确的执行文件名应该是 InteractWith 。]

热身： 方便地分离多行文本

Haskell提供一个内建函数，lines，让我们在行边界上分离一段文本字符串。它返回一个忽略了行终止字符的字符串列表。

  1. ghci> :type lines
  2. lines :: String -> [String]
  3. ghci> lines "line 1\nline 2"
  4. ["line 1","line 2"]
  5. ghci> lines "foo\n\nbar\n"
  6. ["foo","","bar"]

尽管lines看上去有用，但它要工作的话仰赖于我们用“文本模式”去读一个文件。文本模式对于很多编程语言来说是一个很普遍的功能：当我们在Windows系统上读和写文件的时候它提供一个特别的行为。当我们用文本模式读取一个文件的时候，文件I/O库把行终止序列“\r\n”（回车后跟着一个换行）转换成“\n”（单独一个换行），当我们写一个文件的时候，它（译注：文件I/O库）会做相反的事情。而在类Unix系统上，文本模式不会做任何的转换工作。这个不同之处会导致的结果是，如果我们在Windows系统上读取一个在类Unix系统上写入的文件，行终止符很可能会变得乱七八糟。（readFile和writeFile都在文本模式下操作的话）

  1. ghci> lines "a\r\nb"
  2. ["a\r","b"]

lines函数仅仅在换行符处分离文本，留下回车跟在行的结尾处。如果我们在Linux或Unix上读取一个Windows生成的文本文件，我们将在每一行的结尾处得到尾随的回车。

我们舒适地用了Python提供的“通用换行”支持很长时间了：它透明地为我们处理Unix和Windows的行终止惯例。我们也想要用Haskell提供类似的支持。

因为到目前为止我们仅仅接触了少量的Haskell代码，所以我们将一步一步地讨论我们用Haskell实现上述支持的细节。

  1. -- file: ch04/SplitLines.hs
  2. splitLines :: String -> [String]

我们的函数类型签名标示它接受一个字符串，可能是具有某些未知的行终止惯例的文件的内容。它返回一个包含字符串的列表，列表的每一项代表文件中的每一行文本。

  1. -- file: ch04/SplitLines.hs
  2. splitLines [] = []
  3. splitLines cs =
  4.     let (pre, suf) = break isLineTerminator cs
  5.     in  pre : case suf of
  6.                 ('\r':'\n':rest) -> splitLines rest
  7.                 ('\r':rest)      -> splitLines rest
  8.                 ('\n':rest)      -> splitLines rest
  9.                 _                -> []
  10.  
  11. isLineTerminator c = c == '\r' || c == '\n'

在我们深入细节之前，首先注意我们是怎么组织我们的代码的。我们首先呈现重要的代码片段，而把isLineTerminator函数的定义放在后面。因为我们给了这个辅助函数一个易读的名称，所以即使在我们读它的定义之前我们就能知道它是做什么用的。

Prelude定义了一个叫做break的函数，我们可以用它把一个列表分成两部分。它把一个函数作为它的第一个参数。这个函数必须去检查列表中的元素，并且返回一个Bool值来表示列表是否在那个元素处被一分为二。break函数返回一个对值（译注：即二元组），由一个谓词（译注：即一个返回Bool值的函数，下同）返回True（译注：第一次返回True）之前的元素构成的列表（前缀）和剩下的元素构成的列表组成（后缀）。

  1. ghci> break odd [2,4,5,6,8]
  2. ([2,4],[5,6,8])
  3. ghci> :module +Data.Char
  4. ghci> break isUpper "isUpper"
  5. ("is","Upper")

因为我们一次只需要匹配单个的回车或换行，所以每次检查列表中的一个元素正是我们所需要的。

splitLines的第一个算式标示如果我们匹配到一个空的字符串，我们就没有进一步的工作可做了。

在第二个算式中，我们首先对输入的字符串应用break。前缀就是第一个行终止符之前的子字符串，后缀就是整个字符串余下的部分。这个后缀将包含可能存在的行终止符。

“pre :”表达式告诉我们应该在这个代表文本行的列表的头部加上pre所表示的值。然后我们用一个case表达式去检查后缀，我们来决定下一步做什么。case表达式的结果将被用作(:)函数的的二个参数来构造结果列表。

case表达式中的第一个模式匹配以一个回车紧接着一个换行符开始的字符串。变量rest被绑定到这个字符串余下的部分。其它的模式是相似的，因此它们应当容易理解。

以上对Haskell函数的散文式的描述不一定是容易理解的。我们可以借助ghci，观察不同情况下这个函数的行为，以获得更好的理解。

让我们从分割一个不包含任何行终止符的字符串开始。

  1. ghci> splitLines "foo"
  2. ["foo"]

这里，我们的break没找到一个行终止符，所以它返回的后缀是空的。

  1. ghci> break isLineTerminator "foo"
  2. ("foo","")

因此在splitLines函数中的case表达式一定是匹配上了第四个分支，然后完成了求值。 再来一点儿更有趣的例子怎么样？

  1. ghci> splitLines "foo\r\nbar"
  2. ["foo","bar"]

首先我们的break给我们一个非空的后缀。

  1. ghci> break isLineTerminator "foo\r\nbar"
  2. ("foo","\r\nbar")

因为这个后缀以一个回车紧接着一个换行符开始，我们匹配上了case表达式的第一个分支。这个求值结果让我们把pre绑定到“foo”，suf绑定到“bar”。我们递归地应用splitLines，这一次匹配上单独的“bar”。

  1. ghci> splitLines "bar"
  2. ["bar"]

结果是我们构造了一个头部的元素是“foo”，尾部的元素是“bar”的列表

  1. ghci> "foo" : ["bar"]
  2. ["foo","bar"]

这种在ghci中的实验是一种有效的理解和调试一段代码的行为的方法。它甚至有一个更重要的好处就是非刻意的（译注：不是特别理解这句话在原英文语境中的意思，暂且按照网页中的批注直译过来，原句：It has an even more important benefit that is almost accidental in nature.）。从ghci测试复杂的代码是困难的，所以我们将倾向于写更小的函数。这能更进一步改善我们的代码的可读性。

这种创建和复用小的、强大的代码片段的方式是函数式编程的基础。

一个行终止转换程序

让我们把我们的splitLines函数和早先我们写的一个小框架联系起来。首先制作一份Interact.hs源文件的拷贝；让我们叫这个新文件FixLines.hs。把splitLines加到新的源码文件中。因为我们的函数必须产出一个单独的字符串，所以我们必须把这个表示行的列表拼接起来。Prelude提供一个unlines函数，它把一个字符串组成的列表串联起来，并且在每个字符串元素的末尾加上一个换行符。（译注：原文中代码注释命名有误，不是 SplitLines.hs 而是 FixLines.hs）

  1. -- file: ch04/FixLines.hs
  2. fixLines :: String -> String
  3. fixLines input = unlines (splitLines input)

如果我们用fixLines替换这个id函数（译注：是指拷贝自Interact.hs的FixLines.hs中的id函数），我们可以把FixLines.hs编译成一个将文本文件的行终止转换成系统特定的行终止的可执行程序。

  1. $ ghc --make FixLines
  2. [1 of 1] Compiling Main             ( FixLines.hs, FixLines.o )
  3. Linking FixLines ...

如果你在一个Windows系统上面，找到并下载一个在Unix系统上创建的文本文件（比如 gpl-3.0.txt）。在记事本程序中打开它。里面的文本行应该都跑一起去了，导致它几乎不可读。用刚才你编译得到的FixLines命令处理这个文件，然后在记事本程序中打开此命令输出的文件。现在这个行终止符的问题应该被修正了。

在类Unix的系统上，编辑器隐藏了Windows的行终止符。使得验证FixLines是否消除了它们更加困难。这里有一些命令应该能帮助你。

  1. $ file gpl-3.0.txt
  2. gpl-3.0.txt: ASCII English text
  3. $ unix2dos gpl-3.0.txt
  4. unix2dos: converting file gpl-3.0.txt to DOS format ...
  5. $ file gpl-3.0.txt
  6. gpl-3.0.txt: ASCII English text, with CRLF line terminators

中缀函数

通常，当我们在Haskell中定义和应用一个函数的时候，我们写这个函数的名称，紧接着它的参数。这种表示法作为前缀被提及，因为这个函数的名称位于它的参数前面。

如果一个函数或构造器带两个或更多的参数，我们可以选择使用中缀形式，即我们把函数（名称）放在它的第一个和第二个参数之间。这允许我们把函数作为中缀操作符来使用。

要用中缀表示法定义或应用一个函数或值构造器，我们用重音符（有时被称为反引号）包围它的名称。这里有简单的中缀函数和中缀类型的定义。

  1. -- file: ch04/Plus.hs
  2. a `plus` b = a + b
  3.  
  4. data a `Pair` b = a `Pair` b
  5.                   deriving (Show)
  6.  
  7. -- we can use the constructor either prefix or infix
  8. foo = Pair 1 2
  9. bar = True `Pair` "quux"

因为中缀表示法纯粹是为了语法上的便利，因此它不会改变函数的行为。

  1. ghci> 1 `plus` 2
  2. 3
  3. ghci> plus 1 2
  4. 3
  5. ghci> True `Pair` "something"
  6. True `Pair` "something"
  7. ghci> Pair True "something"
  8. True `Pair` "something"

中缀表示法经常对代码可读性有帮助。比如，Prelude定义了一个elem函数，它标示一个给定的值是否出现在一个列表中。如果我们用前缀表示法来使用elem，它构成的代码相当易读。

  1. ghci> elem 'a' "camogie"
  2. True

如果我们换用中缀表示法，这段代码甚至会变得更容易理解。它清楚地标示我们正在检查左边的给定值是否出现在右边的列表里。

  1. ghci> 3 `elem` [1,2,4,8]
  2. False

我们在Data.List模块的一些有用的函数中看到了更明显的改进（译注：这里是指中缀表示法改进了代码可读性）。isPrefixOf函数告诉我们一个列表是否匹配另一个列表的开始部分。

  1. ghci> :module +Data.List
  2. ghci> "foo" `isPrefixOf` "foobar"
  3. True

相应地，isInfixOf和isSuffixOf函数匹配一个列表的中间和结尾处的任何地方。

  1. ghci> "needle" `isInfixOf` "haystack full of needle thingies"
  2. True
  3. ghci> "end" `isSuffixOf` "the end"
  4. True

没有一个硬性的规则指示你什么时候应该用中缀表示法或是前缀表示法，尽管使用前缀表示法要普遍得多。在具体情况下选择使你的代码更可读的那一种表示法就是最好的。

和列表打交道

作为函数式编程的基本组件，列表应该得到足够的重视。Prelude定义了很多函数来处理列表。它们当中的许多是不可或缺的工具，所以及早学习它们是很重要的。

不管怎样，这一节将学习很多函数。为什么要马上展示这么多函数？因为这些函数既容易学而且会经常使用。如果我们不知道有这样的工具箱，那么时间将浪费在编写那些在标准库中已经存在的简单函数上。因此深入学习列表模块中的函数是非常值得的。

Data.List模块包含所有的列表函数。Prelude只不过重新导出了这些在Data.List模块中的函数的大部分。还有一些有用的函数并没有被Prelude重新导出。下面学习列表函数的时候，将明确地提到那些只在Data.List中出现的。

  1. ghci> :module +Data.List

因为这些函数没有什么复杂的或者代码量超过三行的，所有我们对它们只做简单的描述。实际上，快速和有用的学习方法是记住它们是如何定义的。

基本的列表操作

length函数告诉我们一个列表中包含多少个元素。

  1. ghci> :type length
  2. length :: [a] -> Int
  3. ghci> length []
  4. 0
  5. ghci> length [1,2,3]
  6. 3
  7. ghci> length "strings are lists, too"
  8. 22

如果需要检查列表是不是空的，用null函数。

  1. ghci> :type null
  2. null :: [a] -> Bool
  3. ghci> null []
  4. True
  5. ghci> null "plugh"
  6. False

要访问列表的第一个元素，用head函数。

  1. ghci> :type head
  2. head :: [a] -> a
  3. ghci> head [1,2,3]
  4. 1

相反，tail函数，返回列表中除了第一个其它所有的元素。

  1. ghci> :type tail
  2. tail :: [a] -> [a]
  3. ghci> tail "foo"
  4. "oo"

还有一个函数，last，返回列表的最后一个元素。

  1. ghci> :type last
  2. last :: [a] -> a
  3. ghci> last "bar"
  4. 'r'

和last相反的是init，它返回列表中除了最后一个其它所有的元素。

  1. ghci> :type init
  2. init :: [a] -> [a]
  3. ghci> init "bar"
  4. "ba"

上面的一些函数应用在空列表上时会报错，因此当不知道一个列表是否为空的时候要小心了。它们会报告什么样的错误呢？

  1. ghci> head []
  2. *** Exception: Prelude.head: empty list

在ghci里试一试上面的每一个函数，看看哪些应用在空列表上时会崩溃？

安全和明智地跟会崩溃的函数打交道

当我们想使用一个函数比如head时，如果我们传递一个空列表给它，很可能会破坏我们的工作，有效避免这个问题的方法是在使用head之前，检查传递给它的列表的长度。让我们举一个例子说明。

  1. -- file: ch04/EfficientList.hs
  2. myDumbExample xs = if length xs > 0
  3.                    then head xs
  4.                    else 'Z'

如果用过像Perl或者Python这样的编程语言，这段代码看起来就是一种很自然地编写测试的方式。在底层，Python和Perl中的列表都是数组。所以它们必定能通过调用len(foo)或者是scalar(@foo)得知列表（数组）的长度。但是基于很多别的原因，把这些假设照搬到Haskell中不是一个好主意。

我们已经看过列表的数据类型定义好多次了，知道一个列表不会明确地存储它本身的长度。因此length函数的工作方式是遍历整个列表。

所以当我们只关心一个列表是不是为空时，调用length不是一个好的策略。如果我们处理的是一个有限的列表，它潜在地做了比我们想象的更多的事情。因为Haskell很容易创建无限列表，所以不小心使用了length函数可能导致无限循环。

一个更合适的替代方案是调用null函数，它执行的次数是确定不变的。更好的是，使用null能使我们的代码明确地标示出我们真正关心的列表的属性。下面举两个更好的例子。

  1. -- file: ch04/EfficientList.hs
  2. mySmartExample xs = if not (null xs)
  3.                     then head xs
  4.                     else 'Z'
  5.  
  6. myOtherExample (x:_) = x
  7. myOtherExample [] = 'Z'

部分函数和全函数

如果一个函数只为合法输入的一个子集定义了返回值（函数返回的调用过程中产生的错误不属于返回值），这样的函数称作 部分函数（partial function）。类似的，对于整个输入域都能返回一个合法结果的函数，我们称之为 全函数（total function）。[译注：全函数是部分函数的特殊形式]

你应当了解你正在调用的函数是否为部分函数。对于部分函数而言，传入一个其无法处理的参数将导致错误，这也是Haskell程序能够简单明了避免错误的最主要的原因。[译注：为部分函数提供一个全函数的版本可能会导致问题处理层次的上浮，例如head函数在参数为空列表时抛出错误，如果我们定义safeHead函数对于空列表同样返回空列表，那么对于head函数所处的上一级函数，必须判断head函数返回的结果究竟是一个列表还是列表中的元素。]

有些使用Haskell的程序员会为部分函数加上unsafe的前缀，防止某些时候避免搬起石头砸自己的脚。标准的 prelude 定义了许多“不安全”的部分函数（例如head），却没有提供等价的“安全”的全函数，这可以说是标准 prelude 的不足。[译注：此处存在争议，有人认为“不安全”的前缀指的是该函数可能会突破类型系统的限制，比如 unsafePerformIO，unsafeCoerce 等，它们可能会导致程序完全不可预知的行为，这与在空列表上调用head有很大的区别]

更多简单列表操作

Haskell用(++)表示“追加”函数。

  1. ghci> :type (++)
  2. (++) :: [a] -> [a] -> [a]
  3. ghci> "foo" ++ "bar"
  4. "foobar"
  5. ghci> [] ++ [1,2,3]
  6. [1,2,3]
  7. ghci> [True] ++ []
  8. [True]

concat函数取一个包含列表的列表，这些列表中的元素具有相同的类型，它把这些列表连接在一起成为一个单一的列表。

  1. ghci> :type concat
  2. concat :: [[a]] -> [a]
  3. ghci> concat [[1,2,3], [4,5,6]]
  4. [1,2,3,4,5,6]

它会去掉一级的嵌套。（译注：每次调用concat会去除最外一层的方括号）

  1. ghci> concat [[[1,2],[3]], [[4],[5],[6]]]
  2. [[1,2],[3],[4],[5],[6]]
  3. ghci> concat (concat [[[1,2],[3]], [[4],[5],[6]]])
  4. [1,2,3,4,5,6]

reverse函数返回一个元素以相反的顺序排列的新列表。

  1. ghci> :type reverse
  2. reverse :: [a] -> [a]
  3. ghci> reverse "foo"
  4. "oof"

针对包含Bool值的列表，and和or函数相当于用&&和||遍历这个列表并两两求值

  1. ghci> :type and
  2. and :: [Bool] -> Bool
  3. ghci> and [True,False,True]
  4. False
  5. ghci> and []
  6. True
  7. ghci> :type or
  8. or :: [Bool] -> Bool
  9. ghci> or [False,False,False,True,False]
  10. True
  11. ghci> or []
  12. False

还有两个与and和or功能近似的函数，all和any，它们操作任何类型的列表。每一个带着一个谓词作为它的第一个参数；如果谓词对列表中的每个元素的判断都为真，all函数返回True，当对列表中的每个元素的谓词至少有一个成功了，any函数返回True。

  1. ghci> :type all
  2. all :: (a -> Bool) -> [a] -> Bool
  3. ghci> all odd [1,3,5]
  4. True
  5. ghci> all odd [3,1,4,1,5,9,2,6,5]
  6. False
  7. ghci> all odd []
  8. True
  9. ghci> :type any
  10. any :: (a -> Bool) -> [a] -> Bool
  11. ghci> any even [3,1,4,1,5,9,2,6,5]
  12. True
  13. ghci> any even []
  14. False

产生子列表

take函数，在“函数应用”一节遇到过，返回一个由头k个元素组成的子列表。与它相反，drop，丢掉列表开头的k个元素。

  1. ghci> :type take
  2. take :: Int -> [a] -> [a]
  3. ghci> take 3 "foobar"
  4. "foo"
  5. ghci> take 2 [1]
  6. [1]
  7. ghci> :type drop
  8. drop :: Int -> [a] -> [a]
  9. ghci> drop 3 "xyzzy"
  10. "zy"
  11. ghci> drop 1 []
  12. []

splitAt函数组合了take和drop的功能，返回由一个列表产生的二元组，两部分是由原来的列表根据给定的索引分割而成。

  1. ghci> :type splitAt
  2. splitAt :: Int -> [a] -> ([a], [a])
  3. ghci> splitAt 3 "foobar"
  4. ("foo","bar")

takeWhile和dropWhile函数带着谓词：takeWhile从开头遍历一个列表，抽取使谓词返回True的元素组成一个新列表；dropWhile则是把使谓词返回True的元素丢掉。（译注：这里的表述容易引起歧义，实际上两个函数都是走到第一个使谓词返回False的元素处就停止操作了，即使这个元素后面还有使谓词返回True的元素，两个函数也不再take或drop了）

  1. ghci> :type takeWhile
  2. takeWhile :: (a -> Bool) -> [a] -> [a]
  3. ghci> takeWhile odd [1,3,5,6,8,9,11]
  4. [1,3,5]
  5. ghci> :type dropWhile
  6. dropWhile :: (a -> Bool) -> [a] -> [a]
  7. ghci> dropWhile even [2,4,6,7,9,10,12]
  8. [7,9,10,12]

正如splitAt函数利用take和drop的结果组成一个二元组一样，break（已经在“热身：方便地分离多行文本”一节中看到过）和span函数利用takeWhile和dropWhile的结果组成二元组。

每个函数带着一个谓词，break提取列表中使谓词失败的元素组成二元组的首项，而span提取列表中使谓词成功的元素组成二元组的首项。

  1. ghci> :type span
  2. span :: (a -> Bool) -> [a] -> ([a], [a])
  3. ghci> span even [2,4,6,7,9,10,11]
  4. ([2,4,6],[7,9,10,11])
  5. ghci> :type break
  6. break :: (a -> Bool) -> [a] -> ([a], [a])
  7. ghci> break even [1,3,5,6,8,9,10]
  8. ([1,3,5],[6,8,9,10])

搜索列表

正如我们已经看到的，elem函数标示一个值是否出现在一个列表中。它有一个伴生的函数，notElem。

  1. ghci> :type elem
  2. elem :: (Eq a) => a -> [a] -> Bool
  3. ghci> 2 `elem` [5,3,2,1,1]
  4. True
  5. ghci> 2 `notElem` [5,3,2,1,1]
  6. False

对于更普遍的搜索操作，filter函数带着一个谓词，返回列表中使谓词成功的每一个元素。

  1. ghci> :type filter
  2. filter :: (a -> Bool) -> [a] -> [a]
  3. ghci> filter odd [2,4,1,3,6,8,5,7]
  4. [1,3,5,7]

在Data.List模块中，有三个谓词方法，isPrefixOf、isInfixOf和isSuffixOf，能让我们测试一下子列表在一个更大的列表中出现的位置。最容易的方式是把它们作为中缀使用。

isPrefixOf函数告诉我们左边的列表是否出现在右边的列表的开始处。

  1. ghci> :module +Data.List
  2. ghci> :type isPrefixOf
  3. isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
  4. ghci> "foo" `isPrefixOf` "foobar"
  5. True
  6. ghci> [1,2] `isPrefixOf` []
  7. False

isInfixOf函数标示左边的列表是否是右边的列表的一个子列表。

  1. ghci> :module +Data.List
  2. ghci> [2,6] `isInfixOf` [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
  3. True
  4. ghci> "funk" `isInfixOf` "sonic youth"
  5. False

isSuffixOf函数的功能不再赘述。

  1. ghci> :module +Data.List
  2. ghci> ".c" `isSuffixOf` "crashme.c"
  3. True

一次性处理多个列表

zip函数把两个列表压缩成一个单一的由二元组组成的列表。结果列表和被处理的两个列表中较短的那个等长。（译注：言下之意是较长的那个列表中的多出来的元素会被丢弃）

  1. ghci> :type zip
  2. zip :: [a] -> [b] -> [(a, b)]
  3. ghci> zip [12,72,93] "zippity"
  4. [(12,'z'),(72,'i'),(93,'p')]

更有用的是zipWith函数，它带两个列表作为参数并为从每个列表中抽取一个元素而组成的二元组提供一个函数，最后生成与较短的那个列表等长的新列表。

  1. ghci> :type zipWith
  2. zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
  3. ghci> zipWith (+) [1,2,3] [4,5,6]
  4. [5,7,9]

Haskell的类型系统使编写带有可变数量的参数的函数成为一个有趣的挑战。（译注：不知道此句和后面的内容有什么联系）。所以如果想把三个列表压缩在一起，要调用zip3或者zipWith3，可以类推到zip7和zipWith7。

特殊的字符串处理函数

我们已经在“热身：方便地分离多行文本”一节中遇到过lines函数，它有个对应的函数，unlines。注意unlines总是在它处理的结果（译注：列表中的每个元素）的尾部放一个换行符。

  1. ghci> lines "foo\nbar"
  2. ["foo","bar"]
  3. ghci> unlines ["foo", "bar"]
  4. "foo\nbar\n"

words函数利用任何空白字符分割一个字符串，它对应的函数，unwords，用一个空格字符把一个字符串构成的列表连接起来。

  1. ghci> words "the  \r  quick \t  brown\n\n\nfox"
  2. ["the","quick","brown","fox"]
  3. ghci> unwords ["jumps", "over", "the", "lazy", "dog"]
  4. "jumps over the lazy dog"

练习题

  • 自己写一些安全的列表函数，确保它们不会出错。下面给一些类型定义的提示。 
  1. -- file: ch04/ch04.exercises.hs
  2. safeHead :: [a] -> Maybe a
  3. safeTail :: [a] -> Maybe [a]
  4. safeLast :: [a] -> Maybe a
  5. safeInit :: [a] -> Maybe [a]
  • 写一个和words功能近似的函数splitWith，要求带一个谓词和一个任意类型元素组成的列表，在使谓词返回False的元素处分割这个列表。 
  1. -- file: ch04/ch04.exercises.hs
  2. splitWith :: (a -> Bool) -> [a] -> [[a]]
  • 利用在“一个简单的命令行框架”一节中创建的命令行框架，编写一个打印输入数据的每一行的第一个单词的程序。
  • 编写一个转置一个文件中的文本的程序。比如，它应该把“hello\nworld\n”转换成“hw\neo\nlr\nll\nod\n”。

循环的表示

和传统编程语言不同， Haskell 既没有 for 循环，也没有 while 循环。那么，如果有一大堆数据要处理，该用什么代替这些循环呢？这一节就会给出这个问题的几种可能的解决办法。

显式递归

通过例子进行比对，可以很直观地认识有 loop 语言和没 loop 语言之间的区别。以下是一个 C 函数，它将字符串表示的数字转换成整数：

  1. int as_int(char *str)
  2. {
  3.     int acc; // accumulate the partial result
  4.     for (acc = 0; isdigit(*str); str++){
  5.         acc = acc * 10 + (*str -'0');
  6.     }
  7.  
  8. return acc;
  9. }

既然 Haskell 没有 loop 的话，以上这段 C 语言代码，在 Haskell 里该怎么表达呢？

让我们先从类型签名开始写起，这不是必须的，但它对于弄清楚代码在干什么很有帮助：

  1. -- file: ch04/IntParse.hs
  2. import Data.Char (digitToInt) -- we'll need ord shortly
  3.  
  4. asInt :: String -> Int

C 代码在遍历字符串的过程中，渐增地计算结果。Haskell 代码同样可以做到这一点，而且，在 Haskell 里，使用函数已经足以表示 loop 计算了。[译注：在命令式语言里，很多迭代计算都是通过特殊关键字来实现的，比如 do 、 while 和 for 。]

  1. -- file: ch04/IntParse.hs
  2. loop :: Int -> String -> Int
  3.  
  4. asInt xs = loop 0 xs

loop 的第一个参数是累积器的变量，给它赋值 0 等同于 C 语言在 for 循环开始前的初始化操作。

在研究详细的代码前，先来思考一下我们要处理的数据：输入 xs 是一个包含数字的字符串，而 String 类型不过是 [Char] 的别名，一个包含字符的列表。因此，要遍历处理字符串，最好的方法是将它看作是列表来处理：它要么就是一个空字符串；要么就是一个字符，后面跟着列表的其余部分。

以上的想法可以通过对列表的构造器进行模式匹配来表达。先从最简单的情况 —— 输入为空字符串开始：

  1. -- file: ch04/IntParse.hs
  2. loop acc [] = acc

一个空列表并不仅仅意味着“输入列表为空”，另一种可能的情况是，对一个非空字符串进行遍历之后，最终到达了列表的末尾。因此，对于空列表，我们不是抛出错误，而是将累积值返回。

另一个等式处理列表不为空的情况：先取出并处理列表的当前元素，接着处理列表的其他元素。

  1. -- file: ch04/IntParse.hs
  2. loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
  3.                   in loop acc' xs

程序先计算出当前字符所代表的数值，将它赋值给局部变量 acc' 。然后使用 acc' 和剩余列表的元素 xs 作为参数，再次调用 loop 函数。这种调用等同于在 C 代码中再次执行一次循环。

每次递归调用 loop ，累积器的值都会被更新，并处理掉列表里的一个元素。这样一直下去，最终输入列表为空，递归调用结束。

以下是 IntParse 函数的完整定义：

  1. -- file: ch04/IntParse.hs
  2.  
  3. -- 只载入 Data.Char 中的 digitToInt 函数
  4. import Data.Char (digitToInt)
  5.  
  6. asInt xs = loop 0 xs
  7.  
  8. loop :: Int -> String -> Int
  9. loop acc [] = acc
  10. loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
  11.                   in loop acc' xs

[译注：书本原来的代码少了对 Data.Char 的引用，会造成 digitToInt 查找失败。]

在 ghci 里看看程序的表现如何：

  1. Prelude> :load IntParse.hs
  2. [1 of 1] Compiling Main             ( IntParse.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> asInt "33"
  6. 33

在处理字符串表示的字符时，它运行得很好。不过，如果传给它一些不合法的输入，这个可怜的函数就没办法处理了：

  1. *Main> asInt ""
  2. 0
  3. *Main> asInt "potato"
  4. *** Exception: Char.digitToInt: not a digit 'p'

在练习一，我们会想办法解决这个问题。

loop 函数是尾递归函数的一个例子：如果输入非空，这个函数做的最后一件事，就是递归地调用自身。这个代码还展示了另一个惯用法：通过研究列表的结构，分别处理空列表和非空列表两种状况，这种方法称之为结构递归（structural recursion）。

非递归情形（列表为空）被称为“基本情形”（有时也叫终止情形）。当对函数进行递归调用时，计算最终会回到基本情形上。在数学上，这也称为“归纳情形”。

作为一项有用的技术，结构递归并不仅仅局限于列表，它也适用于其他代数数据类型，稍后就会介绍更多这方面的例子。

对列表元素进行转换

考虑以下 C 函数， square ，它对数组中的所有元素执行平方计算：

  1. void square(double *out, const double *in, size_t length)
  2. {
  3.     for (size_t i = 0; i < length; i++) {
  4.         out[i] = in[i] * in[i];
  5.     }
  6. }

这段代码展示了一个直观且常见的 loop 动作，它对输入数组中的所有元素执行同样的动作。以下是 Haskell 版本的 square 函数：

  1. -- file: ch04/square.hs
  2.  
  3. square :: [Double] -> [Double]
  4.  
  5. square (x:xs) = x*x : square xs
  6. square []     = []

square 函数包含两个模式匹配等式。第一个模式解构一个列表，取出它的 head 部分和 tail 部分，并对第一个元素进行加倍操作，然后将计算所得的新元素放进列表里面。一直这样做下去，直到处理完整个列表为止。第二个等式确保计算会在列表为空时顺利终止。

square 产生一个和输入列表一样长的新列表，其中每个新元素的值都是原本元素的平方：

  1. Prelude> :load square.hs
  2. [1 of 1] Compiling Main             ( square.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> let one_to_ten = [1.0 .. 10.0]
  6.  
  7. *Main> square one_to_ten
  8. [1.0,4.0,9.0,16.0,25.0,36.0,49.0,64.0,81.0,100.0]

以下是另一个 C 循环，它将字符串中的所有字母都设置为大写：

  1. #include <ctype.h>
  2.  
  3. char *uppercase(const char *in)
  4. {
  5.     char *out = strdup(in);
  6.  
  7.     if (out != NULL) {
  8.         for (size_t i = 0; out[i] != '\0'; i++) {
  9.             out[i] = toupper(out[i]);
  10.         }
  11.     }
  12.  
  13.     return out;
  14. }

以下是相等的 Haskell 版本：

  1. -- file: ch04/upperCase.hs
  2.  
  3. import Data.Char (toUpper)
  4.  
  5. upperCase :: String -> String
  6.  
  7. upperCase (x: xs) = toUpper x : upperCase xs
  8. upperCase []      = []

代码从 Data.Char 模块引入了 toUpper 函数，如果输入字符是一个字母的话，那么函数就将它转换成大写：

  1. Prelude> :module +Data.Char
  2.  
  3. Prelude Data.Char> toUpper 'a'
  4. 'A'
  5.  
  6. Prelude Data.Char> toUpper 'A'
  7. 'A'
  8.  
  9. Prelude Data.Char> toUpper '1'
  10. '1'
  11.  
  12. Prelude Data.Char> toUpper '*'
  13. '*'

upperCase 函数和之前的 square 函数很相似：如果输入是一个空列表，那么它就停止计算，返回一个空列表。另一方面，如果输入不为空，那么它就对列表的第一个元素调用 toUpper 函数，并且递归调用自身，继续处理剩余的列表元素：

  1. Prelude> :load upperCase.hs
  2. [1 of 1] Compiling Main             ( upperCase.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> upperCase "The quick brown fox jumps over the lazy dog"
  6. "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"

以上两个函数遵循了同一种处理列表的公共模式：基本情形处理（base case）空列表输入。而递归情形（recursive case）则处理列表非空时的情况，它对列表的头元素进行某种操作，然后递归地处理列表余下的其他元素。

列表映射

前面定义的 square 和 upperCase 函数，都生成一个和输入列表同等长度的新列表，并且每次只对列表的一个元素进行处理。因为这种用法非常常见，所以 Haskell 的 Prelude 库定义了 map 函数来更方便地执行这种操作。 map 函数接受一个函数和一个列表作为参数，将输入函数应用到输入列表的每个元素上，并构建出一个新的列表。

以下是使用 map 重写的 square 和 upperCase 函数：

  1. -- file: ch04/rewrite_by_map.hs
  2.  
  3. import Data.Char (toUpper)
  4.  
  5. square2 xs = map squareOne xs
  6.     where squareOne x = x * x
  7.  
  8. upperCase2 xs = map toUpper xs

[译注：原文代码没有载入 Data.Char 中的 toUpper 函数。]

来研究一下 map 是如何实现的。通过查看它的类型签名，可以发现很多有意思的信息：

  1. Prelude> :type map
  2. map :: (a -> b) -> [a] -> [b]

类型签名显示， map 接受两个参数：第一个参数是一个函数，这个函数接受一个 a 类型的值，并返回一个 b 类型的值[译注：这里只是说 a 和 b 类型可能不一样，但不是必须的。]。

像 map 这种接受一个函数作为参数、又或者返回一个函数作为结果的函数，被称为高阶函数。

因为 map 的抽象出现在 square 和 upperCase 函数，所以可以通过观察这两个函数，找出它们之间的共同点，然后实现自己的 map 函数：

  1. -- file: ch04/myMap.hs
  2.  
  3. myMap :: (a -> b) -> [a] -> [b]
  4.  
  5. myMap f (x:xs) = f x : myMap f xs
  6. myMap _ [] = []

[译注：在原文的代码里，第二个等式的定义为 myMap _ _ = [] ，这并不是完全正确的，因为它可以适配于第二个参数不为列表的情况，比如 myMap f 1 。因此，这里遵循标准库里 map 的定义，将第二个等式修改为 myMap _ [] = [] 。]

在 ghci 测试这个 myMap 函数：

  1. Prelude> :load myMap.hs
  2. [1 of 1] Compiling Main             ( myMap.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> :module +Data.Char
  6.  
  7. *Main Data.Char> myMap toUpper "The quick brown fox"
  8. "THE QUICK BROWN FOX"

通过观察代码，并从中提炼出重复的抽象，是复用代码的一种良好方法。尽管对代码进行抽象并不是 Haskell 的“专利”，但高阶函数使得这种抽象变得非常容易。

筛选列表元素

另一种对列表的常见操作是，对列表元素进行筛选，只保留那些符合条件的元素。

以下函数接受一个列表作为参数，并返回这个列表里的所有奇数元素。代码的递归情形比之前的 map 函数要复杂一些，它使用守卫对元素进行条件判断，只有符合条件的元素，才会被加入进结果列表里：

  1. -- file: ch04/oddList.hs
  2.  
  3. oddList :: [Int] -> [Int]
  4.  
  5. oddList (x:xs) | odd x     = x : oddList xs
  6.                | otherwise = oddList xs
  7. oddList []                 = []

[译注：这里将原文代码的 oddList _ = [] 改为 oddList [] = [] ，原因和上一小节修改 map 函数的代码一样。]

测试：

  1. Prelude> :load oddList.hs
  2. [1 of 1] Compiling Main             ( oddList.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> oddList [1 .. 10]
  6. [1,3,5,7,9]

因为这种过滤模式也很常见，所以 Prelude 也定义了相应的函数 filter ：它接受一个谓词函数，并将它应用到列表里的每个元素，只有那些谓词函数求值返回 True 的元素才会被保留：

  1. Prelude> :type odd
  2. odd :: Integral a => a -> Bool
  3.  
  4. Prelude> odd 1
  5. True
  6.  
  7. Prelude> odd 2
  8. False
  9.  
  10. Prelude> :type filter
  11. filter :: (a -> Bool) -> [a] -> [a]
  12.  
  13. Prelude> filter odd [1 .. 10]
  14. [1,3,5,7,9]

[译注：谓词函数是指那种返回 Bool 类型值的函数。]

稍后的章节会介绍如何定义 filter 。

处理集合并得出结果

将一个集合（collection）缩减（reduce）为一个值也是集合的常见操作之一。

对列表的所有元素求和，就是其中的一个例子：

  1. -- file: ch04/mySum.hs
  2.  
  3. mySum xs = helper 0 xs
  4.     where helper acc (x:xs) = helper (acc + x) xs
  5.           helper acc []     = acc

helper 函数通过尾递归进行计算。 acc 是累积器（accumulator）参数，它记录了当前列表元素的总和。正如我们在 asInt 函数看到的那样，这种递归计算是纯函数语言里表示 loop 最自然的方式。

以下是一个稍微复杂一些的例子，它是一个 Adler-32 校验和的 JAVA 实现。Adler-32 是一个流行的校验和算法，它将两个 16 位校验和串联成一个 32 位校验和。第一个校验和是所有输入比特之和，加上一。而第二个校验和则是第一个校验和所有中间值之和。每次计算时，校验和都需要取模 65521 。（如果你不懂 JAVA ，直接跳过也没关系）：

  1. public class Adler32
  2. {
  3.     private static final int base = 65521;
  4.  
  5.     public static int compute(byte[] data, int offset, int length)
  6.     {
  7.         int a = 1, b = 0;
  8.  
  9.         for (int i = offset; i < offset + length; i++) {
  10.             a = (a + (data[i] & oxff)) % base
  11.             b = (a + b) % base;
  12.         }
  13.  
  14.         return (b << 16) | a;
  15.     }
  16. }

尽管 Adler-32 是一个简单的校验和算法，但这个 JAVA 实现还是非常复杂，很难看清楚位操作之间的关系。

以下是 Adler-32 算法的 Haskell 实现：

  1. -- file: ch04/Adler32.hs
  2.  
  3. import Data.Char (ord)
  4. import Data.Bits (shiftL, (.&.), (.|.))
  5.  
  6. base = 65521
  7.  
  8. adler32 xs = helper 1 0 xs
  9.     where helper a b (x:xs) = let a' = (a + (ord x .&. 0xff)) `mod` base
  10.                                   b' = (a' + b) `mod` base
  11.                               in helper a' b' xs
  12.           helper a b []     = (b `shiftL` 16) .|. a

在这段代码里， shiftL 函数实现逻辑左移， (.&.) 实现二进制位的并操作， (.|.) 实现二进制位的或操作， ord 函数则返回给定字符对应的编码值。

helper 函数通过尾递归来进行计算，每次对它的调用，都产生新的累积变量，效果等同于 JAVA 在 for 循环里对变量的赋值更新。当列表处理完毕，递归终止时，程序计算出校验和并将它返回。

和前面抽取出 map 和 filter 函数类似，从 Adler32 函数里面，我们也可以抽取出一种通用的抽象，称之为折叠（fold）：它对一个列表中的所有元素做某种处理，并且一边处理元素，一边更新累积器，最后在处理完整个列表之后，返回累积器的值。

有两种不同类型的折叠，其中 foldl 从左边开始进行折叠，而 foldr 从右边开始进行折叠。

左折叠

以下是 foldl 函数的定义：

  1. -- file: ch04/foldl.hs
  2.  
  3. foldl :: (a -> b -> a) -> a -> [b] -> a
  4.  
  5. foldl step zero (x:xs) = foldl step (step zero x) xs
  6. foldl _ zero []        = zero

[译注：这个函数在载入 ghci 时会因为命名冲突而被拒绝，编写函数直接使用内置的 foldl 就可以了。]

foldl 函数接受一个步骤（step）函数，一个累积器的初始化值，以及一个列表作为参数。步骤函数每次使用累积器和列表中的一个元素作为参数，并计算出新的累积器值，这个过程称为步进（stepper）。然后，将新的累积器作为参数，再次进行同样的计算，直到整个列表处理完为止。

以下是使用 foldl 重写的 mySum 函数：

  1. -- file: ch04/foldlSum.hs
  2. foldlSum xs = foldl step 0 xs
  3.     where step acc x = acc + x

因为代码里的 step 函数执行的操作不过是相加起它的两个输入参数，因此，可以直接将一个加法函数代替 step 函数，并移除多余的 where 语句：

  1. -- file: ch04/niceSum.hs
  2. niceSum :: [Integer] -> Integer
  3. niceSum xs = foldl (+) 0 xs

为了进一步看清楚 foldl 的执行模式，以下代码展示了 niceSum [1, 2, 3] 执行时的计算过程：

  1. niceSum [1, 2, 3]
  2.     == foldl (+) 0                   (1:2:3:[])
  3.     == foldl (+) (0 + 1)             (2:3:[])
  4.     == foldl (+) ((0 + 1) + 2)       (3:[])
  5.     == foldl (+) (((0 + 1) + 2) + 3) []
  6.     == (((0 + 1) + 2) + 3)

注意对比新的 mySum 定义比刚开始的定义节省了多少代码：新版本没有使用显式递归，因为 foldl 可以代替我们搞定了关于循环的一切。现在程序只要求我们回答两个问题：第一，累积器的初始化值是什么（foldl 的第二个参数）；第二，怎么更新累积器的值（(+) 函数）。

为什么使用 fold 、 map 和 filter ？

回顾一下之前的几个例子，可以看出，使用 fold 和 map 等高阶函数定义的函数，比起显式使用递归的函数，并不总是能节约大量代码。那么，我们为什么要使用这些函数呢？

答案是，因为它们在 Haskell 中非常通用，并且这些函数都带有正确的、可预见的行为。

这意味着，即使是一个 Haskell 新手，他/她理解起 fold 通常都要比理解显式递归要容易。一个 fold 并不产生任何意外动作，但一个显式递归函数的所做作为，通常并不是那么显而易见的。

以上观点同样适用于其他高阶函数库，包括前面介绍过的 map 和 filter 。因为这些函数都带有定义良好的行为，我们只需要学习怎样使用这些函数一次，以后每次碰到使用这些函数的代码，这些知识都可以加快我们对代码的理解。这种优势同样体现在代码的编写上：一旦我们能熟练使用高阶函数，那么写出更简洁的代码自然就不在话下。

从右边开始折叠

和 foldl 相对应的是 foldr ，它从一个列表的右边开始进行折叠。

  1. -- file: ch04/foldr.hs
  2.  
  3. foldr :: (a -> b -> b) -> b -> [a] -> b
  4.  
  5. foldr step zero (x:xs) = step x (foldr step zero xs)
  6. foldr _ zero []        = zero

[译注：这个函数在载入 ghci 时会因为命名冲突而被拒绝，编写函数直接使用内置的 foldr 就可以了。]

可以用 foldr 改写在《左折叠》一节定义的 niceSum 函数：

  1. -- file: ch04/niceSumFoldr.hs
  2.  
  3. niceSumFoldr :: [Int] -> Int
  4. niceSumFoldr xs = foldr (+) 0 xs

这个 niceSumFoldr 函数在输入为 [1, 2, 3] 时，产生以下计算序列：

  1. niceSumFoldr [1, 2, 3]
  2.     == foldr (+) 0 (1:2:3:[])
  3.     == 1 +           foldr (+) 0 (2:3:[])
  4.     == 1 + (2 +      foldr (+) 0 (3:[]))
  5.     == 1 + (2 + (3 + foldr (+) 0 []))
  6.     == 1 + (2 + (3 + 0))

可以通过观察括号的包围方式，以及累积器初始化值摆放的位置，来区分 foldl 和 foldr ：foldl 将处初始化值放在左边，括号也是从左边开始包围。另一方面，foldr 将初始化值放在右边，而括号也是从右边开始包围。

这里有一种可爱的凭直觉性的关于foldr如何工作的解释: 他用zero初始值替代了空列表，并且调用step函数替代列表的每个值构造器．

  1. 1 : (2 : (3 : []))
  2. 1 + (2 + (3 + 0 ))

乍一看,比起foldl，foldr似乎不那么有用：一个从右边折叠的函数有什么用呢？ 还记得当年大明湖畔的 filter 函数吗？它可以用显式递归来定义：

  1. -- file: ch04/filter.hs
  2.  
  3. filter :: (a -> Bool) -> [a] -> [a]
  4. filter p [] = []
  5. filter p (x:xs)
  6.     | p x       = x : filter p xs
  7.     | otherwise = filter p xs

[译注：这个函数在载入 ghci 时会因为命名冲突而被拒绝，编写函数直接使用内置的 filter 就可以了。]

除此之外， filter 还可以通过 foldr 来定义：

  1. -- file: ch04/myFilter.hs
  2. myFilter p xs = foldr step [] xs
  3.     where step x ys | p x       = x : ys
  4.                     | otherwise = ys

来仔细分析一下 myFilter 函数的定义：和 foldl 一样， foldr 也接受一个函数、一个基本情形和一个列表作为参数。通过阅读 filter 函数的类型签名可以得知， myFilter 函数的输入和输出都使用同类型的列表，因此函数的基本情形，以及局部函数 step ，都必须返回这个类型的列表。

myFilter 里的 foldr 每次取出列表中的一个元素，并对他进行处理，如果这个元素经过条件判断为 True ，那么就将它放进累积的新列表里面，否则，它就略过这个元素，继续处理列表的其他剩余元素。

所有可以用 foldr 定义的函数，统称为主递归（primitive recursive）。很大一部分列表处理函数都是主递归函数。比如说， map 就可以用 foldr 定义：

  1. -- file: ch04/myFoldrMap.hs
  2.  
  3. myFoldrMap :: (a -> b) -> [a] -> [b]
  4.  
  5. myFoldrMap f xs = foldr step [] xs
  6.     where step x xs = f x : xs

更让人惊奇的是， foldl 甚至可以用 foldr 来表示：

  1. -- file: ch04/myFoldl.hs
  2.  
  3. myFoldl :: (a -> b -> a) -> a -> [b] -> a
  4.  
  5. myFoldl f z xs = foldr step id xs z
  6.     where step x g a = g (f a x)

一种思考 foldr 的方式是，将它看成是对输入列表的一种转换（transform）：它的第一个参数决定了该怎么处理列表的 head 和 tail 部分；而它的第二个参数则决定了，当遇到空列表时，该用什么值来代替这个空列表。

用 foldr 定义的恒等（identity）转换，在列表为空时，返回空列表本身；如果列表不为空，那么它就将列表构造器 (:) 应用于每个 head 和 tail 对（pair）：

  1. -- file: ch04/identity.hs
  2.  
  3. identity :: [a] -> [a]
  4. identity xs = foldr (:) [] xs

最终产生的结果列表和原输入列表一模一样：

  1. Prelude> :load identity.hs
  2. [1 of 1] Compiling Main             ( identity.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> identity [1, 2, 3]
  6. [1,2,3]

如果将 identity 函数定义中，处理空列表时返回的 [] 改为另一个列表，那么我们就得到了列表追加函数 append ：

  1. -- file: ch04/append.hs
  2. append :: [a] -> [a] -> [a]
  3. append xs ys = foldr (:) ys xs

测试：

  1. Prelude> :load append.hs
  2. [1 of 1] Compiling Main             ( append.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> append "the quick " "fox"
  6. "the quick fox"

这个函数的效果等同于 (++) 操作符：

  1. *Main> "the quick " ++ "fox"
  2. "the quick fox"

append 函数依然对每个列表元素使用列表构造器，但是，当第一个输入列表为空时，它将第二个输入列表（而不是空列表元素）拼接到第一个输入列表的表尾。

通过前面这些例子对 foldr 的介绍，我们应该可以了解到， foldr 函数和《列表处理》一节所介绍的基本列表操作函数一样重要。由于 foldr 可以增量地处理和产生列表，所以它对于惰性数据处理也非常有用。

左折叠、惰性和内存泄漏

为了简化讨论，本节的例子通常都使用 foldl 来进行，这对于普通的测试是没有问题的，但是，千万不要把 foldl 用在实际使用中。

这样做是因为， Haskell 使用的是非严格求值。如果我们仔细观察 foldl (+) [1, 2, 3] 的执行过程，就可以会从中看出一些问题：

  1. foldl (+) 0 (1:2:3:[])
  2.           == foldl (+) (0 + 1)             (2:3:[])
  3.           == foldl (+) ((0 + 1) + 2)       (3:[])
  4.           == foldl (+) (((0 + 1) + 2) + 3) []
  5.           ==           (((0 + 1) + 2) + 3)

除非被显式地要求，否则最后的表达式不会被求值为 6 。在表达式被求值之前，它会被保存在块里面。保存一个块比保存单独一个数字要昂贵得多，而被块保存的表达式越复杂，这个块占用的空间就越多。对于数值计算这样的廉价操作来说，块保存这种表达式所需的计算量，比直接求值这个表达式所需的计算量还多。最终，我们既浪费了时间，又浪费了金钱。

在 GHC 中，对块中表达式的求值在一个内部栈中进行。因为块中的表达式可能是无限大的，而 GHC 为栈设置了有限大的的容量，多亏这个限制，我们可以在 ghci 里尝试求值一个大的块，而不必担心消耗掉全部内存。

[译注：使用栈来执行一些可能无限大的操作，是一种常见优化和保护技术。这种用法减少了操作系统显式的上下文切换，而且就算计算量超出栈可以容纳的范围，那么最坏的结果就是栈崩溃，而如果直接使用系统内存，一旦请求超出内存可以容纳的范围，可能会造成整个程序崩溃，甚至影响系统的稳定性。]

  1. Prelude> foldl (+) 0 [1..1000]
  2. 500500

可以推测出，在上面的表达式被求值之前，它创建了一个保存 1000 个数字和 999 个 (+) 操作的块。单单为了表示一个数字，我们就用了非常多的内存和 CPU ！

[译注：这些块到底有多大？算算就知道了：对于每一个加法表达式，比如 x + y ，都要使用一个块来保存。而这种操作在 foldl (+) 0 [1..1000] 里要执行 999 次，因此一共有 999 个块被创建，这些块都保存着像 x + y 这样的表达式。]

对于一个更大的表达式 —— 尽管它并不是真的非常庞大， foldl 的执行会失败：

  1. ghci> foldl (+) 0 [1..1000000]
  2. *** Exception: stack overflow

对于小的表达式来说， foldl 可以给出正确的答案，但是，因为过度的块资源占用，它运行非常缓慢。我们称这种现象为内存泄漏(space leak)：代码可以正确地执行，但它占用了比实际所需多得多的内存。

对于大的表达式来说，带有内存泄漏的代码会造成运行失败，就像前面例子展示的那样。

内存泄漏是 Haskell 新手常常会遇到的问题，幸好的是，它非常容易避免。Data.List 模块定义了一个 foldl' 函数，它和 foldl 的作用类似，唯一的区别是， foldl' 并不创建块。以下的代码直观地展示了它们的区别：

  1. ghci> foldl  (+) 0 [1..1000000]
  2. *** Exception: stack overflow
  3.  
  4. ghci> :module +Data.List
  5.  
  6. ghci> foldl' (+) 0 [1..1000000]
  7. 500000500000

综上所述，最好不要在实际代码中使用 foldl ：即使计算不失败，它的效率也好不到那里去。更好的办法是，使用 Data.List 里面的 foldl' 来代替。

[译注：在我的电脑上，超出内存的 foldl 失败方式和书本列出的并不一样：

  1. Prelude> foldl (+) 0 [1..1000000000]
  2. <interactive>: internal error: getMBlock: mmap: Operation not permitted
  3. (GHC version 7.4.2 for i386_unknown_linux)
  4. Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug
  5. 已放弃

从错误信息看， GHC/GHCi 处理 foldl 的方式应该已经发生了变化。

如果使用 foldl' 来执行计算，就不会出现任何问题：

  1. Prelude> :module +Data.List
  2.  
  3. Prelude Data.List> foldl' (+) 0 [1..1000000000]
  4. 500000000500000000

就是这样。] [我(github:sancao2)的电脑上面行为还是”Exception: stack overflow”.

  1. ➜  ch04  uname -a
  2. Linux centos 3.10.0-229.20.1.el7.x86_64 #1 SMP Tue Nov 3 19:10:07 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux
  3. ➜  ch04  ghci
  4. GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
  5. Loading package ghc-prim ... linking ... done.
  6. Loading package integer-gmp ... linking ... done.
  7. Loading package base ... linking ... done.
  8. Prelude> foldl (+) 0 [1..100000000]
  9. *** Exception: stack overflow

]

练习

1.运用 fold （运用合适的fold将会使你的代码更简单）重写并扩展位于＂显式递归＂章节的 asInt 函数．

  1. -- file: ch04/ch04.exercises.hs
  2. asInt_fold :: String -> Int

你函数的效果应该是这样的．

  1. ghci> asInt_fold "101"
  2. 101
  3. ghci> asInt_fold "-31337"
  4. -31337
  5. ghci> asInt_fold "1798"
  6. 1798

扩展你的函数以处理下面当调用错误时候出现的异常的情况．

  1. ghci> asInt_fold ""
  2. 0
  3. ghci> asInt_fold "-"
  4. 0
  5. ghci> asInt_fold "-3"
  6. -3
  7. ghci> asInt_fold "2.7"
  8. *** Exception: Char.digitToInt: not a digit '.'
  9. ghci> asInt_fold "314159265358979323846"
  10. 564616105916946374
  • asInt_fold 函数使用 error, 因而调用者不能处理这些错误．重写他来修复这个问题． 
  1. -- file: ch04/ch04.exercises.hs
  2. type ErrorMessage = String
  3. asInt_either :: String -> Either ErrorMessage Int
  4. ghci> asInt_either "33"
  5. Right 33
  6. ghci> asInt_either "foo"
  7. Left "non-digit 'o'"

3.Prelude下面的函数 concat 将一个列表的列表连接成一个单独的列表．他的函数签名如下．

  1. --file: ch04/ch04.exercises.hs
  2. concat :: [[a]] -> [a]

用foldr写出你自己山寨的concat．

4.写出你自己山寨的 takeWhile 函数，首先用显式递归的手法，然后改成 foldr 形式．

  • Data.List 模块定义了一个函数, groupBy.其拥有如下签名． 
  1. -- file: ch04/ch04.exercises.hs
  2. groupBy :: (a -> a -> Bool) -> [a] -> [[a]]

运用 ghci 加载 Data.List 模块以理解 groupBy 的行为，然后写出你自己山寨的 fold 实现．

  • 下面Prelude函数能用 fold 系列函数重写的函数有多少？ 
  1. any
  2.  
  3. cycle
  4.  
  5. words
  6.  
  7. unlines

这些函数你能用 foldl 或者 foldr 重写，请问那种情况更合适？

延伸阅读

A tutorial on the universality and expressiveness of fold 是一篇关于 fold 的优秀且深入的文章。它使用了很多例子来展示如何通过简单的系统化计算技术，将一些显式递归的函数转换成 fold 。

匿名（lambda）函数

在前面章节定义的函数中，很多函数都带有一个简单的辅助函数：

  1. -- file: ch04/isInAny.hs
  2.  
  3. import Data.List (isInfixOf)
  4.  
  5. isInAny needle haystack = any inSequence haystack
  6.     where inSequence s = needle `isInfixOf` s

Haskell 允许我们编写完全匿名的函数，这样就不必再费力地为辅助函数想名字了。因为匿名函数从 lambda 演算而来，所以匿名函数通常也被称为 lambda 函数。

在 Haskell 中，匿名函数以反斜杠符号 \ 为开始，后跟函数的参数（可以包含模式），而函数体定义在 -> 符号之后。其中， \ 符号读作 lambda 。

以下是前面的 isInAny 函数用 lambda 改写的版本：

  1. -- file: ch04/isInAny2.hs
  2.  
  3. import Data.List (isInfixOf)
  4.  
  5. isInAny2 needle haystack = any (\s -> needle `isInfixOf` s) haystack

定义使用括号包裹了整个匿名函数，确保 Haskell 可以知道匿名函数体在那里结束。

匿名函数各个方面的行为都和带名称的函数基本一致，但是，匿名函数的定义受到几个严格的限制，其中最重要的一点是：普通函数可以通过多条语句来定义，而 lambda 函数的定义只能有一条语句。

只能使用一条语句的局限性，限制了在 lambda 定义中可使用的模式。一个普通函数，通常要使用多条定义，来覆盖各种不同的模式：

  1. -- file: ch04/safeHead.hs
  2.  
  3. safeHead (x:_) = Just x
  4. safeHead [] = Nothing

而 lambda 只能覆盖其中一种情形：

  1. -- file ch04/unsafeHead.hs
  2. unsafeHead = \(x:_) -> x

如果一不小心，将这个函数应用到错误的模式上，它就会给我们带来麻烦：

  1. Prelude> :load unsafeHead.hs
  2. [1 of 1] Compiling Main             ( unsafeHead.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> :type unsafeHead
  6. unsafeHead :: [t] -> t
  7.  
  8. *Main> unsafeHead [1]
  9. 1
  10.  
  11. *Main> unsafeHead []
  12. *** Exception: unsafeHead.hs:2:14-24: Non-exhaustive patterns in lambda

因为这个 lambda 定义是完全合法的，它的类型也没有错误，所以它可以被顺利编译，而最终在运行期产生错误。这个故事说明，如果你要在 lambda 函数里使用模式，请千万小心，必须确保你的模式不会匹配失败。

另外需要注意的是，在前面定义的 isInAny 函数和 isInAny2 函数里，带有辅助函数的 isInAny 要比使用 lambda 的 isInAny2 要更具可读性。带有名字的辅助函数不会破坏程序的代码流（flow），而且它的名字也可以传达更多的相关信息。

相反，当在一个函数定义里面看到 lambda 时，我们必须慢下来，仔细阅读这个匿名函数的定义，弄清楚它都干了些什么。为了程序的可读性和可维护性考虑，我们在很多情况下都会避免使用 lambda 。

当然，这并不是说 lambda 函数完全没用，只是在使用它们的时候，必须小心谨慎。

很多时候，部分应用函数可以很好地代替 lambda 函数，避免不必要的函数定义，粘合起不同的函数，并产生更清晰和更可读的代码。下一节就会介绍部分应用函数。

部分函数应用和柯里化

类型签名里的 -> 可能会让人感到奇怪：

  1. Prelude> :type dropWhile
  2. dropWhile :: (a -> Bool) -> [a] -> [a]

初看上去，似乎 -> 既用于隔开 dropWhile 函数的各个参数（比如括号里的 a 和 Bool ），又用于隔开函数参数和返回值的类型（(a -> Bool) -> [a] 和 [a]）。

但是，实际上 -> 只有一种作用：它表示一个函数接受一个参数，并返回一个值。其中 -> 符号的左边是参数的类型，右边是返回值的类型。

理解 -> 的含义非常重要：在 Haskell 中，所有函数都只接受一个参数。尽管 dropWhile 看上去像是一个接受两个参数的函数，但实际上它是一个接受一个参数的函数，而这个函数的返回值是另一个函数，这个被返回的函数也只接受一个参数。

以下是一个完全合法的 Haskell 表达式：

  1. Prelude> :module +Data.Char
  2.  
  3. Prelude Data.Char> :type dropWhile isSpace
  4. dropWhile isSpace :: [Char] -> [Char]

表达式 dropWhile isSpace 的值是一个函数，这个函数移除一个字符串的所有前缀空白。作为一个例子，可以将它应用到一个高阶函数：

  1. Prelude Data.Char> map (dropWhile isSpace) [" a", "f", "    e"]
  2. ["a","f","e"]

每当我们将一个参数传给一个函数时，这个函数的类型签名最前面的一个元素就会被“移除掉”。这里用函数 zip3 来做例子，这个函数接受三个列表，并将它们压缩成一个包含三元组的列表：

  1. Prelude> :type zip3
  2. zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
  3.  
  4. Prelude> zip3 "foo" "bar" "quux"
  5. [('f','b','q'),('o','a','u'),('o','r','u')]

如果只将一个参数应用到 zip3 函数，那么它就会返回一个接受两个参数的函数。无论之后将什么参数传给这个复合函数，之前传给它的第一个参数的值都不会改变。

  1. Prelude> :type zip3
  2. zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
  3.  
  4. Prelude> :type zip3 "foo"
  5. zip3 "foo" :: [b] -> [c] -> [(Char, b, c)]
  6.  
  7. Prelude> :type zip3 "foo" "bar"
  8. zip3 "foo" "bar" :: [c] -> [(Char, Char, c)]
  9.  
  10. Prelude> :type zip3 "foo" "bar" "quux"
  11. zip3 "foo" "bar" "quux" :: [(Char, Char, Char)]

传入参数的数量，少于函数所能接受参数的数量，这种情况被称为函数的部分应用（partial application of the function）：函数正被它的其中几个参数所应用。

在上面的例子中， zip3 "foo" 就是一个部分应用函数，它以 "foo" 作为第一个参数，部分应用了 zip3 函数；而 zip3 "foo" "bar" 也是另一个部分应用函数，它以 "foo" 和 "bar" 作为参数，部分应用了 zip3 函数。

只要给部分函数补充上足够的参数，它就可以被成功求值：

  1. Prelude> let zip3foo = zip3 "foo"
  2.  
  3. Prelude> zip3foo "bar" "quux"
  4. [('f','b','q'),('o','a','u'),('o','r','u')]
  5.  
  6. Prelude> let zip3foobar = zip3 "foo" "bar"
  7.  
  8. Prelude> zip3foobar "quux"
  9. [('f','b','q'),('o','a','u'),('o','r','u')]
  10.  
  11. Prelude> zip3foobar [1, 2, 3]
  12. [('f','b',1),('o','a',2),('o','r',3)]

部分函数应用（partial function application）让我们免于编写烦人的一次性函数，而且它比起之前介绍的匿名函数要来得更有用。回顾之前的 isInAny 函数，以下是一个部分应用函数改写的版本，它既不需要匿名函数，也不需要辅助函数：

  1. -- file: ch04/isInAny3.hs
  2.  
  3. import Data.List (isInfixOf)
  4.  
  5. isInAny3 needle haystack = any (isInfixOf needle) haystack

表达式 isInfixOf needle 是部分应用函数，它以 needle 变量作为第一个参数，传给 isInfixOf ，并产生一个部分应用函数，这个部分应用函数的作用等同于 isInAny 定义的辅助函数，以及 isInAny2 定义的匿名函数。

部分函数应用被称为柯里化（currying），以逻辑学家 Haskell Curry 命名（Haskell 语言的命名也是来源于他的名字）。

以下是另一个使用柯里化的例子。先来回顾《左折叠》章节的 niceSum 函数：

  1. -- file: ch04/niceSum.hs
  2. niceSum :: [Integer] -> Integer
  3. niceSum xs = foldl (+) 0 xs

实际上，并不需要完全应用 foldl [译注：完全应用是指提供函数所需的全部参数]，niceSum 函数的 xs 参数，以及传给 foldl 函数的 xs 参数，这两者都可以被省略，最终得到一个更紧凑的函数，它的类型也和原本的一样：

  1. -- file: ch04/niceSumPartial.hs
  2. niceSumPartial :: [Integer] -> Integer
  3. niceSumPartial = foldl (+) 0

测试：

  1. Prelude> :load niceSumPartial.hs
  2. [1 of 1] Compiling Main             ( niceSumPartial.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> niceSumPartial [1 .. 10]
  6. 55

节

Haskell 提供了一种方便的符号快捷方式，用于对中序函数进行部分应用：使用括号包围一个操作符，通过在括号里面提供左操作对象或者右操作对象，可以产生一个部分应用函数。这种类型的部分函数应用称之为节（section）。

  1. Prelude> (1+) 2
  2. 3
  3.  
  4. Prelude> map (*3) [24, 36]
  5. [72,108]
  6.  
  7. Prelude> map (2^) [3, 5, 7, 9]
  8. [8,32,128,512]

如果向节提供左操作对象，那么得出的部分函数就会将接收到的参数应用为右操作对对象，反之亦然。

以下两个表达式都计算 2 的 3 次方，但是第一个节接受的是左操作对象 2 ，而第二个节接受的则是右操作对象 3 。

  1. Prelude> (2^) 3
  2. 8
  3.  
  4. Prelude> (^3) 2
  5. 8

之前提到过，通过使用反括号来包围一个函数，可以将这个函数用作中序操作符。这种用法可以让节使用函数：

  1. Prelude> :type (`elem` ['a' .. 'z'])
  2. (`elem` ['a' .. 'z']) :: Char -> Bool

上面的定义将 ['a' .. 'z'] 传给 elem 作为第二个参数，表达式返回的函数可以用于检查一个给定字符值是否属于小写字母：

  1. Prelude> (`elem` ['a' .. 'z']) 'f'
  2. True
  3.  
  4. Prelude> (`elem` ['a' .. 'z']) '1'
  5. False

还可以将这个节用作 all 函数的输入，这样就得到了一个检查给定字符串是否整个字符串都由小写字母组成的函数：

  1. Prelude> all (`elem` ['a' .. 'z']) "Haskell"
  2. False
  3.  
  4. Prelude> all (`elem` ['a' .. 'z']) "haskell"
  5. True

通过这种用法，可以再一次提升 isInAny3 函数的可读性：

  1. -- file: ch04/isInAny4.hs
  2.  
  3. import Data.List (isInfixOf)
  4.  
  5. isInAny4 needle haystack = any (needle `isInfixOf`) haystack

[译注：根据前面部分函数部分提到的技术，这个 isInAny4 的定义还可以进一步精简，去除 haystack 参数：

  1. import Data.List (isInfixOf)
  2. isInAny4Partial needle = any (needle `isInfixOf`)

]

As-模式

Data.List 模块里定义的 tails 函数是 tail 的推广，它返回一个列表的所有“尾巴”：

  1. Prelude> :m +Data.List
  2.  
  3. Prelude Data.List> tail "foobar"
  4. "oobar"
  5.  
  6. Prelude Data.List> tail (tail "foobar")
  7. "obar"
  8.  
  9. Prelude Data.List> tails "foobar"
  10. ["foobar","oobar","obar","bar","ar","r",""]

tails 返回一个包含字符串的列表，这个列表保存了输入字符串的所有后缀，以及一个额外的空列表（放在结果列表的最后）。tails 的返回值总是带有额外的空列表，即使它的输入为空时：

  1. Prelude Data.List> tails ""
  2. [[]]

如果想要一个行为和 tails 类似，但是并不包含空列表后缀的函数，可以自己写一个：

  1. -- file: ch04/suffixes.hs
  2.  
  3. suffixes :: [a] -> [[a]]
  4. suffixes xs@(_:xs') = xs : suffixes xs'
  5. suffixes [] = []

[译注：在稍后的章节就会看到，有简单得多的方法来完成这个目标，这个例子主要用于展示 as-模式的作用。]

源码里面用到了新引入的 @ 符号，模式 xs@(_:xs') 被称为 as-模式，它的意思是：如果输入值能匹配 @ 符号右边的模式（这里是 (_:xs') ），那么就将这个值绑定到 @ 符号左边的变量中（这里是 xs ）。

在这个例子里，如果输入值能够匹配模式 (_:xs') ，那么这个输入值这就被绑定为 xs ，它的 tail 部分被绑定为 xs' ，而它的 head 部分因为使用通配符 _ 进行匹配，所以这部分没有被绑定到任何变量。

  1. *Main Data.List> tails "foo"
  2. ["foo","oo","o",""]
  3.  
  4. *Main Data.List> suffixes "foo"
  5. ["foo","oo","o"]

As-模式可以提升代码的可读性，作为对比，以下是一个没有使用 as-模式的 suffixes 定义：

  1. -- file: noAsPattern.hs
  2.  
  3. noAsPattern :: [a] -> [[a]]
  4. noAsPattern (x:xs) = (x:xs) : noAsPattern xs
  5. noAsPattern [] = []

可以看到，使用 as-模式的定义同时完成了模式匹配和变量绑定两项工作。而不使用 as-模式的定义，则需要在对列表进行结构之后，在函数体里又重新对列表进行组合。

除了增强可读性之外， as-模式还有其他作用：它可以对输入数据进行共享，而不是复制它。在 noAsPattern 函数的定义中，当 (x:xs) 匹配时，在函数体里需要复制一个 (x:xs) 的副本。这个动作会引起内存分配。虽然这个分配动作可能很廉价，但它并不是免费的。相反，当使用 suffixes 函数时，我们通过变量 xs 重用匹配了 as-模式的输入值，因此就避免了内存分配。

通过组合函数来进行代码复用

前面的 suffixes 函数实际上有一种更简单的实现方式。

回忆前面在《使用列表》一节里介绍的 init 函数，它可以返回一个列表中除了最后一个元素之外的其他元素。而组合使用 init 和 tails ，可以给出一个 suffixes 函数的更简单实现：

  1. -- file: ch04/suffixes.hs
  2.  
  3. import Data.List (tails)
  4.  
  5. suffixes2 xs = init (tails xs)

suffixes2 和 suffixes 函数的行为完全一样，但 suffixes2 的定义只需一行：

  1. Prelude> :load suffixes2.hs
  2. [1 of 1] Compiling Main             ( suffixes2.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> suffixes2 "foobar"
  6. ["foobar","oobar","obar","bar","ar","r"]

如果仔细地观察，就会发现这里隐含着一个模式：我们先应用一个函数，然后又将这个函数得出的结果应用到另一个函数。可以将这个模式定义为一个函数：

  1. -- file: ch04/compose.hs
  2.  
  3. compose :: (b -> c) -> (a -> b) -> a -> c
  4. compose f g x = f (g x)

compose 函数可以用于粘合两个函数：

  1. Prelude> :load compose.hs
  2. [1 of 1] Compiling Main             ( compose.hs, interpreted )
  3. Ok, modules loaded: Main.
  4.  
  5. *Main> :m +Data.List
  6.  
  7. *Main Data.List> let suffixes3 xs = compose init tails xs

通过柯里化，可以丢掉 xs 函数：

  1. *Main Data.List> let suffixes4 = compose init tails

更棒的是，其实我们并不需要自己编写 compose 函数，因为 Haskell 已经内置在了 Prelude 里面，使用 (.) 操作符就可以组合起两个函数：

  1. *Main Data.List> let suffixes5 = init . tails

(.) 操作符并不是什么特殊语法，它只是一个普通的操作符：

  1. *Main Data.List> :type (.)
  2. (.) :: (b -> c) -> (a -> b) -> a -> c
  3.  
  4. *Main Data.List> :type suffixes5
  5. suffixes5 :: [a] -> [[a]]
  6.  
  7. *Main Data.List> suffixes5 "foobar"
  8. ["foobar","oobar","obar","bar","ar","r"]

在任何时候，都可以通过使用 (.) 来组合函数，并产生新函数。组合链的长度并没有限制，只要 (.) 符号右边函数的输出值类型适用于 (.) 符号左边函数的输入值类型就可以了。

也即是，对于 f . g 来说， g 的输出值必须是 f 能接受的类型，这样的组合就是合法的， (.) 的类型签名也显示了这一点。

作为例子，再来解决一个非常常见的问题：计算字符串中以大写字母开头的单词的个数：

  1. Prelude> :module +Data.Char
  2.  
  3. Prelude Data.Char> let capCount = length . filter (isUpper . head) . words
  4.  
  5. Prelude Data.Char> capCount "Hello there, Mon!"
  6. 2

来逐步分析 capCount 函数的组合过程。因为 (.) 操作符是右关联的，因此我们从组合链的最右边开始研究：

  1. Prelude Data.Char> :type words
  2. words :: String -> [String]

words 返回一个 [String] 类型值，因此 (.) 的左边的函数必须能接受这个参数。

  1. Prelude Data.Char> :type isUpper . head
  2. isUpper . head :: [Char] -> Bool

上面的组合函数在输入字符串以大写字母开头时返回 True ，因此 filter (isUpper . head) 表达式会返回所有以大写字母开头的字符串：

  1. Prelude Data.Char> :type filter (isUpper . head)
  2. filter (isUpper . head) :: [[Char]] -> [[Char]]

因为这个表达式返回一个列表，而 length 函数用于统计列表的长度，所以 length . filter (isUpper . head) 就计算出了所有以大写字母开头的字符串的个数。

以下是另一个例子，它从 libpcap —— 一个流行的网络包过滤库中提取 C 文件头中给定格式的宏名字。这些头文件带有很多以下格式的宏：

  1. #define DLT_EN10MB      1       /* Ethernet (10Mb) */
  2. #define DLT_EN3MB       2       /* Experimental Ethernet (3Mb) */
  3. #define DLT_AX25        3       /* Amateur Radio AX.25 */

我们的目标是提取出所有像 DLT_AX25 和 DLT_EN3MB 这种名字。以下是程序的定义，它将整个文件看作是一个字符串，先使用 lines 对文件进行按行分割，再将 foldr step [] 应用到各行当中，其中 step 辅助函数用于过滤和提取符合格式的宏名字：

  1. -- file: ch04/dlts.hs
  2.  
  3. import Data.List (isPrefixOf)
  4.  
  5. dlts :: String -> [String]
  6.  
  7. dlts = foldr step [] . lines
  8.   where step l ds
  9.           | "#define DLT_" `isPrefixOf` l = secondWord l : ds
  10.           | otherwise                     = ds
  11.         secondWord = head . tail . words

程序通过守卫表达式来过滤输入：如果输入字符串符合给定格式，就将它加入到结果列表里；否则，就略过这个字符串，继续处理剩余的输入字符串。

至于 secondWord 函数，它先取出一个列表的 tail 部分，得出一个新列表。再取出新列表的 head 部分，等同于取出一个列表的第二个元素。

[译注：书本的这个程序弱爆了，以下是 dlts 的一个更直观的版本，它使用 filter 来过滤输入，只保留符合格式的输入，而不是使用复杂且难看的显式递归和守卫来进行过滤：

  1. -- file: ch04/dlts2.hs
  2.  
  3. import Data.List (isPrefixOf)
  4.  
  5. dlts2 :: String -> [String]
  6. dlts2 = map (head . tail . words) . filter ("#define DLT_" `isPrefixOf`) . lines

]

编写可读代码的提示

目前为止，我们知道 Haskell 有两个非常诱人的特性：尾递归和匿名函数。但是，这两个特性通常并不被使用。

对列表的处理操作一般可以通过组合库函数比如 map 、 take 和 filter 来进行。当然，熟悉这些库函数需要一定的时间，不过掌握这些函数之后，就可以使用它们写出更快更好更少 bug 的代码。

库函数比尾递归更好的原因很简单：尾递归和命令式语言里的 loop 有同样的问题 —— 它们太通用（general）了。在一个尾递归里，你可以同时执行过滤（filtering）、映射（mapping）和其他别的动作。这强迫代码的阅读者（可能是你自己）必须弄懂整个递归函数的定义，才能理解这个函数到底做了些什么。与此相反，map 和其他很多列表函数，都只专注于做一件事。通过这些函数，我们可以很快理解某段代码到底做了什么，以及整个程序想表达什么意思，而不是将时间浪费在关注细节方面。

折叠（fold）操作处于（完全通用化的）尾递归和（只做一件事的）列表处理函数之间的中间地带。折叠也很值得我们花时间去好好理解，它的作用跟组合起 map 和 filter 函数差不多，但比起显式递归来说，折叠的行为要来得更有规律，而且更可控。一般来说，可以通过组合函数来解决的问题，就不要使用折叠。另一方面，如果问题用组合函数没办法解决，那么使用折叠要比使用显式递归要好。

另一方面，匿名函数通常会对代码的可读性造成影响。一般来说，匿名函数都可以用 let 或者 where 定义的局部函数来代替。而且带名字的局部函数可以达到一箭双雕的效果：它使得代码更具可读性，且函数名本身也达到了文档化的作用。

内存泄漏和严格求值

前面介绍的 foldl 函数并不是 Haskell 代码里唯一会造成内存泄漏的地方。

在这一节，我们使用 foldl 来展示非严格求值在什么情况下会造成问题，以及如何去解决这些问题。

通过 seq 函数避免内存泄漏

我们称非惰性求值的表达式为严格的（strict）。 foldl' 就是左折叠的严格版本，它使用特殊的 seq 函数来绕过 Haskell 默认的非严格求值：

  1. -- file: ch04/strictFoldl.hs
  2.  
  3. foldl' _ zero [] = zero
  4. foldl' step zero (x:xs) = 
  5.     let new = step zero x
  6.     in new `seq` foldl' step new xs

seq 函数的类型签名和之前看过的函数都有些不同，昭示了它的特殊身份：

  1. ghci> :type seq
  2. seq :: a -> t -> t

[译注：在 7.4.2 版本的 GHCi 里， seq 函数的类型签名不再使用 t ，而是像其他函数一样，使用 a 和 b 。

  1. Prelude> :type seq
  2. seq :: a -> b -> b

]

实际上， seq 函数的行为并没有那么神秘：它强迫（force）求值传入的第一个参数，然后返回它的第二个参数。

比如说，对于以下表达式：

  1. foldl' (+) 1 (2:[])

它展开为：

  1. let new = 1 + 2
  2. in new `seq` foldl' (+) new []

它强迫 new 求值为 3 ，然后返回它的第二个参数：

  1. foldl' (+) 3 []

最终得到结果 3 。

因为 seq 的存在，这个创建过程没有用到任何块。

seq 的用法

本节介绍一些更有效地使用 seq 的指导规则。

要正确地产生 seq 的作用，表达式中被求值的第一个必须是 seq ：

  1. -- 错误：因为表达式中第一个被求值的是 someFunc 而不是 seq
  2. -- 所以 seq 的调用被隐藏了在 someFunc 调用之下
  3. hiddenInside x y = someFunc (x `seq` y)
  4.  
  5. -- 错误：原因和上面一样
  6. hiddenByLet x y z = let a = x `seq` someFunc y
  7.                     in anotherFunc a z
  8.  
  9. -- 正确： seq 被第一个求值，并且 x 被强迫求值
  10. onTheOutside x y = x `seq` someFunc y

为了严格求值多个值，可以连接起 seq 调用：

  1. chained x y z = x `seq` y `seq` someFunc z

一个常见错误是，将 seq 用在没有关联的两个表达式上面：

  1. badExpression step zero (x:xs) =
  2.     seq (step zero x)
  3.             (badExpression step (step zero x) xs)

step zero x 分别出现在 seq 的第一个参数和 badExpression 的表达式内， seq 只会对第一个 step zero x 求值，而它的结果并不会影响 badExpression 表达式内的 step zero x 。正确的用法应该是用一个 let 结果保存起 step zero x 表达式，然后将它分别传给 seq 和 badExpression ，做法可以参考前面的 foldl' 的定义。

seq 在遇到像数字这样的值时，它会对值进行求值，但是，一旦 seq 碰到构造器，比如 (:) 或者 (,) ，那么 seq 的求值就会停止。举个例子，如果将 (1+2):[] 传给 seq 作为它的第一个参数，那么 seq 不会对这个表达式进行求值；相反，如果将 1 传给 seq 作为第一个参数，那么它会被求值为 1 。

[译注：

原文说，对于 (1+2):[] 这样的表达式， seq 在求值 (1+2) 之后，碰到 : ，然后停止求值。但是根据原文网站上的评论者测试， seq 并不会对 (1+2) 求值，而是在碰到 (1+2):[] 时就直接停止求值。

这一表现可能的原因如下：虽然 : 是中序操作符，但它实际上只是函数 (:) ，而 Haskell 的函数总是前序的，因此 (1+2):[] 实际上应该表示为 (:) (1+2) [] ，所以原文说“seq 在碰到构造器时就会停止求值”这一描述并没有出错，只是给的例子出了问题。

因为以上原因，这里对原文进行了修改。

]

如果有需要的话，也可以绕过这些限制：

  1. strictPair (a,b) = a `seq` b `seq` (a,b)
  2.  
  3. strictList (x:xs) = x `seq` x : strictList xs
  4. strictList []     = []

seq 的使用并不是无成本的，知道这一点很重要：它需要在运行时检查输入值是否已经被求值。必须谨慎使用 seq 。比如说，上面定义的 strictPair ，尽管它能顺利对元组进行强制求值，但它在求值元组所需的计算量上，加上了一次模式匹配、两次 seq 调用和一次构造新元组的计算量。如果我们检测这个函数的性能的话，就会发现它降低了程序的处理速度。

即使不考虑性能的问题， seq 也不是处理内存泄漏的万能药。可以进行非严格求值，但并不意味着非用它不可。对 seq 的不小心使用可能对内存泄漏并没有帮助，在更糟糕的情况下，它还会造成新的内存泄漏。

第二十五章会介绍关于性能和优化的内容，到时会说明更多 seq 的用法和细节。