In [1]:
:opt no-pager
初学 Haskell 的人需要迈过两个难关:
首先,我们需要将自己的编程观念从命令式语言转换到函数式语言上面来。这样做的原因并不是因为命令式语言不好,而是因为比起命令式语言,函数式语言更胜一筹。
其次,我们需要熟悉 Haskell 的标准库。和其他语言一样,函数库可以像杠杆那样,极大地提升我们解决问题的能力。因为 Haskell 是一门层次非常高的语言,而 Haskell 的标准库也趋向于处理高层次的抽象,因此对 Haskell 标准库的学习也稍微更难一些,但这些努力最终都会物有所值。
这一章会介绍一些常用的函数式编程技术,以及一些 Haskell 特性。还会在命令式语言和函数式语言之间进行对比,帮助读者了解它们之间的区别,并且在这个过程中,陆续介绍一些基本的 Haskell 标准库。
在本章的大部分时间里,我们都只和无副作用的代码打交道。为了将注意力集中在实际的代码上,我们需要开发一个接口程序,连接起带副作用的代码和无副作用的代码。
这个接口程序读入一个文件,将函数应用到文件,并且将结果写到另一个文件:
In [2]:
-- file: ch04/InteractWith.hs
import System.Environment (getArgs)
interactWith function inputFile outputFile = do
input <- readFile inputFile
writeFile outputFile (function input)
main = mainWith myFunction
where mainWith function = do
args <- getArgs
case args of
[input,output] -> interactWith function input output
_ -> putStrLn "error: exactly two arguments needed"
-- replace "id" with the name of our function below
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 类型 ”。
接下来编译这个程序:
$ ghc --make InteractWith
[1 of 1] Compiling Main ( InteractWith.hs, InteractWith.o )
Linking InteractWith ...
通过命令行运行这个程序。它接受两个文件名作为参数输入,一个用于读取,一个用于写入:
$ echo "hello world" > hello-in.txt
$ ./InteractWith hello-in.txt hello-out.txt
$ cat hello-in.txt
hello world
$ cat hello-out.txt
hello world
[译注:原书这里的执行过程少了写入内容到 hello-in.txt 的一步,导致执行会出错,所以这里加上 echo ... 这一步。另外原书执行的是 Interact 过程,也是错误的,正确的执行文件名应该是 InteractWith 。]
Haskell提供一个内建函数,lines,让我们在行边界上分离一段文本字符串。它返回一个忽略了行终止字符的字符串列表。
ghci> :type lines
lines :: String -> [String]
ghci> lines "line 1\nline 2"
["line 1","line 2"]
ghci> lines "foo\n\nbar\n"
["foo","","bar"]
尽管lines看上去有用,但它要工作的话仰赖于我们用“文本模式”去读一个文件。文本模式对于很多编程语言来说是一个很普遍的功能:当我们在Windows系统上读和写文件的时候它提供一个特别的行为。当我们用文本模式读取一个文件的时候,文件I/O库把行终止序列“rn”(回车后跟着一个换行)转换成“n”(单独一个换行),当我们写一个文件的时候,它(译注:文件I/O库)会做相反的事情。而在类Unix系统上,文本模式不会做任何的转换工作。这个不同之处会导致的结果是,如果我们在Windows系统上读取一个在类Unix系统上写入的文件,行终止符很可能会变得乱七八糟。(readFile和writeFile都在文本模式下操作的话)
ghci> lines "a\r\nb"
["a\r","b"]
lines函数仅仅在换行符处分离文本,留下回车跟在行的结尾处。如果我们在Linux或Unix上读取一个Windows生成的文本文件,我们将在每一行的结尾处得到尾随的回车。
我们舒适地用了Python提供的“通用换行”支持很长时间了:它透明地为我们处理Unix和Windows的行终止惯例。我们也想要用Haskell提供类似的支持。
因为到目前为止我们仅仅接触了少量的Haskell代码,所以我们将一步一步地讨论我们用Haskell实现上述支持的细节。
In [3]:
-- file: ch04/SplitLines.hs
splitLines :: String -> [String]
splitLines [] = []
splitLines cs =
let (pre, suf) = break isLineTerminator cs
in pre : case suf of
('\r':'\n':rest) -> splitLines rest
('\r':rest) -> splitLines rest
('\n':rest) -> splitLines rest
_ -> []
isLineTerminator c = c == '\r' || c == '\n'
在我们深入细节之前,首先注意我们是怎么组织我们的代码的。我们首先呈现重要的代码片段,而把isLineTerminator函数的定义放在后面。因为我们给了这个辅助函数一个易读的名称,所以即使在我们读它的定义之前我们就能知道它是做什么用的。
Prelude定义了一个叫做break的函数,我们可以用它把一个列表分成两部分。它把一个函数作为它的第一个参数。这个函数必须去检查列表中的元素,并且返回一个Bool值来表示列表是否在那个元素处被一分为二。break函数返回一个对值(译注:即二元组),由一个谓词(译注:即一个返回Bool值的函数,下同)返回True(译注:第一次返回True)之前的元素构成的列表(前缀)和剩下的元素构成的列表组成(后缀)。
ghci> break odd [2,4,5,6,8]
([2,4],[5,6,8])
ghci> :module +Data.Char
ghci> break isUpper "isUpper"
("is","Upper")
因为我们一次只需要匹配单个的回车或换行,所以每次检查列表中的一个元素正是我们所需要的。
splitLines的第一个算式标示如果我们匹配到一个空的字符串,我们就没有进一步的工作可做了。
在第二个算式中,我们首先对输入的字符串应用break。前缀就是第一个行终止符之前的子字符串,后缀就是整个字符串余下的部分。这个后缀将包含可能存在的行终止符。
“pre :”表达式告诉我们应该在这个代表文本行的列表的头部加上pre所表示的值。然后我们用一个case表达式去检查后缀,我们来决定下一步做什么。case表达式的结果将被用作(:)函数的的二个参数来构造结果列表。
case表达式中的第一个模式匹配以一个回车紧接着一个换行符开始的字符串。变量rest被绑定到这个字符串余下的部分。其它的模式是相似的,因此它们应当容易理解。
以上对Haskell函数的散文式的描述不一定是容易理解的。我们可以借助ghci,观察不同情况下这个函数的行为,以获得更好的理解。
让我们从分割一个不包含任何行终止符的字符串开始。
ghci> splitLines "foo"
["foo"]
这里,我们的break没找到一个行终止符,所以它返回的后缀是空的。
ghci> break isLineTerminator "foo"
("foo","")
因此在splitLines函数中的case表达式一定是匹配上了第四个分支,然后完成了求值。 再来一点儿更有趣的例子怎么样?
ghci> splitLines "foo\r\nbar"
["foo","bar"]
首先我们的break给我们一个非空的后缀。
ghci> break isLineTerminator "foo\r\nbar"
("foo","\r\nbar")
因为这个后缀以一个回车紧接着一个换行符开始,我们匹配上了case表达式的第一个分支。这个求值结果让我们把pre绑定到“foo”,suf绑定到“bar”。我们递归地应用splitLines,这一次匹配上单独的“bar”。
ghci> splitLines "bar"
["bar"]
结果是我们构造了一个头部的元素是“foo”,尾部的元素是“bar”的列表
ghci> "foo" : ["bar"]
["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函数,它把一个字符串组成的列表串联起来,并且在每个字符串元素的末尾加上一个换行符。
In [4]:
-- file: ch04/SplitLines.hs
fixLines :: String -> String
fixLines input = unlines (splitLines input)
fixLines "123\nqwe\r\nzxc\n"
如果我们用fixLines替换这个id函数(译注:是指拷贝自Interact.hs的FixLines.hs中的id函数),我们可以把FixLines.hs编译成一个将文本文件的行终止转换成系统特定的行终止的可执行程序。
$ ghc --make FixLines
[1 of 1] Compiling Main ( FixLines.hs, FixLines.o )
Linking FixLines ...
如果你在一个Windows系统上面,找到并下载一个在Unix系统上创建的文本文件(比如 gpl-3.0.txt)。在记事本程序中打开它。里面的文本行应该都跑一起去了,导致它几乎不可读。用刚才你编译得到的FixLines命令处理这个文件,然后在记事本程序中打开此命令输出的文件。现在这个行终止符的问题应该被修正了。
在类Unix的系统上,编辑器隐藏了Windows的行终止符。使得验证FixLines是否消除了它们更加困难。这里有一些命令应该能帮助你。
$ file gpl-3.0.txt
gpl-3.0.txt: ASCII English text
$ unix2dos gpl-3.0.txt
unix2dos: converting file gpl-3.0.txt to DOS format ...
$ file gpl-3.0.txt
gpl-3.0.txt: ASCII English text, with CRLF line terminators
通常,当我们在Haskell中定义和应用一个函数的时候,我们写这个函数的名称,紧接着它的参数。这种表示法作为前缀被提及,因为这个函数的名称位于它的参数前面。
如果一个函数或构造器带两个或更多的参数,我们可以选择使用中缀形式,即我们把函数(名称)放在它的第一个和第二个参数之间。这允许我们把函数作为中缀操作符来使用。
要用中缀表示法定义或应用一个函数或值构造器,我们用重音符(有时被称为反引号)包围它的名称。这里有简单的中缀函数和中缀类型的定义。
In [5]:
-- file: ch04/Plus.hs
a `plus` b = a + b
data a `Pair` b = a `Pair` b
deriving (Show)
-- we can use the constructor either prefix or infix
foo = Pair 1 2
bar = True `Pair` "quux"
因为中缀表示法纯粹是为了语法上的便利,因此它不会改变函数的行为。
In [6]:
1 `plus` 2
plus 1 2
True `Pair` "something"
Pair True "something"
中缀表示法经常对代码可读性有帮助。比如,Prelude定义了一个elem函数,它标示一个给定的值是否出现在一个列表中。如果我们用前缀表示法来使用elem,它构成的代码相当易读。
In [7]:
elem 'a' "camogie"
如果我们换用中缀表示法,这段代码甚至会变得更容易理解。它清楚地标示我们正在检查左边的给定值是否出现在右边的列表里。
In [8]:
3 `elem` [1,2,4,8]
我们在Data.List模块的一些有用的函数中看到了更明显的改进(译注:这里是指中缀表示法改进了代码可读性)。isPrefixOf函数告诉我们一个列表是否匹配另一个列表的开始部分。
In [9]:
:module +Data.List
"foo" `isPrefixOf` "foobar"
相应地,isInfixOf和isSuffixOf函数匹配一个列表的中间和结尾处的任何地方。
In [10]:
"needle" `isInfixOf` "haystack full of needle thingies"
"end" `isSuffixOf` "the end"
没有一个硬性的规则指示你什么时候应该用中缀表示法或是前缀表示法,尽管使用前缀表示法要普遍得多。在具体情况下选择使你的代码更可读的那一种表示法就是最好的。
作为函数式编程的基本组件,列表应该得到足够的重视。Prelude定义了很多函数来处理列表。它们当中的许多是不可或缺的工具,所以及早学习它们是很重要的。
不管怎样,这一节将学习很多函数。为什么要马上展示这么多函数?因为这些函数既容易学而且会经常使用。如果我们不知道有这样的工具箱,那么时间将浪费在编写那些在标准库中已经存在的简单函数上。因此深入学习列表模块中的函数是非常值得的。
Data.List模块包含所有的列表函数。Prelude只不过重新导出了这些在Data.List模块中的函数的大部分。还有一些有用的函数并没有被Prelude重新导出。下面学习列表函数的时候,将明确地提到那些只在Data.List中出现的。
ghci> :module +Data.List
因为这些函数没有什么复杂的或者代码量超过三行的,所有我们对它们只做简单的描述。实际上,快速和有用的学习方法是记住它们是如何定义的。
length函数告诉我们一个列表中包含多少个元素。
In [11]:
:type length
length []
length [1,2,3]
length "strings are lists, too"
如果需要检查列表是不是空的,用null函数。
In [12]:
:type null
null []
null "plugh"
要访问列表的第一个元素,用head函数。
In [13]:
:type head
head [1,2,3]
相反,tail函数,返回列表中除了第一个其它所有的元素。
In [14]:
:type tail
tail "foo"
还有一个函数,last,返回列表的最后一个元素。
In [15]:
:type last
last "bar"
和last相反的是init,它返回列表中除了最后一个其它所有的元素。
In [16]:
:type init
init "bar"
上面的一些函数应用在空列表上时会报错,因此当不知道一个列表是否为空的时候要小心了。它们会报告什么样的错误呢?
In [17]:
head []
In [18]:
-- file: ch04/EfficientList.hs
myDumbExample xs = if length xs > 0
then head xs
else 'Z'
如果用过像Perl或者Python这样的编程语言,这段代码看起来就是一种很自然地编写测试的方式。在底层,Python和Perl中的列表都是数组。所以它们必定能通过调用len(foo)或者是scalar(@foo)得知列表(数组)的长度。但是基于很多别的原因,把这些假设照搬到Haskell中不是一个好主意。
我们已经看过列表的数据类型定义好多次了,知道一个列表不会明确地存储它本身的长度。因此length函数的工作方式是遍历整个列表。
所以当我们只关心一个列表是不是为空时,调用length不是一个好的策略。如果我们处理的是一个有限的列表,它潜在地做了比我们想象的更多的事情。因为Haskell很容易创建无限列表,所以不小心使用了length函数可能导致无限循环。
一个更合适的替代方案是调用null函数,它执行的次数是确定不变的。更好的是,使用null能使我们的代码明确地标示出我们真正关心的列表的属性。下面举两个更好的例子。
In [19]:
-- file: ch04/EfficientList.hs
mySmartExample xs = if not (null xs)
then head xs
else 'Z'
myOtherExample (x:_) = x
myOtherExample [] = 'Z'
更多简单列表操作
Haskell用(++)表示“追加”函数。
In [20]:
:type (++)
"foo" ++ "bar"
[] ++ [1,2,3]
[True] ++ []
concat函数取一个包含列表的列表,这些列表中的元素具有相同的类型,它把这些列表连接在一起成为一个单一的列表。
In [21]:
:type concat
concat [[1,2,3], [4,5,6]]
它会去掉一级的嵌套。(译注:每次调用concat会去除最外一层的方括号)
In [22]:
concat [[[1,2],[3]], [[4],[5],[6]]]
concat (concat [[[1,2],[3]], [[4],[5],[6]]])
reverse函数返回一个元素以相反的顺序排列的新列表。
In [23]:
:type reverse
reverse "foo"
针对包含Bool值的列表,and和or函数相当于用&&和||遍历这个列表并两两求值
In [24]:
:type and
and [True,False,True]
and []
:type or
or [False,False,False,True,False]
or []
还有两个与and和or功能近似的函数,all和any,它们操作任何类型的列表。每一个带着一个谓词作为它的第一个参数;如果谓词对列表中的每个元素的判断都为真,all函数返回True,当对列表中的每个元素的谓词至少有一个成功了,any函数返回True。
In [25]:
:type all
all odd [1,3,5]
all odd [3,1,4,1,5,9,2,6,5]
all odd []
:type any
any even [3,1,4,1,5,9,2,6,5]
any even []
In [26]:
:type take
take 3 "foobar"
take 2 [1]
:type drop
drop 3 "xyzzy"
drop 1 []
splitAt函数组合了take和drop的功能,返回由一个列表产生的二元组,两部分是由原来的列表根据给定的索引分割而成。
In [27]:
:type splitAt
splitAt 3 "foobar"
takeWhile和dropWhile函数带着谓词:takeWhile从开头遍历一个列表,抽取使谓词返回True的元素组成一个新列表;dropWhile则是把使谓词返回True的元素丢掉。(译注:这里的表述容易引起歧义,实际上两个函数都是走到第一个使谓词返回False的元素处就停止操作了,即使这个元素后面还有使谓词返回True的元素,两个函数也不再take或drop了)
In [28]:
:type takeWhile
takeWhile odd [1,3,5,6,8,9,11]
:type dropWhile
dropWhile even [2,4,6,7,9,10,12]
正如splitAt函数利用take和drop的结果组成一个二元组一样,break(已经在“热身:方便地分离多行文本”一节中看到过)和span函数利用takeWhile和dropWhile的结果组成二元组。
每个函数带着一个谓词,break提取列表中使谓词失败的元素组成二元组的首项,而span提取列表中使谓词成功的元素组成二元组的首项。
In [29]:
:type span
span even [2,4,6,7,9,10,11]
:type break
break even [1,3,5,6,8,9,10]
In [30]:
:type elem
2 `elem` [5,3,2,1,1]
2 `notElem` [5,3,2,1,1]
对于更普遍的搜索操作,filter函数带着一个谓词,返回列表中使谓词成功的每一个元素。
ghci> :type filter
filter :: (a -> Bool) -> [a] -> [a]
ghci> filter odd [2,4,1,3,6,8,5,7]
[1,3,5,7]
In [31]:
:type filter
filter odd [2,4,1,3,6,8,5,7]
在Data.List模块中,有三个谓词方法,isPrefixOf、isInfixOf和isSuffixOf,能让我们测试一下子列表在一个更大的列表中出现的位置。最容易的方式是把它们作为中缀使用。
isPrefixOf函数告诉我们左边的列表是否出现在右边的列表的开始处。
ghci> :module +Data.List
ghci> :type isPrefixOf
isPrefixOf :: (Eq a) => [a] -> [a] -> Bool
ghci> "foo" `isPrefixOf` "foobar"
True
ghci> [1,2] `isPrefixOf` []
False
In [32]:
:type isPrefixOf
"foo" `isPrefixOf` "foobar"
[1,2] `isPrefixOf` []
isInfixOf函数标示左边的列表是否是右边的列表的一个子列表。
ghci> :module +Data.List
ghci> [2,6] `isInfixOf` [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
True
ghci> "funk" `isInfixOf` "sonic youth"
False
In [33]:
:module +Data.List
[2,6] `isInfixOf` [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9]
"funk" `isInfixOf` "sonic youth"
isSuffixOf函数的功能不再赘述。
ghci> :module +Data.List
ghci> ".c" `isSuffixOf` "crashme.c"
True
In [34]:
".c" `isSuffixOf` "crashme.c"
In [35]:
:type zip
zip [12,72,93] "zippity"
更有用的是zipWith函数,它带两个列表作为参数并为从每个列表中抽取一个元素而组成的二元组提供一个函数,最后生成与较短的那个列表等长的新列表。
ghci> :type zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
ghci> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]
In [36]:
:type zipWith
zipWith (+) [1,2,3] [4,5,6]
In [37]:
lines "foo\nbar"
unlines ["foo", "bar"]
words函数利用任何空白字符分割一个字符串,它对应的函数,unwords,用一个空格字符把一个字符串构成的列表连接起来。
ghci> words "the \r quick \t brown\n\n\nfox"
["the","quick","brown","fox"]
ghci> unwords ["jumps", "over", "the", "lazy", "dog"]
"jumps over the lazy dog"
In [38]:
words "the \r quick \t brown\n\n\nfox"
words ""
unwords ["jumps", "over", "the", "lazy", "dog"]
-- file: ch04/ch04.exercises.hs
safeHead :: [a] -> Maybe a
safeTail :: [a] -> Maybe [a]
safeLast :: [a] -> Maybe a
safeInit :: [a] -> Maybe [a]
-- file: ch04/ch04.exercises.hs
splitWith :: (a -> Bool) -> [a] -> [[a]]
In [39]:
-- 1.
safeHead :: [a] -> Maybe a
safeHead (x:_) = Just x
safeHead [] = Nothing
safeHead []
safeHead [1,2,3]
safeTail :: [a] -> Maybe [a]
safeTail x
| not (null x) = Just (tail x)
| otherwise = Nothing
safeTail [1,2,3]
safeTail []
safeLast :: [a] -> Maybe a
safeLast x
| not (null x) = Just (last x)
| otherwise = Nothing
safeLast [1,2,3]
safeLast []
safeInit :: [a] -> Maybe [a]
safeInit x
| not (null x) = Just (init x)
| otherwise = Nothing
safeInit [1,2,3]
safeInit []
In [43]:
-- 2. 写一个和words功能近似的函数splitWith,要求带一个谓词和一个任意类型元素组成的列表,在使谓词返回False的元素处分割这个列表。
import Data.List (dropWhile,dropWhileEnd)
splitWith :: (a -> Bool) -> [a] -> [[a]]
splitWith f (x:xs) = (fst breaked:(splitWith f (snd breaked)))
where breaked = f `break` ( f `dropWhileEnd` (f `dropWhile` (x:xs)))
splitWith f _ = []
i1 = [1,1,2,3,4,5,6,1,1,6,5,4,3,2,1,1]
splitWith (==1) [1,1,1,1]
splitWith (==1) i1
splitWith (=='a') "aa is aa word aa"
In [41]:
-- 3. 利用在“一个简单的命令行框架”一节中创建的命令行框架,编写一个打印输入数据的每一个的第一个单词的程序。
In [42]:
-- 4. 编写一个转置一个文件中的文本的程序。比如,它应该把“hellonworldn”转换成“hwneonlrnllnodn”。
和传统编程语言不同, Haskell 既没有 for 循环,也没有 while 循环。那么,如果有一大堆数据要处理,该用什么代替这些循环呢?这一节就会给出这个问题的几种可能的解决办法。
通过例子进行比对,可以很直观地认识有 loop 语言和没 loop 语言之间的区别。以下是一个 C 函数,它将字符串表示的数字转换成整数:
int as_int(char *str)
{
int acc; // accumulate the partial result
for (acc = 0; isdigit(*str); str++){
acc = acc * 10 + (*str -'0');
}
return acc;
}
既然 Haskell 没有 loop 的话,以上这段 C 语言代码,在 Haskell 里该怎么表达呢?
让我们先从类型签名开始写起,这不是必须的,但它对于弄清楚代码在干什么很有帮助:
-- file: ch04/IntParse.hs
import Data.Char (digitToInt) -- we'll need ord shortly
asInt :: String -> Int
In [ ]:
C 代码在遍历字符串的过程中,渐增地计算结果。Haskell 代码同样可以做到这一点,而且,在 Haskell 里,使用函数已经足以表示 loop 计算了。[译注:在命令式语言里,很多迭代计算都是通过特殊关键字来实现的,比如 do 、 while 和 for 。]
-- file: ch04/IntParse.hs
loop :: Int -> String -> Int
asInt xs = loop 0 xs
In [ ]:
loop 的第一个参数是累积器的变量,给它赋值 0 等同于 C 语言在 for 循环开始前的初始化操作。
在研究详细的代码前,先来思考一下我们要处理的数据:输入 xs 是一个包含数字的字符串,而 String 类型不过是 [Char] 的别名,一个包含字符的列表。因此,要遍历处理字符串,最好的方法是将它看作是列表来处理:它要么就是一个空字符串;要么就是一个字符,后面跟着列表的其余部分。
以上的想法可以通过对列表的构造器进行模式匹配来表达。先从最简单的情况 —— 输入为空字符串开始:
-- file: ch04/IntParse.hs
loop acc [] = acc
In [ ]:
一个空列表并不仅仅意味着“输入列表为空”,另一种可能的情况是,对一个非空字符串进行遍历之后,最终到达了列表的末尾。因此,对于空列表,我们不是抛出错误,而是将累积值返回。
另一个等式处理列表不为空的情况:先取出并处理列表的当前元素,接着处理列表的其他元素。
-- file: ch04/IntParse.hs
loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
in loop acc' xs
In [ ]:
程序先计算出当前字符所代表的数值,将它赋值给局部变量 acc' 。然后使用 acc' 和剩余列表的元素 xs 作为参数,再次调用 loop 函数。这种调用等同于在 C 代码中再次执行一次循环。
每次递归调用 loop ,累积器的值都会被更新,并处理掉列表里的一个元素。这样一直下去,最终输入列表为空,递归调用结束。
以下是 IntParse 函数的完整定义:
-- file: ch04/IntParse.hs
-- 只载入 Data.Char 中的 digitToInt 函数
import Data.Char (digitToInt)
asInt xs = loop 0 xs
loop :: Int -> String -> Int
loop acc [] = acc
loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
in loop acc' xs
[译注:书本原来的代码少了对 Data.Char 的引用,会造成 digitToInt 查找失败。]
In [ ]:
在 ghci 里看看程序的表现如何:
Prelude> :load IntParse.hs
[1 of 1] Compiling Main ( IntParse.hs, interpreted )
Ok, modules loaded: Main.
*Main> asInt "33"
33
In [ ]:
在处理字符串表示的字符时,它运行得很好。不过,如果传给它一些不合法的输入,这个可怜的函数就没办法处理了:
*Main> asInt ""
0
*Main> asInt "potato"
*** Exception: Char.digitToInt: not a digit 'p'
In [ ]:
在练习一,我们会想办法解决这个问题。
loop 函数是尾递归函数的一个例子:如果输入非空,这个函数做的最后一件事,就是递归地调用自身。这个代码还展示了另一个惯用法:通过研究列表的结构,分别处理空列表和非空列表两种状况,这种方法称之为结构递归(structural recursion)。
非递归情形(列表为空)被称为“基本情形”(有时也叫终止情形)。当对函数进行递归调用时,计算最终会回到基本情形上。在数学上,这也称为“归纳情形”。
作为一项有用的技术,结构递归并不仅仅局限于列表,它也适用于其他代数数据类型,稍后就会介绍更多这方面的例子。
考虑以下 C 函数, square ,它对数组中的所有元素执行平方计算:
void square(double *out, const double *in, size_t length)
{
for (size_t i = 0; i < length; i++) {
out[i] = in[i] * in[i];
}
}
这段代码展示了一个直观且常见的 loop 动作,它对输入数组中的所有元素执行同样的动作。以下是 Haskell 版本的 square 函数:
-- file: ch04/square.hs
square :: [Double] -> [Double]
square (x:xs) = x*x : square xs
square [] = []
In [ ]:
square 函数包含两个模式匹配等式。第一个模式解构一个列表,取出它的 head 部分和 tail 部分,并对第一个元素进行加倍操作,然后将计算所得的新元素放进列表里面。一直这样做下去,直到处理完整个列表为止。第二个等式确保计算会在列表为空时顺利终止。
square 产生一个和输入列表一样长的新列表,其中每个新元素的值都是原本元素的平方:
Prelude> :load square.hs
[1 of 1] Compiling Main ( square.hs, interpreted )
Ok, modules loaded: Main.
*Main> let one_to_ten = [1.0 .. 10.0]
*Main> square one_to_ten
[1.0,4.0,9.0,16.0,25.0,36.0,49.0,64.0,81.0,100.0]
In [ ]:
以下是另一个 C 循环,它将字符串中的所有字母都设置为大写:
#include <ctype.h>
char *uppercase(const char *in)
{
char *out = strdup(in);
if (out != NULL) {
for (size_t i = 0; out[i] != '\0'; i++) {
out[i] = toupper(out[i]);
}
}
return out;
}
以下是相等的 Haskell 版本:
-- file: ch04/upperCase.hs
import Data.Char (toUpper)
upperCase :: String -> String
upperCase (x: xs) = toUpper x : upperCase xs
upperCase [] = []
In [ ]:
代码从 Data.Char 模块引入了 toUpper 函数,如果输入字符是一个字母的话,那么函数就将它转换成大写:
Prelude> :module +Data.Char
Prelude Data.Char> toUpper 'a'
'A'
Prelude Data.Char> toUpper 'A'
'A'
Prelude Data.Char> toUpper '1'
'1'
Prelude Data.Char> toUpper '*'
'*'
In [ ]:
upperCase 函数和之前的 square 函数很相似:如果输入是一个空列表,那么它就停止计算,返回一个空列表。另一方面,如果输入不为空,那么它就对列表的第一个元素调用 toUpper 函数,并且递归调用自身,继续处理剩余的列表元素:
Prelude> :load upperCase.hs
[1 of 1] Compiling Main ( upperCase.hs, interpreted )
Ok, modules loaded: Main.
*Main> upperCase "The quick brown fox jumps over the lazy dog"
"THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG"
In [ ]:
以上两个函数遵循了同一种处理列表的公共模式:基本情形处理(base case)空列表输入。而递归情形(recursive case)则处理列表非空时的情况,它对列表的头元素进行某种操作,然后递归地处理列表余下的其他元素。
前面定义的 square 和 upperCase 函数,都生成一个和输入列表同等长度的新列表,并且每次只对列表的一个元素进行处理。因为这种用法非常常见,所以 Haskell 的 Prelude 库定义了 map 函数来更方便地执行这种操作。 map 函数接受一个函数和一个列表作为参数,将输入函数应用到输入列表的每个元素上,并构建出一个新的列表。
以下是使用 map 重写的 square 和 upperCase 函数:
-- file: ch04/rewrite_by_map.hs
import Data.Char (toUpper)
square2 xs = map squareOne xs
where squareOne x = x * x
upperCase2 xs = map toUpper xs
[译注:原文代码没有载入 Data.Char 中的 toUpper 函数。]
In [ ]:
来研究一下 map 是如何实现的。通过查看它的类型签名,可以发现很多有意思的信息:
Prelude> :type map
map :: (a -> b) -> [a] -> [b]
类型签名显示, map 接受两个参数:第一个参数是一个函数,这个函数接受一个 a 类型的值,并返回一个 b 类型的值[译注:这里只是说 a 和 b 类型可能不一样,但不是必须的。]。
In [ ]:
像 map 这种接受一个函数作为参数、又或者返回一个函数作为结果的函数,被称为高阶函数。
因为 map 的抽象出现在 square 和 upperCase 函数,所以可以通过观察这两个函数,找出它们之间的共同点,然后实现自己的 map 函数:
-- file: ch04/myMap.hs
myMap :: (a -> b) -> [a] -> [b]
myMap f (x:xs) = f x : myMap f xs
myMap _ [] = []
[译注:在原文的代码里,第二个等式的定义为 myMap = [] ,这并不是完全正确的,因为它可以适配于第二个参数不为列表的情况,比如 myMap f 1 。因此,这里遵循标准库里 map 的定义,将第二个等式修改为 myMap _ [] = [] 。]
In [ ]:
在 ghci 测试这个 myMap 函数:
Prelude> :load myMap.hs
[1 of 1] Compiling Main ( myMap.hs, interpreted )
Ok, modules loaded: Main.
*Main> :module +Data.Char
*Main Data.Char> myMap toUpper "The quick brown fox"
"THE QUICK BROWN FOX"
通过观察代码,并从中提炼出重复的抽象,是复用代码的一种良好方法。尽管对代码进行抽象并不是 Haskell 的“专利”,但高阶函数使得这种抽象变得非常容易。
In [ ]:
另一种对列表的常见操作是,对列表元素进行筛选,只保留那些符合条件的元素。
以下函数接受一个列表作为参数,并返回这个列表里的所有奇数元素。代码的递归情形比之前的 map 函数要复杂一些,它使用守卫对元素进行条件判断,只有符合条件的元素,才会被加入进结果列表里:
-- file: ch04/oddList.hs
oddList :: [Int] -> [Int]
oddList (x:xs) | odd x = x : oddList xs
| otherwise = oddList xs
oddList [] = []
[译注:这里将原文代码的 oddList _ = [] 改为 oddList [] = [] ,原因和上一小节修改 map 函数的代码一样。]
In [ ]:
测试:
Prelude> :load oddList.hs
[1 of 1] Compiling Main ( oddList.hs, interpreted )
Ok, modules loaded: Main.
*Main> oddList [1 .. 10]
[1,3,5,7,9]
In [ ]:
因为这种过滤模式也很常见,所以 Prelude 也定义了相应的函数 filter :它接受一个谓词函数,并将它应用到列表里的每个元素,只有那些谓词函数求值返回 True 的元素才会被保留:
Prelude> :type odd
odd :: Integral a => a -> Bool
Prelude> odd 1
True
Prelude> odd 2
False
Prelude> :type filter
filter :: (a -> Bool) -> [a] -> [a]
Prelude> filter odd [1 .. 10]
[1,3,5,7,9]
[译注:谓词函数是指那种返回 Bool 类型值的函数。]
稍后的章节会介绍如何定义 filter 。
In [ ]:
In [ ]:
以下是一个稍微复杂一些的例子,它是一个 Adler-32 校验和的 JAVA 实现。Adler-32 是一个流行的校验和算法,它将两个 16 位校验和串联成一个 32 位校验和。第一个校验和是所有输入比特之和,加上一。而第二个校验和则是第一个校验和所有中间值之和。每次计算时,校验和都需要取模 65521 。(如果你不懂 JAVA ,直接跳过也没关系):
public class Adler32
{
private static final int base = 65521;
public static int compute(byte[] data, int offset, int length)
{
int a = 1, b = 0;
for (int i = offset; i < offset + length; i++) {
a = (a + (data[i] & oxff)) % base
b = (a + b) % base;
}
return (b << 16) | a;
}
}
尽管 Adler-32 是一个简单的校验和算法,但这个 JAVA 实现还是非常复杂,很难看清楚位操作之间的关系。
以下是 Adler-32 算法的 Haskell 实现:
-- file: ch04/Adler32.hs
import Data.Char (ord)
import Data.Bits (shiftL, (.&.), (.|.))
base = 65521
adler32 xs = helper 1 0 xs
where helper a b (x:xs) = let a' = (a + (ord x .&. 0xff)) `mod` base
b' = (a' + b) `mod` base
in helper a' b' xs
helper a b [] = (b `shiftL` 16) .|. a
在这段代码里, shiftL 函数实现逻辑左移, (.&.) 实现二进制位的并操作, (.|.) 实现二进制位的或操作, ord 函数则返回给定字符对应的编码值。
helper 函数通过尾递归来进行计算,每次对它的调用,都产生新的累积变量,效果等同于 JAVA 在 for 循环里对变量的赋值更新。当列表处理完毕,递归终止时,程序计算出校验和并将它返回。
和前面抽取出 map 和 filter 函数类似,从 Adler32 函数里面,我们也可以抽取出一种通用的抽象,称之为折叠(fold):它对一个列表中的所有元素做某种处理,并且一边处理元素,一边更新累积器,最后在处理完整个列表之后,返回累积器的值。
有两种不同类型的折叠,其中 foldl 从左边开始进行折叠,而 foldr 从右边开始进行折叠。
In [ ]:
In [ ]:
foldl 函数接受一个步骤(step)函数,一个累积器的初始化值,以及一个列表作为参数。步骤函数每次使用累积器和列表中的一个元素作为参数,并计算出新的累积器值,这个过程称为步进(stepper)。然后,将新的累积器作为参数,再次进行同样的计算,直到整个列表处理完为止。
以下是使用 foldl 重写的 mySum 函数:
-- file: ch04/foldlSum.hs
foldlSum xs = foldl step 0 xs
where step acc x = acc + x
In [ ]:
因为代码里的 step 函数执行的操作不过是相加起它的两个输入参数,因此,可以直接将一个加法函数代替 step 函数,并移除多余的 where 语句:
-- file: ch04/niceSum.hs
niceSum :: [Integer] -> Integer
niceSum xs = foldl (+) 0 xs
In [ ]:
为了进一步看清楚 foldl 的执行模式,以下代码展示了 niceSum [1, 2, 3] 执行时的计算过程:
niceSum [1, 2, 3]
== foldl (+) 0 (1:2:3:[])
== foldl (+) (0 + 1) (2:3:[])
== foldl (+) ((0 + 1) + 2) (3:[])
== foldl (+) (((0 + 1) + 2) + 3) []
== (((0 + 1) + 2) + 3)
注意对比新的 mySum 定义比刚开始的定义节省了多少代码:新版本没有使用显式递归,因为 foldl 可以代替我们搞定了关于循环的一切。现在程序只要求我们回答两个问题:第一,累积器的初始化值是什么(foldl 的第二个参数);第二,怎么更新累积器的值((+) 函数)。
In [ ]:
回顾一下之前的几个例子,可以看出,使用 fold 和 map 等高阶函数定义的函数,比起显式使用递归的函数,并不总是能节约大量代码。那么,我们为什么要使用这些函数呢?
答案是,因为它们在 Haskell 中非常通用,并且这些函数都带有正确的、可预见的行为。
这意味着,即使是一个 Haskell 新手,他/她理解起 fold 通常都要比理解显式递归要容易。一个 fold 并不产生任何意外动作,但一个显式递归函数的所做作为,通常并不是那么显而易见的。
以上观点同样适用于其他高阶函数库,包括前面介绍过的 map 和 filter 。因为这些函数都带有定义良好的行为,我们只需要学习怎样使用这些函数一次,以后每次碰到使用这些函数的代码,这些知识都可以加快我们对代码的理解。这种优势同样体现在代码的编写上:一旦我们能熟练使用高阶函数,那么写出更简洁的代码自然就不在话下。
和 foldl 相对应的是 foldr ,它从一个列表的右边开始进行折叠。
-- file: ch04/foldr.hs
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _ zero [] = zero
[译注:这个函数在载入 ghci 时会因为命名冲突而被拒绝,编写函数直接使用内置的 foldr 就可以了。]
In [ ]:
可以用 foldr 改写在《左折叠》一节定义的 niceSum 函数:
-- file: ch04/niceSumFoldr.hs
niceSumFoldr :: [Int] -> Int
niceSumFoldr xs = foldr (+) 0 xs
In [ ]:
这个 niceSumFoldr 函数在输入为 [1, 2, 3] 时,产生以下计算序列:
niceSumFoldr [1, 2, 3]
== foldr (+) 0 (1:2:3[])
== 1 + foldr (+) 0 (2:3:[])
== 1 + (2 + foldr (+) 0 (3:[]))
== 1 + (2 + (3 + foldr (+) 0 []))
== 1 + (2 + (3 + 0))
可以通过观察括号的包围方式,以及累积器初始化值摆放的位置,来区分 foldl 和 foldr :foldl 将处初始化值放在左边,括号也是从左边开始包围。另一方面,foldr 将初始化值放在右边,而括号也是从右边开始包围。
In [ ]:
还记得当年大明湖畔的 filter 函数吗?它可以用显式递归来定义:
-- file: ch04/filter.hs
filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
[译注:这个函数在载入 ghci 时会因为命名冲突而被拒绝,编写函数直接使用内置的 filter 就可以了。]
In [ ]:
除此之外, filter 还可以通过 foldr 来定义:
-- file: ch04/myFilter.hs
myFilter p xs = foldr step [] xs
where step x ys | p x = x : ys
| otherwise = ys
来仔细分析一下 myFilter 函数的定义:和 foldl 一样, foldr 也接受一个函数、一个基本情形和一个列表作为参数。通过阅读 filter 函数的类型签名可以得知, myFilter 函数的输入和输出都使用同类型的列表,因此函数的基本情形,以及局部函数 step ,都必须返回这个类型的列表。
myFilter 里的 foldr 每次取出列表中的一个元素,并对他进行处理,如果这个元素经过条件判断为 True ,那么就将它放进累积的新列表里面,否则,它就略过这个元素,继续处理列表的其他剩余元素。
In [ ]:
所有可以用 foldr 定义的函数,统称为主递归(primitive recursive)。很大一部分列表处理函数都是主递归函数。比如说, map 就可以用 foldr 定义:
-- file: ch04/myFoldrMap.hs
myFoldrMap :: (a -> b) -> [a] -> [b]
myFoldrMap f xs = foldr step [] xs
where step x xs = f x : xs
In [ ]:
更让人惊奇的是, foldl 甚至可以用 foldr 来表示:
-- file: ch04/myFoldl.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
一种思考 foldr 的方式是,将它看成是对输入列表的一种转换(transform):它的第一个参数决定了该怎么处理列表的 head 和 tail 部分;而它的第二个参数则决定了,当遇到空列表时,该用什么值来代替这个空列表。
In [ ]:
用 foldr 定义的恒等(identity)转换,在列表为空时,返回空列表本身;如果列表不为空,那么它就将列表构造器 (:) 应用于每个 head 和 tail 对(pair):
-- file: ch04/identity.hs
identity :: [a] -> [a]
identity xs = foldr (:) [] xs
In [ ]:
最终产生的结果列表和原输入列表一模一样:
Prelude> :load identity.hs
[1 of 1] Compiling Main ( identity.hs, interpreted )
Ok, modules loaded: Main.
*Main> identity [1, 2, 3]
[1,2,3]
In [ ]:
如果将 identity 函数定义中,处理空列表时返回的 [] 改为另一个列表,那么我们就得到了列表追加函数 append :
-- file: ch04/append.hs
append :: [a] -> [a] -> [a]
append xs ys = foldr (:) ys xs
测试:
Prelude> :load append.hs
[1 of 1] Compiling Main ( append.hs, interpreted )
Ok, modules loaded: Main.
*Main> append "the quick " "fox"
"the quick fox"
In [ ]:
这个函数的效果等同于 (++) 操作符:
*Main> "the quick " ++ "fox"
"the quick fox"
append 函数依然对每个列表元素使用列表构造器,但是,当第一个输入列表为空时,它将第二个输入列表(而不是空列表元素)拼接到第一个输入列表的表尾。
通过前面这些例子对 foldr 的介绍,我们应该可以了解到, foldr 函数和《列表处理》一节所介绍的基本列表操作函数一样重要。由于 foldr 可以增量地处理和产生列表,所以它对于惰性数据处理也非常有用。
In [ ]:
为了简化讨论,本节的例子通常都使用 foldl 来进行,这对于普通的测试是没有问题的,但是,千万不要把 foldl 用在实际使用中。
这样做是因为, Haskell 使用的是非严格求值。如果我们仔细观察 foldl (+) [1, 2, 3] 的执行过程,就可以会从中看出一些问题:
foldl (+) 0 (1:2:3:[])
== foldl (+) (0 + 1) (2:3:[])
== foldl (+) ((0 + 1) + 2) (3:[])
== foldl (+) (((0 + 1) + 2) + 3) []
== (((0 + 1) + 2) + 3)
除非被显式地要求,否则最后的表达式不会被求值为 6 。在表达式被求值之前,它会被保存在块里面。保存一个块比保存单独一个数字要昂贵得多,而被块保存的表达式越复杂,这个块占用的空间就越多。对于数值计算这样的廉价操作来说,块保存这种表达式所需的计算量,比直接求值这个表达式所需的计算量还多。最终,我们既浪费了时间,又浪费了金钱。
In [ ]:
在 GHC 中,对块中表达式的求值在一个内部栈中进行。因为块中的表达式可能是无限大的,而 GHC 为栈设置了有限大的的容量,多得这个限制,我们可以在 ghci 里尝试求值一个大的块,而不必担心消耗掉全部内存。
[译注:使用栈来执行一些可能无限大的操作,是一种常见优化和保护技术。这种用法减少了操作系统显式的上下文切换,而且就算计算量超出栈可以容纳的范围,那么最坏的结果就是栈崩溃,而如果直接使用系统内存,一旦请求超出内存可以容纳的范围,可能会造成整个程序崩溃,甚至影响系统的稳定性。]
Prelude> foldl (+) 0 [1..1000]
500500
可以推测出,在上面的表达式被求值之前,它创建了一个保存 1000 个数字和 999 个 (+) 操作的块。单单为了表示一个数字,我们就用了非常多的内存和 CPU !
[译注:这些块到底有多大?算算就知道了:对于每一个加法表达式,比如 x + y ,都要使用一个块来保存。而这种操作在 foldl (+) 0 [1..1000] 里要执行 999 次,因此一共有 999 个块被创建,这些块都保存着像 x + y 这样的表达式。]
对于一个更大的表达式 —— 尽管它并不是真的非常庞大, foldl 的执行会失败:
ghci> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
对于小的表达式来说, foldl 可以给出正确的答案,但是,因为过度的块资源占用,它运行非常缓慢。我们称这种现象为内存泄漏(space leak):代码可以正确地执行,但它占用了比实际所需多得多的内存。
对于大的表达式来说,带有内存泄漏的代码会造成运行失败,就像前面例子展示的那样。
内存泄漏是 Haskell 新手常常会遇到的问题,幸好的是,它非常容易避免。Data.List 模块定义了一个 foldl' 函数,它和 foldl 的作用类似,唯一的区别是, foldl' 并不创建块。以下的代码直观地展示了它们的区别:
ghci> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
ghci> :module +Data.List
ghci> foldl' (+) 0 [1..1000000]
500000500000
综上所述,最好不要在实际代码中使用 foldl :即使计算不失败,它的效率也好不到那里去。更好的办法是,使用 Data.List 里面的 foldl' 来代替。
[译注:在我的电脑上,超出内存的 foldl 失败方式和书本列出的并不一样:
Prelude> foldl (+) 0 [1..1000000000]
<interactive>: internal error: getMBlock: mmap: Operation not permitted
(GHC version 7.4.2 for i386_unknown_linux)
Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug
已放弃
从错误信息看, GHC/GHCi 处理 foldl 的方式应该已经发生了变化。
如果使用 foldl' 来执行计算,就不会出现任何问题:
Prelude> :module +Data.List
Prelude Data.List> foldl' (+) 0 [1..1000000000]
500000000500000000
就是这样。
A tutorial on the universality and expressiveness of fold 是一篇关于 fold 的优秀且深入的文章。它使用了很多例子来展示如何通过简单的系统化计算技术,将一些显式递归的函数转换成 fold 。
In [ ]:
In [ ]:
在 Haskell 中,匿名函数以反斜杠符号 \ 为开始,后跟函数的参数(可以包含模式),而函数体定义在 -> 符号之后。其中, \ 符号读作 lambda 。
以下是前面的 isInAny 函数用 lambda 改写的版本:
-- file: ch04/isInAny2.hs
import Data.List (isInfixOf)
isInAny2 needle haystack = any (\s -> needle `isInfixOf` s) haystack
定义使用括号包裹了整个匿名函数,确保 Haskell 可以知道匿名函数体在那里结束。
In [ ]:
匿名函数各个方面的行为都和带名称的函数基本一致,但是,匿名函数的定义受到几个严格的限制,其中最重要的一点是:普通函数可以通过多条语句来定义,而 lambda 函数的定义只能有一条语句。
只能使用一条语句的局限性,限制了在 lambda 定义中可使用的模式。一个普通函数,通常要使用多条定义,来覆盖各种不同的模式:
-- file: ch04/safeHead.hs
safeHead (x:_) = Just x
safeHead [] = Nothing
而 lambda 只能覆盖其中一种情形:
-- file ch04/unsafeHead.hs
unsafeHead = \(x:_) -> x
如果一不小心,将这个函数应用到错误的模式上,它就会给我们带来麻烦:
Prelude> :load unsafeHead.hs
[1 of 1] Compiling Main ( unsafeHead.hs, interpreted )
Ok, modules loaded: Main.
*Main> :type unsafeHead
unsafeHead :: [t] -> t
*Main> unsafeHead [1]
1
*Main> unsafeHead []
*** Exception: unsafeHead.hs:2:14-24: Non-exhaustive patterns in lambda
因为这个 lambda 定义是完全合法的,它的类型也没有错误,所以它可以被顺利编译,而最终在运行期产生错误。这个故事说明,如果你要在 lambda 函数里使用模式,请千万小心,必须确保你的模式不会匹配失败。
另外需要注意的是,在前面定义的 isInAny 函数和 isInAny2 函数里,带有辅助函数的 isInAny 要比使用 lambda 的 isInAny2 要更具可读性。带有名字的辅助函数不会破坏程序的代码流(flow),而且它的名字也可以传达更多的相关信息。
相反,当在一个函数定义里面看到 lambda 时,我们必须慢下来,仔细阅读这个匿名函数的定义,弄清楚它都干了些什么。为了程序的可读性和可维护性考虑,我们在很多情况下都会避免使用 lambda 。
当然,这并不是说 lambda 函数完全没用,只是在使用它们的时候,必须小心谨慎。
很多时候,部分应用函数可以很好地代替 lambda 函数,避免不必要的函数定义,粘合起不同的函数,并产生更清晰和更可读的代码。下一节就会介绍部分应用函数。
In [ ]:
在前面章节定义的函数中,很多函数都带有一个简单的辅助函数:
-- file: ch04/isInAny.hs
import Data.List (isInfixOf)
isInAny needle haystack = any inSequence haystack
where inSequence s = needle `isInfixOf` s
Haskell 允许我们编写完全匿名的函数,这样就不必再费力地为辅助函数想名字了。因为匿名函数从 lambda 演算而来,所以匿名函数通常也被称为 lambda 函数。
在 Haskell 中,匿名函数以反斜杠符号 \ 为开始,后跟函数的参数(可以包含模式),而函数体定义在 -> 符号之后。其中, \ 符号读作 lambda 。
In [ ]:
以下是前面的 isInAny 函数用 lambda 改写的版本:
-- file: ch04/isInAny2.hs
import Data.List (isInfixOf)
isInAny2 needle haystack = any (\s -> needle `isInfixOf` s) haystack
定义使用括号包裹了整个匿名函数,确保 Haskell 可以知道匿名函数体在那里结束。
匿名函数各个方面的行为都和带名称的函数基本一致,但是,匿名函数的定义受到几个严格的限制,其中最重要的一点是:普通函数可以通过多条语句来定义,而 lambda 函数的定义只能有一条语句。
In [ ]:
只能使用一条语句的局限性,限制了在 lambda 定义中可使用的模式。一个普通函数,通常要使用多条定义,来覆盖各种不同的模式:
-- file: ch04/safeHead.hs
safeHead (x:_) = Just x
safeHead [] = Nothing
In [ ]:
而 lambda 只能覆盖其中一种情形:
-- file ch04/unsafeHead.hs
unsafeHead = \(x:_) -> x
In [ ]:
如果一不小心,将这个函数应用到错误的模式上,它就会给我们带来麻烦:
Prelude> :load unsafeHead.hs
[1 of 1] Compiling Main ( unsafeHead.hs, interpreted )
Ok, modules loaded: Main.
*Main> :type unsafeHead
unsafeHead :: [t] -> t
*Main> unsafeHead [1]
1
*Main> unsafeHead []
*** Exception: unsafeHead.hs:2:14-24: Non-exhaustive patterns in lambda
因为这个 lambda 定义是完全合法的,它的类型也没有错误,所以它可以被顺利编译,而最终在运行期产生错误。这个故事说明,如果你要在 lambda 函数里使用模式,请千万小心,必须确保你的模式不会匹配失败。
另外需要注意的是,在前面定义的 isInAny 函数和 isInAny2 函数里,带有辅助函数的 isInAny 要比使用 lambda 的 isInAny2 要更具可读性。带有名字的辅助函数不会破坏程序的代码流(flow),而且它的名字也可以传达更多的相关信息。
相反,当在一个函数定义里面看到 lambda 时,我们必须慢下来,仔细阅读这个匿名函数的定义,弄清楚它都干了些什么。为了程序的可读性和可维护性考虑,我们在很多情况下都会避免使用 lambda 。
当然,这并不是说 lambda 函数完全没用,只是在使用它们的时候,必须小心谨慎。
很多时候,部分应用函数可以很好地代替 lambda 函数,避免不必要的函数定义,粘合起不同的函数,并产生更清晰和更可读的代码。下一节就会介绍部分应用函数。
In [ ]: