第四章：函數(shù)式編程
第四章：函數(shù)式編程
使用 Haskell 思考
初學(xué) Haskell 的人需要邁過兩個難關(guān)：
首先，我們需要將自己的編程觀念從命令式語言轉(zhuǎn)換到函數(shù)式語言上面來。這樣做的原因并不是因為命令式語言不好，而是因為比起命令式語言，函數(shù)式語言更勝一籌。
其次，我們需要熟悉 Haskell 的標(biāo)準(zhǔn)庫。和其他語言一樣，函數(shù)庫可以像杠桿那樣，極大地提升我們解決問題的能力。因為 Haskell 是一門層次非常高的語言，而 Haskell 的標(biāo)準(zhǔn)庫也趨向于處理高層次的抽象，因此對 Haskell 標(biāo)準(zhǔn)庫的學(xué)習(xí)也稍微更難一些，但這些努力最終都會物有所值。
這一章會介紹一些常用的函數(shù)式編程技術(shù)，以及一些 Haskell 特性。還會在命令式語言和函數(shù)式語言之間進(jìn)行對比，幫助讀者了解它們之間的區(qū)別，并且在這個過程中，陸續(xù)介紹一些基本的 Haskell 標(biāo)準(zhǔn)庫。
一個簡單的命令行程序
在本章的大部分時間里，我們都只和無副作用的代碼打交道。為了將注意力集中在實際的代碼上，我們需要開發(fā)一個接口程序，連接起帶副作用的代碼和無副作用的代碼。
這個接口程序讀入一個文件，將函數(shù)應(yīng)用到文件，并且將結(jié)果寫到另一個文件：
-- 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 關(guān)鍵字引入一個塊，標(biāo)識那些帶有副作用的代碼，比如對文件進(jìn)行讀和寫操作。被 do 包圍的 <- 操作符效果等同于賦值。第七章還會介紹更多 I/O 方面的函數(shù)。
當(dāng)我們需要測試其他函數(shù)的時候，我們就將程序中的 id 換成其他函數(shù)的名字。另外，這些被測試的函數(shù)的類型包含 String->String ，也即是，這些函數(shù)應(yīng)該都接受并返回字符串值。
[譯注： id 函數(shù)接受一個值，并原封不動地返回這個值，比如 id"hello" 返回值 "hello" ，而 id10 返回值 10 。]
[譯注：這一段最后一句的原文是“ ... need to have the type String->String ... ” ，因為 Haskell 是一種帶有類型多態(tài)的語言，所以將“ have the type ” 翻譯成 “ 包含 xx 類型 ”，而不是 “ 必須是 xx 類型 ”。
接下來編譯這個程序：
$ ghc --make InteractWith
[1 of 1] Compiling Main ( InteractWith.hs, InteractWith.o )
Linking InteractWith ...
通過命令行運行這個程序。它接受兩個文件名作為參數(shù)輸入，一個用于讀取，一個用于寫入：
$ 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
[譯注：原書這里的執(zhí)行過程少了寫入內(nèi)容到 hello-in.txt 的一步，導(dǎo)致執(zhí)行會出錯，所以這里加上 echo... 這一步。另外原書執(zhí)行的是 Interact 過程，也是錯誤的，正確的執(zhí)行文件名應(yīng)該是 InteractWith 。]
循環(huán)的表示
和傳統(tǒng)編程語言不同， Haskell 既沒有 for 循環(huán)，也沒有 while 循環(huán)。那么，如果有一大堆數(shù)據(jù)要處理，該用什么代替這些循環(huán)呢？這一節(jié)就會給出這個問題的幾種可能的解決辦法。
顯式遞歸
通過例子進(jìn)行比對，可以很直觀地認(rèn)識有 loop 語言和沒 loop 語言之間的區(qū)別。以下是一個 C 函數(shù)，它將字符串表示的數(shù)字轉(zhuǎn)換成整數(shù)：
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 里該怎么表達(dá)呢？
讓我們先從類型簽名開始寫起，這不是必須的，但它對于弄清楚代碼在干什么很有幫助：
-- file: ch04/IntParse.hs
import Data.Char (digitToInt) -- we'll need ord shortly
asInt :: String -> Int
C 代碼在遍歷字符串的過程中，漸增地計算結(jié)果。Haskell 代碼同樣可以做到這一點，而且，在 Haskell 里，使用函數(shù)已經(jīng)足以表示 loop 計算了。[譯注：在命令式語言里，很多迭代計算都是通過特殊關(guān)鍵字來實現(xiàn)的，比如 do 、 while 和 for 。]
-- file: ch04/IntParse.hs
loop :: Int -> String -> Int
asInt xs = loop 0 xs
loop 的第一個參數(shù)是累積器的變量，給它賦值 0 等同于 C 語言在 for 循環(huán)開始前的初始化操作。
在研究詳細(xì)的代碼前，先來思考一下我們要處理的數(shù)據(jù)：輸入 xs 是一個包含數(shù)字的字符串，而 String 類型不過是 [Char] 的別名，一個包含字符的列表。因此，要遍歷處理字符串，最好的方法是將它看作是列表來處理：它要么就是一個空字符串；要么就是一個字符，后面跟著列表的其余部分。
以上的想法可以通過對列表的構(gòu)造器進(jìn)行模式匹配來表達(dá)。先從最簡單的情況 —— 輸入為空字符串開始：
-- file: ch04/IntParse.hs
loop acc [] = acc
一個空列表并不僅僅意味著“輸入列表為空”，另一種可能的情況是，對一個非空字符串進(jìn)行遍歷之后，最終到達(dá)了列表的末尾。因此，對于空列表，我們不是拋出錯誤，而是將累積值返回。
另一個等式處理列表不為空的情況：先取出并處理列表的當(dāng)前元素，接著處理列表的其他元素。
-- file: ch04/IntParse.hs
loop acc (x:xs) = let acc' = acc * 10 + digitToInt x
in loop acc' xs
程序先計算出當(dāng)前字符所代表的數(shù)值，將它賦值給局部變量 acc' 。然后使用 acc' 和剩余列表的元素 xs 作為參數(shù)，再次調(diào)用 loop 函數(shù)。這種調(diào)用等同于在 C 代碼中再次執(zhí)行一次循環(huán)。
每次遞歸調(diào)用 loop ，累積器的值都會被更新，并處理掉列表里的一個元素。這樣一直下去，最終輸入列表為空，遞歸調(diào)用結(jié)束。
以下是 IntParse 函數(shù)的完整定義：
-- file: ch04/IntParse.hs
-- 只載入 Data.Char 中的 digitToInt 函數(shù)
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 查找失敗。]
在 ghci 里看看程序的表現(xiàn)如何：
Prelude> :load IntParse.hs
[1 of 1] Compiling Main ( IntParse.hs, interpreted )
Ok, modules loaded: Main.
*Main> asInt "33"
33
在處理字符串表示的字符時，它運行得很好。不過，如果傳給它一些不合法的輸入，這個可憐的函數(shù)就沒辦法處理了：
*Main> asInt ""
0
*Main> asInt "potato"
*** Exception: Char.digitToInt: not a digit 'p'
在練習(xí)一，我們會想辦法解決這個問題。
loop 函數(shù)是尾遞歸函數(shù)的一個例子：如果輸入非空，這個函數(shù)做的最后一件事，就是遞歸地調(diào)用自身。這個代碼還展示了另一個慣用法：通過研究列表的結(jié)構(gòu)，分別處理空列表和非空列表兩種狀況，這種方法稱之為結(jié)構(gòu)遞歸（structural recursion）。
非遞歸情形（列表為空）被稱為“基本情形”（有時也叫終止情形）。當(dāng)對函數(shù)進(jìn)行遞歸調(diào)用時，計算最終會回到基本情形上。在數(shù)學(xué)上，這也稱為“歸納情形”。
作為一項有用的技術(shù)，結(jié)構(gòu)遞歸并不僅僅局限于列表，它也適用于其他代數(shù)數(shù)據(jù)類型，稍后就會介紹更多這方面的例子。
對列表元素進(jìn)行轉(zhuǎn)換
考慮以下 C 函數(shù)， square ，它對數(shù)組中的所有元素執(zhí)行平方計算：
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 動作，它對輸入數(shù)組中的所有元素執(zhí)行同樣的動作。以下是 Haskell 版本的 square 函數(shù)：
-- file: ch04/square.hs
square :: [Double] -> [Double]
square (x:xs) = x*x : square xs
square [] = []
square 函數(shù)包含兩個模式匹配等式。第一個模式解構(gòu)一個列表，取出它的 head 部分和 tail 部分，并對第一個元素進(jìn)行加倍操作，然后將計算所得的新元素放進(jìn)列表里面。一直這樣做下去，直到處理完整個列表為止。第二個等式確保計算會在列表為空時順利終止。
square 產(chǎn)生一個和輸入列表一樣長的新列表，其中每個新元素的值都是原本元素的平方：
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]
以下是另一個 C 循環(huán)，它將字符串中的所有字母都設(shè)置為大寫：
#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 [] = []
代碼從 Data.Char 模塊引入了 toUpper 函數(shù)，如果輸入字符是一個字母的話，那么函數(shù)就將它轉(zhuǎn)換成大寫：
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 '*'
'*'
upperCase 函數(shù)和之前的 square 函數(shù)很相似：如果輸入是一個空列表，那么它就停止計算，返回一個空列表。另一方面，如果輸入不為空，那么它就對列表的第一個元素調(diào)用 toUpper 函數(shù)，并且遞歸調(diào)用自身，繼續(xù)處理剩余的列表元素：
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"
以上兩個函數(shù)遵循了同一種處理列表的公共模式：基本情形處理（base case）空列表輸入。而遞歸情形（recursive case）則處理列表非空時的情況，它對列表的頭元素進(jìn)行某種操作，然后遞歸地處理列表余下的其他元素。
列表映射
前面定義的 square 和 upperCase 函數(shù)，都生成一個和輸入列表同等長度的新列表，并且每次只對列表的一個元素進(jìn)行處理。因為這種用法非常常見，所以 Haskell 的 Prelude 庫定義了 map 函數(shù)來更方便地執(zhí)行這種操作。 map 函數(shù)接受一個函數(shù)和一個列表作為參數(shù)，將輸入函數(shù)應(yīng)用到輸入列表的每個元素上，并構(gòu)建出一個新的列表。
以下是使用 map 重寫的 square 和 upperCase 函數(shù)：
-- 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 函數(shù)。]
來研究一下 map 是如何實現(xiàn)的。通過查看它的類型簽名，可以發(fā)現(xiàn)很多有意思的信息：
Prelude> :type map
map :: (a -> b) -> [a] -> [b]
類型簽名顯示， map 接受兩個參數(shù)：第一個參數(shù)是一個函數(shù)，這個函數(shù)接受一個 a 類型的值，并返回一個 b 類型的值[譯注：這里只是說 a 和 b 類型可能不一樣，但不是必須的。]。
像 map 這種接受一個函數(shù)作為參數(shù)、又或者返回一個函數(shù)作為結(jié)果的函數(shù)，被稱為高階函數(shù)。
因為 map 的抽象出現(xiàn)在 square 和 upperCase 函數(shù)，所以可以通過觀察這兩個函數(shù)，找出它們之間的共同點，然后實現(xiàn)自己的 map 函數(shù)：
-- file: ch04/myMap.hs
myMap :: (a -> b) -> [a] -> [b]
myMap f (x:xs) = f x : myMap f xs
myMap _ [] = []
[譯注：在原文的代碼里，第二個等式的定義為 myMap_=[] ，這并不是完全正確的，因為它可以適配于第二個參數(shù)不為列表的情況，比如 myMapf1 。因此，這里遵循標(biāo)準(zhǔn)庫里 map 的定義，將第二個等式修改為 myMap[]=[] 。]
在 ghci 測試這個 myMap 函數(shù)：
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"
通過觀察代碼，并從中提煉出重復(fù)的抽象，是復(fù)用代碼的一種良好方法。盡管對代碼進(jìn)行抽象并不是 Haskell 的“專利”，但高階函數(shù)使得這種抽象變得非常容易。
篩選列表元素 另一種對列表的常見操作是，對列表元素進(jìn)行篩選，只保留那些符合條件的元素。 以下函數(shù)接受一個列表作為參數(shù)，并返回這個列表里的所有奇數(shù)元素。代碼的遞歸情形比之前的 map 函數(shù)要復(fù)雜一些，它使用守衛(wèi)對元素進(jìn)行條件判斷，只有符合條件的元素，才會被加入進(jìn)結(jié)果列表里：
-- file: ch04/oddList.hs
oddList :: [Int] -> [Int]
oddList (x:xs) | odd x = x : oddList xs
| otherwise = oddList xs
oddList [] = []
[譯注：這里將原文代碼的 oddList_=[] 改為 oddList[]=[] ，原因和上一小節(jié)修改 map 函數(shù)的代碼一樣。]
測試：
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]
因為這種過濾模式也很常見，所以 Prelude 也定義了相應(yīng)的函數(shù) filter ：它接受一個謂詞函數(shù)，并將它應(yīng)用到列表里的每個元素，只有那些謂詞函數(shù)求值返回 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]
[譯注：謂詞函數(shù)是指那種返回 Bool 類型值的函數(shù)。]
稍后的章節(jié)會介紹如何定義 filter 。
處理收集器并得出結(jié)果
將一個收集器（collection）簡化（reduce）為一個值也是收集器的常見操作之一。
對列表的所有元素求和，就是其中的一個例子：
-- file: ch04/mySum.hs
mySum xs = helper 0 xs
where helper acc (x:xs) = helper (acc + x) xs
helper acc [] = acc
helper 函數(shù)通過尾遞歸進(jìn)行計算。 acc 是累積器參數(shù)，它記錄了當(dāng)前列表元素的總和。正如我們在 asInt 函數(shù)看到的那樣，這種遞歸計算是純函數(shù)語言里表示 loop 最自然的方式。
以下是一個稍微復(fù)雜一些的例子，它是一個 Adler-32 校驗和的 JAVA 實現(xiàn)。Adler-32 是一個流行的校驗和算法，它將兩個 16 位校驗和串聯(lián)成一個 32 位校驗和。第一個校驗和是所有輸入比特之和，加上一。而第二個校驗和則是第一個校驗和所有中間值之和。每次計算時，校驗和都需要取模 65521 。（如果你不懂 JAVA ，直接跳過也沒關(guān)系）：
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 實現(xiàn)還是非常復(fù)雜，很難看清楚位操作之間的關(guān)系。
以下是 Adler-32 算法的 Haskell 實現(xiàn)：
-- 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 函數(shù)實現(xiàn)邏輯左移， (.&.) 實現(xiàn)二進(jìn)制位的并操作， (.|.) 實現(xiàn)二進(jìn)制位的或操作， ord 函數(shù)則返回給定字符對應(yīng)的編碼值。
helper 函數(shù)通過尾遞歸來進(jìn)行計算，每次對它的調(diào)用，都產(chǎn)生新的累積變量，效果等同于 JAVA 在 for 循環(huán)里對變量的賦值更新。當(dāng)列表處理完畢，遞歸終止時，程序計算出校驗和并將它返回。
和前面抽取出 map 和 filter 函數(shù)類似，從 Adler32 函數(shù)里面，我們也可以抽取出一種通用的抽象，稱之為折疊（fold）：它對一個列表中的所有元素做某種處理，并且一邊處理元素，一邊更新累積器，最后在處理完整個列表之后，返回累積器的值。
有兩種不同類型的折疊，其中 foldl 從左邊開始進(jìn)行折疊，而 foldr 從右邊開始進(jìn)行折疊。
左折疊
以下是 foldl 函數(shù)的定義：
-- file: ch04/foldl.hs
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step zero (x:xs) = foldl step (step zero x) xs
foldl _ zero [] = zero
[譯注：這個函數(shù)在載入 ghci 時會因為命名沖突而被拒絕，編寫函數(shù)直接使用內(nèi)置的 foldl 就可以了。]
foldl 函數(shù)接受一個步驟（step）函數(shù)，一個累積器的初始化值，以及一個列表作為參數(shù)。步驟函數(shù)每次使用累積器和列表中的一個元素作為參數(shù)，并計算出新的累積器值，這個過程稱為步進(jìn)（stepper）。然后，將新的累積器作為參數(shù)，再次進(jìn)行同樣的計算，直到整個列表處理完為止。
以下是使用 foldl 重寫的 mySum 函數(shù)：
-- file: ch04/foldlSum.hs
foldlSum xs = foldl step 0 xs
where step acc x = acc + x
因為代碼里的 step 函數(shù)執(zhí)行的操作不過是相加起它的兩個輸入?yún)?shù)，因此，可以直接將一個加法函數(shù)代替 step 函數(shù)，并移除多余的 where 語句：
-- file: ch04/niceSum.hs
niceSum :: [Integer] -> Integer
niceSum xs = foldl (+) 0 xs
為了進(jìn)一步看清楚 foldl 的執(zhí)行模式，以下代碼展示了 niceSum[1,2,3] 執(zhí)行時的計算過程：
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 定義比剛開始的定義節(jié)省了多少代碼：新版本沒有使用顯式遞歸，因為 foldl 可以代替我們搞定了關(guān)于循環(huán)的一切?，F(xiàn)在程序只要求我們回答兩個問題：第一，累積器的初始化值是什么（foldl 的第二個參數(shù)）；第二，怎么更新累積器的值（(+) 函數(shù)）。
為什么使用 fold 、 map 和 filter ？
回顧一下之前的幾個例子，可以看出，使用 fold 和 map 等高階函數(shù)定義的函數(shù)，比起顯式使用遞歸的函數(shù)，并不總是能節(jié)約大量代碼。那么，我們?yōu)槭裁匆褂眠@些函數(shù)呢？
答案是，因為它們在 Haskell 中非常通用，并且這些函數(shù)都帶有正確的、可預(yù)見的行為。
這意味著，即使是一個 Haskell 新手，他/她理解起 fold 通常都要比理解顯式遞歸要容易。一個 fold 并不產(chǎn)生任何意外動作，但一個顯式遞歸函數(shù)的所做作為，通常并不是那么顯而易見的。
以上觀點同樣適用于其他高階函數(shù)庫，包括前面介紹過的 map 和 filter 。因為這些函數(shù)都帶有定義良好的行為，我們只需要學(xué)習(xí)怎樣使用這些函數(shù)一次，以后每次碰到使用這些函數(shù)的代碼，這些知識都可以加快我們對代碼的理解。這種優(yōu)勢同樣體現(xiàn)在代碼的編寫上：一旦我們能熟練使用高階函數(shù)，那么寫出更簡潔的代碼自然就不在話下。
從右邊開始折疊
和 foldl 相對應(yīng)的是 foldr ，它從一個列表的右邊開始進(jìn)行折疊。
-- 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
[譯注：這個函數(shù)在載入 ghci 時會因為命名沖突而被拒絕，編寫函數(shù)直接使用內(nèi)置的 foldr 就可以了。]
可以用 foldr 改寫在《左折疊》一節(jié)定義的 niceSum 函數(shù)：
-- file: ch04/niceSumFoldr.hs
niceSumFoldr :: [Int] -> Int
niceSumFoldr xs = foldr (+) 0 xs
這個 niceSumFoldr 函數(shù)在輸入為 [1,2,3] 時，產(chǎn)生以下計算序列：
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))
可以通過觀察括號的包圍方式，以及累積器初始化值擺放的位置，來區(qū)分 foldl 和 foldr ：foldl 將處初始化值放在左邊，括號也是從左邊開始包圍。另一方面，foldr 將初始化值放在右邊，而括號也是從右邊開始包圍。
還記得當(dāng)年大明湖畔的 filter 函數(shù)嗎？它可以用顯式遞歸來定義：
-- 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
[譯注：這個函數(shù)在載入 ghci 時會因為命名沖突而被拒絕，編寫函數(shù)直接使用內(nèi)置的 filter 就可以了。]
除此之外， filter 還可以通過 foldr 來定義：
-- file: ch04/myFilter.hs
myFilter p xs = foldr step [] xs
where step x ys | p x = x : ys
| otherwise = ys
來仔細(xì)分析一下 myFilter 函數(shù)的定義：和 foldl 一樣， foldr 也接受一個函數(shù)、一個基本情形和一個列表作為參數(shù)。通過閱讀 filter 函數(shù)的類型簽名可以得知， myFilter 函數(shù)的輸入和輸出都使用同類型的列表，因此函數(shù)的基本情形，以及局部函數(shù) step ，都必須返回這個類型的列表。
myFilter 里的 foldr 每次取出列表中的一個元素，并對他進(jìn)行處理，如果這個元素經(jīng)過條件判斷為 True ，那么就將它放進(jìn)累積的新列表里面，否則，它就略過這個元素，繼續(xù)處理列表的其他剩余元素。
所有可以用 foldr 定義的函數(shù)，統(tǒng)稱為主遞歸（primitive recursive）。很大一部分列表處理函數(shù)都是主遞歸函數(shù)。比如說， map 就可以用 foldr 定義：
-- file: ch04/myFoldrMap.hs
myFoldrMap :: (a -> b) -> [a] -> [b]
myFoldrMap f xs = foldr step [] xs
where step x xs = f x : xs
更讓人驚奇的是， 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 的方式是，將它看成是對輸入列表的一種轉(zhuǎn)換（transform）：它的第一個參數(shù)決定了該怎么處理列表的 head 和 tail 部分；而它的第二個參數(shù)則決定了，當(dāng)遇到空列表時，該用什么值來代替這個空列表。
用 foldr 定義的恒等（identity）轉(zhuǎn)換，在列表為空時，返回空列表本身；如果列表不為空，那么它就將列表構(gòu)造器 (:) 應(yīng)用于每個 head 和 tail 對（pair）：
-- file: ch04/identity.hs
identity :: [a] -> [a]
identity xs = foldr (:) [] xs
最終產(chǎn)生的結(jié)果列表和原輸入列表一模一樣：
Prelude> :load identity.hs
[1 of 1] Compiling Main ( identity.hs, interpreted )
Ok, modules loaded: Main.
*Main> identity [1, 2, 3]
[1,2,3]
如果將 identity 函數(shù)定義中，處理空列表時返回的 [] 改為另一個列表，那么我們就得到了列表追加函數(shù) 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"
這個函數(shù)的效果等同于 (++) 操作符：
*Main> "the quick " ++ "fox"
"the quick fox"
append 函數(shù)依然對每個列表元素使用列表構(gòu)造器，但是，當(dāng)?shù)谝粋€輸入列表為空時，它將第二個輸入列表（而不是空列表元素）拼接到第一個輸入列表的表尾。
通過前面這些例子對 foldr 的介紹，我們應(yīng)該可以了解到， foldr 函數(shù)和《列表處理》一節(jié)所介紹的基本列表操作函數(shù)一樣重要。由于 foldr 可以增量地處理和產(chǎn)生列表，所以它對于惰性數(shù)據(jù)處理也非常有用。
左折疊、惰性和內(nèi)存泄漏
為了簡化討論，本節(jié)的例子通常都使用 foldl 來進(jìn)行，這對于普通的測試是沒有問題的，但是，千萬不要把 foldl 用在實際使用中。
這樣做是因為， Haskell 使用的是非嚴(yán)格求值。如果我們仔細(xì)觀察 foldl(+)[1,2,3] 的執(zhí)行過程，就可以會從中看出一些問題：
foldl (+) 0 (1:2:3:[])
== foldl (+) (0 + 1) (2:3:[])
== foldl (+) ((0 + 1) + 2) (3:[])
== foldl (+) (((0 + 1) + 2) + 3) []
== (((0 + 1) + 2) + 3)
除非被顯式地要求，否則最后的表達(dá)式不會被求值為 6 。在表達(dá)式被求值之前，它會被保存在塊里面。保存一個塊比保存單獨一個數(shù)字要昂貴得多，而被塊保存的表達(dá)式越復(fù)雜，這個塊占用的空間就越多。對于數(shù)值計算這樣的廉價操作來說，塊保存這種表達(dá)式所需的計算量，比直接求值這個表達(dá)式所需的計算量還多。最終，我們既浪費了時間，又浪費了金錢。
在 GHC 中，對塊中表達(dá)式的求值在一個內(nèi)部棧中進(jìn)行。因為塊中的表達(dá)式可能是無限大的，而 GHC 為棧設(shè)置了有限大的的容量，多得這個限制，我們可以在 ghci 里嘗試求值一個大的塊，而不必?fù)?dān)心消耗掉全部內(nèi)存。
[譯注：使用棧來執(zhí)行一些可能無限大的操作，是一種常見優(yōu)化和保護(hù)技術(shù)。這種用法減少了操作系統(tǒng)顯式的上下文切換，而且就算計算量超出?？梢匀菁{的范圍，那么最壞的結(jié)果就是棧崩潰，而如果直接使用系統(tǒng)內(nèi)存，一旦請求超出內(nèi)存可以容納的范圍，可能會造成整個程序崩潰，甚至影響系統(tǒng)的穩(wěn)定性。]
Prelude> foldl (+) 0 [1..1000]
500500
可以推測出，在上面的表達(dá)式被求值之前，它創(chuàng)建了一個保存 1000 個數(shù)字和 999 個 (+) 操作的塊。單單為了表示一個數(shù)字，我們就用了非常多的內(nèi)存和 CPU ！
[譯注：這些塊到底有多大？算算就知道了：對于每一個加法表達(dá)式，比如 x+y ，都要使用一個塊來保存。而這種操作在 foldl(+)0[1..1000] 里要執(zhí)行 999 次，因此一共有 999 個塊被創(chuàng)建，這些塊都保存著像 x+y 這樣的表達(dá)式。]
對于一個更大的表達(dá)式 —— 盡管它并不是真的非常龐大， foldl 的執(zhí)行會失?。?/p>
ghci> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
對于小的表達(dá)式來說， foldl 可以給出正確的答案，但是，因為過度的塊資源占用，它運行非常緩慢。我們稱這種現(xiàn)象為內(nèi)存泄漏：代碼可以正確地執(zhí)行，但它占用了比實際所需多得多的內(nèi)存。
對于大的表達(dá)式來說，帶有內(nèi)存泄漏的代碼會造成運行失敗，就像前面例子展示的那樣。
內(nèi)存泄漏是 Haskell 新手常常會遇到的問題，幸好的是，它非常容易避免。Data.List 模塊定義了一個 foldl' 函數(shù)，它和 foldl 的作用類似，唯一的區(qū)別是， foldl' 并不創(chuàng)建塊。以下的代碼直觀地展示了它們的區(qū)別：
ghci> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
ghci> :module +Data.List
ghci> foldl' (+) 0 [1..1000000]
500000500000
綜上所述，最好不要在實際代碼中使用 foldl ：即使計算不失敗，它的效率也好不到那里去。更好的辦法是，使用 Data.List 里面的 foldl' 來代替。 [譯注：在我的電腦上，超出內(nèi)存的 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 的方式應(yīng)該已經(jīng)發(fā)生了變化。
如果使用 foldl' 來執(zhí)行計算，就不會出現(xiàn)任何問題：
Prelude> :module +Data.List
Prelude Data.List> foldl' (+) 0 [1..1000000000]
500000000500000000
就是這樣。]
延伸閱讀 A tutorial on the universality and expressiveness of fold [http://www.cs.nott.ac.uk/~gmh/fold.pdf] 是一篇關(guān)于 fold 的優(yōu)秀且深入的文章。它使用了很多例子來展示如何通過簡單的系統(tǒng)化計算技術(shù)，將一些顯式遞歸的函數(shù)轉(zhuǎn)換成 fold 。
匿名（lambda）函數(shù) 在前面章節(jié)定義的函數(shù)中，很多函數(shù)都帶有一個簡單的輔助函數(shù)：
-- file: ch04/isInAny.hs
import Data.List (isInfixOf)
isInAny needle haystack = any inSequence haystack
where inSequence s = needle `isInfixOf` s
Haskell 允許我們編寫完全匿名的函數(shù)，這樣就不必再費力地為輔助函數(shù)想名字了。因為匿名函數(shù)從 lambda 演算而來，所以匿名函數(shù)通常也被稱為 lambda 函數(shù)。
在 Haskell 中，匿名函數(shù)以反斜杠符號 \ 為開始，后跟函數(shù)的參數(shù)（可以包含模式），而函數(shù)體定義在 -> 符號之后。其中， \ 符號讀作 lambda 。
以下是前面的 isInAny 函數(shù)用 lambda 改寫的版本：
-- file: ch04/isInAny2.hs
import Data.List (isInfixOf)
isInAny2 needle haystack = any (\s -> needle `isInfixOf` s) haystack
定義使用括號包裹了整個匿名函數(shù)，確保 Haskell 可以知道匿名函數(shù)體在那里結(jié)束。
匿名函數(shù)各個方面的行為都和帶名稱的函數(shù)基本一致，但是，匿名函數(shù)的定義受到幾個嚴(yán)格的限制，其中最重要的一點是：普通函數(shù)可以通過多條語句來定義，而 lambda 函數(shù)的定義只能有一條語句。
只能使用一條語句的局限性，限制了在 lambda 定義中可使用的模式。一個普通函數(shù)，通常要使用多條定義，來覆蓋各種不同的模式：
-- file: ch04/safeHead.hs
safeHead (x:_) = Just x
safeHead [] = Nothing
而 lambda 只能覆蓋其中一種情形：
-- file ch04/unsafeHead.hs
unsafeHead = \(x:_) -> x
如果一不小心，將這個函數(shù)應(yīng)用到錯誤的模式上，它就會給我們帶來麻煩：
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 定義是完全合法的，它的類型也沒有錯誤，所以它可以被順利編譯，而最終在運行期產(chǎn)生錯誤。這個故事說明，如果你要在 lambda 函數(shù)里使用模式，請千萬小心，必須確保你的模式不會匹配失敗。
另外需要注意的是，在前面定義的 isInAny 函數(shù)和 isInAny2 函數(shù)里，帶有輔助函數(shù)的 isInAny 要比使用 lambda 的 isInAny2 要更具可讀性。帶有名字的輔助函數(shù)不會破壞程序的代碼流（flow），而且它的名字也可以傳達(dá)更多的相關(guān)信息。
相反，當(dāng)在一個函數(shù)定義里面看到 lambda 時，我們必須慢下來，仔細(xì)閱讀這個匿名函數(shù)的定義，弄清楚它都干了些什么。為了程序的可讀性和可維護(hù)性考慮，我們在很多情況下都會避免使用 lambda 。
當(dāng)然，這并不是說 lambda 函數(shù)完全沒用，只是在使用它們的時候，必須小心謹(jǐn)慎。
很多時候，部分應(yīng)用函數(shù)可以很好地代替 lambda 函數(shù)，避免不必要的函數(shù)定義，粘合起不同的函數(shù)，并產(chǎn)生更清晰和更可讀的代碼。下一節(jié)就會介紹部分應(yīng)用函數(shù)。
部分函數(shù)應(yīng)用和柯里化
類型簽名里的 -> 可能會讓人感到奇怪：
Prelude> :type dropWhile
dropWhile :: (a -> Bool) -> [a] -> [a]
初看上去，似乎 -> 既用于隔開 dropWhile 函數(shù)的各個參數(shù)（比如括號里的 a 和 Bool ），又用于隔開函數(shù)參數(shù)和返回值的類型（(a->Bool)->[a] 和 [a]）。
但是，實際上 -> 只有一種作用：它表示一個函數(shù)接受一個參數(shù)，并返回一個值。其中 -> 符號的左邊是參數(shù)的類型，右邊是返回值的類型。
理解 -> 的含義非常重要：在 Haskell 中，所有函數(shù)都只接受一個參數(shù)。盡管 dropWhile 看上去像是一個接受兩個參數(shù)的函數(shù)，但實際上它是一個接受一個參數(shù)的函數(shù)，而這個函數(shù)的返回值是另一個函數(shù)，這個被返回的函數(shù)也只接受一個參數(shù)。
以下是一個完全合法的 Haskell 表達(dá)式：
Prelude> :module +Data.Char
Prelude Data.Char> :type dropWhile isSpace
dropWhile isSpace :: [Char] -> [Char]
表達(dá)式 dropWhile isSpace 的值是一個函數(shù)，這個函數(shù)移除一個字符串的所有前置空白。作為一個例子，可以將它應(yīng)用到一個高階函數(shù)：
Prelude Data.Char> map (dropWhile isSpace) [" a", "f", " e"]
["a","f","e"]
每當(dāng)我們將一個參數(shù)傳給一個函數(shù)時，這個函數(shù)的類型簽名最前面的一個元素就會被“移除掉”。這里用函數(shù) zip3 來做例子，這個函數(shù)接受三個列表，并將它們壓縮成一個包含三元組的列表：
Prelude> :type zip3
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
Prelude> zip3 "foo" "bar" "quux"
[('f','b','q'),('o','a','u'),('o','r','u')]
如果只將一個參數(shù)應(yīng)用到 zip3 函數(shù)，那么它就會返回一個接受兩個參數(shù)的函數(shù)。無論之后將什么參數(shù)傳給這個復(fù)合函數(shù)，之前傳給它的第一個參數(shù)的值都不會改變。
Prelude> :type zip3
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
Prelude> :type zip3 "foo"
zip3 "foo" :: [b] -> [c] -> [(Char, b, c)]
Prelude> :type zip3 "foo" "bar"
zip3 "foo" "bar" :: [c] -> [(Char, Char, c)]
Prelude> :type zip3 "foo" "bar" "quux"
zip3 "foo" "bar" "quux" :: [(Char, Char, Char)]
傳入?yún)?shù)的數(shù)量，少于函數(shù)所能接受參數(shù)的數(shù)量，這種情況被稱為函數(shù)的部分應(yīng)用（partial application of the function）：函數(shù)正被它的其中幾個參數(shù)所應(yīng)用。
在上面的例子中， zip3"foo" 就是一個部分應(yīng)用函數(shù)，它以 "foo" 作為第一個參數(shù)，部分應(yīng)用了 zip3 函數(shù)；而 zip3"foo""bar" 也是另一個部分應(yīng)用函數(shù)，它以 "foo" 和 "bar" 作為參數(shù)，部分應(yīng)用了 zip3 函數(shù)。
只要給部分函數(shù)補(bǔ)充上足夠的參數(shù)，它就可以被成功求值：
Prelude> let zip3foo = zip3 "foo"
Prelude> zip3foo "bar" "quux"
[('f','b','q'),('o','a','u'),('o','r','u')]
Prelude> let zip3foobar = zip3 "foo" "bar"
Prelude> zip3foobar "quux"
[('f','b','q'),('o','a','u'),('o','r','u')]
Prelude> zip3foobar [1, 2, 3]
[('f','b',1),('o','a',2),('o','r',3)]
部分函數(shù)應(yīng)用（partial function application）讓我們免于編寫煩人的一次性函數(shù)，而且它比起之前介紹的匿名函數(shù)要來得更有用?；仡欀暗?isInAny 函數(shù)，以下是一個部分應(yīng)用函數(shù)改寫的版本，它既不需要匿名函數(shù)，也不需要輔助函數(shù)：
-- file: ch04/isInAny3.hs
import Data.List (isInfixOf)
isInAny3 needle haystack = any (isInfixOf needle) haystack
表達(dá)式 isInfixOfneedle 是部分應(yīng)用函數(shù)，它以 needle 變量作為第一個參數(shù)，傳給 isInfixOf ，并產(chǎn)生一個部分應(yīng)用函數(shù)，這個部分應(yīng)用函數(shù)的作用等同于 isInAny 定義的輔助函數(shù)，以及 isInAny2 定義的匿名函數(shù)。
部分函數(shù)應(yīng)用被稱為柯里化（currying），以邏輯學(xué)家 Haskell Curry 命名（Haskell 語言的命名也是來源于他的名字）。
以下是另一個使用柯里化的例子。先來回顧《左折疊》章節(jié)的 niceSum 函數(shù)：
-- file: ch04/niceSum.hs
niceSum :: [Integer] -> Integer
niceSum xs = foldl (+) 0 xs
實際上，并不需要完全應(yīng)用 foldl [譯注：完全應(yīng)用是指提供函數(shù)所需的全部參數(shù)]，niceSum 函數(shù)的 xs 參數(shù)，以及傳給 foldl 函數(shù)的 xs 參數(shù)，這兩者都可以被省略，最終得到一個更緊湊的函數(shù)，它的類型也和原本的一樣：
-- file: ch04/niceSumPartial.hs
niceSumPartial :: [Integer] -> Integer
niceSumPartial = foldl (+) 0
測試：
Prelude> :load niceSumPartial.hs
[1 of 1] Compiling Main ( niceSumPartial.hs, interpreted )
Ok, modules loaded: Main.
*Main> niceSumPartial [1 .. 10]
55
節(jié)
Haskell 提供了一種方便的符號快捷方式，用于對中序函數(shù)進(jìn)行部分應(yīng)用：使用括號包圍一個操作符，通過在括號里面提供左操作對象或者右操作對象，可以產(chǎn)生一個部分應(yīng)用函數(shù)。這種類型的部分函數(shù)應(yīng)用稱之為節(jié)（section）。
Prelude> (1+) 2
3
Prelude> map (*3) [24, 36]
[72,108]
Prelude> map (2^) [3, 5, 7, 9]
[8,32,128,512]
如果向節(jié)提供左操作對象，那么得出的部分函數(shù)就會將接收到的參數(shù)應(yīng)用為右操作對對象，反之亦然。
以下兩個表達(dá)式都計算 2 的 3 次方，但是第一個節(jié)接受的是左操作對象 2 ，而第二個節(jié)接受的則是右操作對象 3 。
Prelude> (2^) 3
8
Prelude> (^3) 2
8
之前提到過，通過使用反括號來包圍一個函數(shù)，可以將這個函數(shù)用作中序操作符。這種用法可以讓節(jié)使用函數(shù)：
Prelude> :type (`elem` ['a' .. 'z'])
(`elem` ['a' .. 'z']) :: Char -> Bool
上面的定義將 ['a'..'z'] 傳給 elem 作為第二個參數(shù)，表達(dá)式返回的函數(shù)可以用于檢查一個給定字符值是否屬于小寫字母：
Prelude> (`elem` ['a' .. 'z']) 'f'
True
Prelude> (`elem` ['a' .. 'z']) '1'
False
還可以將這個節(jié)用作 all 函數(shù)的輸入，這樣就得到了一個檢查給定字符串是否整個字符串都由小寫字母組成的函數(shù)：
Prelude> all (`elem` ['a' .. 'z']) "Haskell"
False
Prelude> all (`elem` ['a' .. 'z']) "haskell"
True
通過這種用法，可以再一次提升 isInAny3 函數(shù)的可讀性：
-- file: ch04/isInAny4.hs
import Data.List (isInfixOf)
isInAny4 needle haystack = any (needle `isInfixOf`) haystack
[譯注：根據(jù)前面部分函數(shù)部分提到的技術(shù)，這個 isInAny4 的定義還可以進(jìn)一步精簡，去除 haystack 參數(shù)：
import Data.List (isInfixOf)
isInAny4Partial needle = any (needle `isInfixOf`)
]
As-模式
Data.List 模塊里定義的 tails 函數(shù)是 tail 的推廣，它返回一個列表的所有“尾巴”：
Prelude> :m +Data.List
Prelude Data.List> tail "foobar"
"oobar"
Prelude Data.List> tail (tail "foobar")
"obar"
Prelude Data.List> tails "foobar"
["foobar","oobar","obar","bar","ar","r",""]
tails 返回一個包含字符串的列表，這個列表保存了輸入字符串的所有后綴，以及一個額外的空列表（放在結(jié)果列表的最后）。tails 的返回值總是帶有額外的空列表，即使它的輸入為空時：
Prelude Data.List> tails ""
[""]
如果想要一個行為和 tails 類似，但是并不包含空列表后綴的函數(shù)，可以自己寫一個：
-- file: ch04/suffixes.hs
suffixes :: [a] -> [[a]]
suffixes xs@(_:xs') = xs : suffixes xs'
suffixes [] = []
[譯注：在稍后的章節(jié)就會看到，有簡單得多的方法來完成這個目標(biāo)，這個例子主要用于展示 as-模式的作用。]
源碼里面用到了新引入的 @ 符號，模式 xs@(:xs') 被稱為 as-模式，它的意思是：如果輸入值能匹配 @ 符號右邊的模式（這里是 (:xs') ），那么就將這個值綁定到 @ 符號左邊的變量中（這里是 xs ）。
在這個例子里，如果輸入值能夠匹配模式 (:xs') ，那么這個輸入值這就被綁定為 xs ，它的 tail 部分被綁定為 xs' ，而它的 head 部分因為使用通配符 進(jìn)行匹配，所以這部分沒有被綁定到任何變量。
*Main Data.List> tails "foo"
["foo","oo","o",""]
*Main Data.List> suffixes "foo"
["foo","oo","o"]
As-模式可以提升代碼的可讀性，作為對比，以下是一個沒有使用 as-模式的 suffixes 定義：
-- file: noAsPattern.hs
noAsPattern :: [a] -> [[a]]
noAsPattern (x:xs) = (x:xs) : noAsPattern xs
noAsPattern [] = []
可以看到，使用 as-模式的定義同時完成了模式匹配和變量綁定兩項工作。而不使用 as-模式的定義，則需要在對列表進(jìn)行結(jié)構(gòu)之后，在函數(shù)體里又重新對列表進(jìn)行組合。
除了增強(qiáng)可讀性之外， as-模式還有其他作用：它可以對輸入數(shù)據(jù)進(jìn)行共享，而不是復(fù)制它。在 noAsPattern 函數(shù)的定義中，當(dāng) (x:xs) 匹配時，在函數(shù)體里需要復(fù)制一個 (x:xs) 的副本。這個動作會引起內(nèi)存分配。雖然這個分配動作可能很廉價，但它并不是免費的。相反，當(dāng)使用 suffixes 函數(shù)時，我們通過變量 xs 重用匹配了 as-模式的輸入值，因此就避免了內(nèi)存分配。
通過組合函數(shù)來進(jìn)行代碼復(fù)用
前面的 suffixes 函數(shù)實際上有一種更簡單的實現(xiàn)方式。
回憶前面在《使用列表》一節(jié)里介紹的 init 函數(shù)，它可以返回一個列表中除了最后一個元素之外的其他元素。而組合使用 init 和 tails ，可以給出一個 suffixes 函數(shù)的更簡單實現(xiàn)：
-- file: ch04/suffixes.hs
import Data.List (tails)
suffixes2 xs = init (tails xs)
suffixes2 和 suffixes 函數(shù)的行為完全一樣，但 suffixes2 的定義只需一行：
Prelude> :load suffixes2.hs
[1 of 1] Compiling Main ( suffixes2.hs, interpreted )
Ok, modules loaded: Main.
*Main> suffixes2 "foobar"
["foobar","oobar","obar","bar","ar","r"]
如果仔細(xì)地觀察，就會發(fā)現(xiàn)這里隱含著一個模式：我們先應(yīng)用一個函數(shù)，然后又將這個函數(shù)得出的結(jié)果應(yīng)用到另一個函數(shù)?？梢詫⑦@個模式定義為一個函數(shù)：
-- file: ch04/compose.hs
compose :: (b -> c) -> (a -> b) -> a -> c
compose f g x = f (g x)
compose 函數(shù)可以用于粘合兩個函數(shù)：
Prelude> :load compose.hs
[1 of 1] Compiling Main ( compose.hs, interpreted )
Ok, modules loaded: Main.
*Main> :m +Data.List
*Main Data.List> let suffixes3 xs = compose init tails xs
通過柯里化，可以丟掉 xs 函數(shù)：
*Main Data.List> let suffixes4 = compose init tails
更棒的是，其實我們并不需要自己編寫 compose 函數(shù)，因為 Haskell 已經(jīng)內(nèi)置在了 Prelude 里面，使用 (.) 操作符就可以組合起兩個函數(shù)：
*Main Data.List> let suffixes5 = init . tails
(.) 操作符并不是什么特殊語法，它只是一個普通的操作符：
*Main Data.List> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
*Main Data.List> :type suffixes5
suffixes5 :: [a] -> [[a]]
*Main Data.List> suffixes5 "foobar"
["foobar","oobar","obar","bar","ar","r"]
在任何時候，都可以通過使用 (.) 來組合函數(shù)，并產(chǎn)生新函數(shù)。組合鏈的長度并沒有限制，只要 (.) 符號右邊函數(shù)的輸出值類型適用于 (.) 符號左邊函數(shù)的輸入值類型就可以了。
也即是，對于 f.g 來說， g 的輸出值必須是 f 能接受的類型，這樣的組合就是合法的， (.) 的類型簽名也顯示了這一點。
作為例子，再來解決一個非常常見的問題：計算字符串中以大寫字母開頭的單詞的個數(shù)：
Prelude> :module +Data.Char
Prelude Data.Char> let capCount = length . filter (isUpper . head) . words
Prelude Data.Char> capCount "Hello there, Mon!"
2
來逐步分析 capCount 函數(shù)的組合過程。因為 (.) 操作符是右關(guān)聯(lián)的，因此我們從組合鏈的最右邊開始研究：
Prelude Data.Char> :type words
words :: String -> [String]
words 返回一個 [String] 類型值，因此 (.) 的左邊的函數(shù)必須能接受這個參數(shù)。
Prelude Data.Char> :type isUpper . head
isUpper . head :: [Char] -> Bool
上面的組合函數(shù)在輸入字符串以大寫字母開頭時返回 True ，因此 filter(isUpper.head) 表達(dá)式會返回所有以大寫字母開頭的字符串：
Prelude Data.Char> :type filter (isUpper . head)
filter (isUpper . head) :: [[Char]] -> [[Char]]
因為這個表達(dá)式返回一個列表，而 length 函數(shù)用于統(tǒng)計列表的長度，所以 length.filter(isUpper.head) 就計算出了所有以大寫字母開頭的字符串的個數(shù)。
以下是另一個例子，它從 libpcap —— 一個流行的網(wǎng)絡(luò)包過濾庫中提取 C 文件頭中給定格式的宏名字。這些頭文件帶有很多以下格式的宏：
#define DLT_EN10MB 1 /* Ethernet (10Mb) */
#define DLT_EN3MB 2 /* Experimental Ethernet (3Mb) */
#define DLT_AX25 3 /* Amateur Radio AX.25 */
我們的目標(biāo)是提取出所有像 DLT_AX25 和 DLT_EN3MB 這種名字。以下是程序的定義，它將整個文件看作是一個字符串，先使用 lines 對文件進(jìn)行按行分割，再將 foldrstep[] 應(yīng)用到各行當(dāng)中，其中 step 輔助函數(shù)用于過濾和提取符合格式的宏名字：
-- file: ch04/dlts.hs
import Data.List (isPrefixOf)
dlts :: String -> [String]
dlts = foldr step [] . lines
where step l ds
| "#define DLT_" `isPrefixOf` l = secondWord l : ds
| otherwise = ds
secondWord = head . tail . words
程序通過守衛(wèi)表達(dá)式來過濾輸入：如果輸入字符串符合給定格式，就將它加入到結(jié)果列表里；否則，就略過這個字符串，繼續(xù)處理剩余的輸入字符串。
至于 secondWord 函數(shù)，它先取出一個列表的 tail 部分，得出一個新列表。再取出新列表的 head 部分，等同于取出一個列表的第二個元素。
[譯注：書本的這個程序弱爆了，以下是 dlts 的一個更直觀的版本，它使用 filter 來過濾輸入，只保留符合格式的輸入，而不是使用復(fù)雜且難看的顯式遞歸和守衛(wèi)來進(jìn)行過濾：
-- file: ch04/dlts2.hs
import Data.List (isPrefixOf)
dlts2 :: String -> [String]
dlts2 = map (head . tail . words) . filter ("#define DLT_" `isPrefixOf`) . lines
]
編寫可讀代碼的提示
目前為止，我們知道 Haskell 有兩個非常誘人的特性：尾遞歸和匿名函數(shù)。但是，這兩個特性通常并不被使用。
對列表的處理操作一般可以通過組合庫函數(shù)比如 map 、 take 和 filter 來進(jìn)行。當(dāng)然，熟悉這些庫函數(shù)需要一定的時間，不過掌握這些函數(shù)之后，就可以使用它們寫出更快更好更少 bug 的代碼。
庫函數(shù)比尾遞歸更好的原因很簡單：尾遞歸和命令式語言里的 loop 有同樣的問題 —— 它們太通用（general）了。在一個尾遞歸里，你可以同時執(zhí)行過濾（filtering）、映射（mapping）和其他別的動作。這強(qiáng)迫代碼的閱讀者（可能是你自己）必須弄懂整個遞歸函數(shù)的定義，才能理解這個函數(shù)到底做了些什么。與此相反，map 和其他很多列表函數(shù)，都只專注于做一件事。通過這些函數(shù)，我們可以很快理解某段代碼到底做了什么，以及整個程序想表達(dá)什么意思，而不是將時間浪費在關(guān)注細(xì)節(jié)方面。
折疊（fold）操作處于（完全通用化的）尾遞歸和（只做一件事的）列表處理函數(shù)之間的中間地帶。折疊也很值得我們花時間去好好理解，它的作用跟組合起 map 和 filter 函數(shù)差不多，但比起顯式遞歸來說，折疊的行為要來得更有規(guī)律，而且更可控。一般來說，可以通過組合函數(shù)來解決的問題，就不要使用折疊。另一方面，如果問題用組合函數(shù)沒辦法解決，那么使用折疊要比使用顯式遞歸要好。
另一方面，匿名函數(shù)通常會對代碼的可讀性造成影響。一般來說，匿名函數(shù)都可以用 let 或者 where 定義的局部函數(shù)來代替。而且?guī)值木植亢瘮?shù)可以達(dá)到一箭雙雕的效果：它使得代碼更具可讀性，且函數(shù)名本身也達(dá)到了文檔化的作用。
內(nèi)存泄漏和嚴(yán)格求值
前面介紹的 foldl 函數(shù)并不是 Haskell 代碼里唯一會造成內(nèi)存泄漏的地方。
在這一節(jié)，我們使用 foldl 來展示非嚴(yán)格求值在什么情況下會造成問題，以及如何去解決這些問題。
通過 seq 函數(shù)避免內(nèi)存泄漏
我們稱非惰性求值的表達(dá)式為嚴(yán)格的（strict）。 foldl' 就是左折疊的嚴(yán)格版本，它使用特殊的 seq 函數(shù)來繞過 Haskell 默認(rèn)的非嚴(yán)格求值：
-- file: ch04/strictFoldl.hs
foldl' _ zero [] = zero
foldl' step zero (x:xs) =
let new = step zero x
in new `seq` foldl' step new xs
seq 函數(shù)的類型簽名和之前看過的函數(shù)都有些不同，昭示了它的特殊身份：
ghci> :type seq
seq :: a -> t -> t
[譯注：在 7.4.2 版本的 GHCi 里， seq 函數(shù)的類型簽名不再使用 t ，而是像其他函數(shù)一樣，使用 a 和 b 。
Prelude> :type seq
seq :: a -> b -> b
]
實際上， seq 函數(shù)的行為并沒有那么神秘：它強(qiáng)迫（force）求值傳入的第一個參數(shù)，然后返回它的第二個參數(shù)。
比如說，對于以下表達(dá)式：
foldl' (+) 1 (2:[])
它展開為：
let new = 1 + 2
in new `seq` foldl' (+) new []
它強(qiáng)迫 new 求值為 3 ，然后返回它的第二個參數(shù)：
foldl' (+) 3 []
最終得到結(jié)果 3 。
因為 seq 的存在，這個創(chuàng)建過程沒有用到任何塊。
seq 的用法
本節(jié)介紹一些更有效地使用 seq 的指導(dǎo)規(guī)則。
要正確地產(chǎn)生 seq 的作用，表達(dá)式中被求值的第一個必須是 seq ：
-- 錯誤：因為表達(dá)式中第一個被求值的是 someFunc
掃描二維碼
下載編程獅App
編程獅公眾號
更多建議：