第四章：函數(shù)式編程

第四章：函數(shù)式編程

使用 Haskell 思考

初學(xué) Haskell 的人需要邁過(guò)兩個(gè)難關(guān)：

首先，我們需要將自己的編程觀念從命令式語(yǔ)言轉(zhuǎn)換到函數(shù)式語(yǔ)言上面來(lái)。這樣做的原因并不是因?yàn)槊钍秸Z(yǔ)言不好，而是因?yàn)楸绕鹈钍秸Z(yǔ)言，函數(shù)式語(yǔ)言更勝一籌。

其次，我們需要熟悉 Haskell 的標(biāo)準(zhǔn)庫(kù)。和其他語(yǔ)言一樣，函數(shù)庫(kù)可以像杠桿那樣，極大地提升我們解決問(wèn)題的能力。因?yàn)?Haskell 是一門層次非常高的語(yǔ)言，而 Haskell 的標(biāo)準(zhǔn)庫(kù)也趨向于處理高層次的抽象，因此對(duì) Haskell 標(biāo)準(zhǔn)庫(kù)的學(xué)習(xí)也稍微更難一些，但這些努力最終都會(huì)物有所值。

這一章會(huì)介紹一些常用的函數(shù)式編程技術(shù)，以及一些 Haskell 特性。還會(huì)在命令式語(yǔ)言和函數(shù)式語(yǔ)言之間進(jìn)行對(duì)比，幫助讀者了解它們之間的區(qū)別，并且在這個(gè)過(guò)程中，陸續(xù)介紹一些基本的 Haskell 標(biāo)準(zhǔn)庫(kù)。

一個(gè)簡(jiǎn)單的命令行程序

在本章的大部分時(shí)間里，我們都只和無(wú)副作用的代碼打交道。為了將注意力集中在實(shí)際的代碼上，我們需要開發(fā)一個(gè)接口程序，連接起帶副作用的代碼和無(wú)副作用的代碼。

這個(gè)接口程序讀入一個(gè)文件，將函數(shù)應(yīng)用到文件，并且將結(jié)果寫到另一個(gè)文件：

-- 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

這是一個(gè)簡(jiǎn)單但完整的文件處理程序。其中 do 關(guān)鍵字引入一個(gè)塊，標(biāo)識(shí)那些帶有副作用的代碼，比如對(duì)文件進(jìn)行讀和寫操作。被 do 包圍的 <- 操作符效果等同于賦值。第七章還會(huì)介紹更多 I/O 方面的函數(shù)。

當(dāng)我們需要測(cè)試其他函數(shù)的時(shí)候，我們就將程序中的 id 換成其他函數(shù)的名字。另外，這些被測(cè)試的函數(shù)的類型包含 String->String ，也即是，這些函數(shù)應(yīng)該都接受并返回字符串值。

[譯注： id 函數(shù)接受一個(gè)值，并原封不動(dòng)地返回這個(gè)值，比如 id"hello" 返回值 "hello" ，而 id10 返回值 10 。]

[譯注：這一段最后一句的原文是“ ... need to have the type String->String ... ” ，因?yàn)?Haskell 是一種帶有類型多態(tài)的語(yǔ)言，所以將“ have the type ” 翻譯成 “ 包含 xx 類型 ”，而不是 “ 必須是 xx 類型 ”。

接下來(lái)編譯這個(gè)程序：

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

通過(guò)命令行運(yùn)行這個(gè)程序。它接受兩個(gè)文件名作為參數(shù)輸入，一個(gè)用于讀取，一個(gè)用于寫入：

$ 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í)行過(guò)程少了寫入內(nèi)容到 hello-in.txt 的一步，導(dǎo)致執(zhí)行會(huì)出錯(cuò)，所以這里加上 echo... 這一步。另外原書執(zhí)行的是 Interact 過(guò)程，也是錯(cuò)誤的，正確的執(zhí)行文件名應(yīng)該是 InteractWith 。]

循環(huán)的表示

和傳統(tǒng)編程語(yǔ)言不同， Haskell 既沒有 for 循環(huán)，也沒有 while 循環(huán)。那么，如果有一大堆數(shù)據(jù)要處理，該用什么代替這些循環(huán)呢？這一節(jié)就會(huì)給出這個(gè)問(wèn)題的幾種可能的解決辦法。

顯式遞歸

通過(guò)例子進(jìn)行比對(duì)，可以很直觀地認(rèn)識(shí)有 loop 語(yǔ)言和沒 loop 語(yǔ)言之間的區(qū)別。以下是一個(gè) 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 語(yǔ)言代碼，在 Haskell 里該怎么表達(dá)呢？

讓我們先從類型簽名開始寫起，這不是必須的，但它對(duì)于弄清楚代碼在干什么很有幫助：

-- file: ch04/IntParse.hs
import Data.Char (digitToInt) -- we'll need ord shortly

asInt :: String -> Int

C 代碼在遍歷字符串的過(guò)程中，漸增地計(jì)算結(jié)果。Haskell 代碼同樣可以做到這一點(diǎn)，而且，在 Haskell 里，使用函數(shù)已經(jīng)足以表示 loop 計(jì)算了。[譯注：在命令式語(yǔ)言里，很多迭代計(jì)算都是通過(guò)特殊關(guān)鍵字來(lái)實(shí)現(xiàn)的，比如 do 、 while 和 for 。]

-- file: ch04/IntParse.hs
loop :: Int -> String -> Int

asInt xs = loop 0 xs

loop 的第一個(gè)參數(shù)是累積器的變量，給它賦值 0 等同于 C 語(yǔ)言在 for 循環(huán)開始前的初始化操作。

在研究詳細(xì)的代碼前，先來(lái)思考一下我們要處理的數(shù)據(jù)：輸入 xs 是一個(gè)包含數(shù)字的字符串，而 String 類型不過(guò)是 [Char] 的別名，一個(gè)包含字符的列表。因此，要遍歷處理字符串，最好的方法是將它看作是列表來(lái)處理：它要么就是一個(gè)空字符串；要么就是一個(gè)字符，后面跟著列表的其余部分。

以上的想法可以通過(guò)對(duì)列表的構(gòu)造器進(jìn)行模式匹配來(lái)表達(dá)。先從最簡(jiǎn)單的情況 —— 輸入為空字符串開始：

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

一個(gè)空列表并不僅僅意味著“輸入列表為空”，另一種可能的情況是，對(duì)一個(gè)非空字符串進(jìn)行遍歷之后，最終到達(dá)了列表的末尾。因此，對(duì)于空列表，我們不是拋出錯(cuò)誤，而是將累積值返回。

另一個(gè)等式處理列表不為空的情況：先取出并處理列表的當(dāng)前元素，接著處理列表的其他元素。

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

程序先計(jì)算出當(dāng)前字符所代表的數(shù)值，將它賦值給局部變量 acc' 。然后使用 acc' 和剩余列表的元素 xs 作為參數(shù)，再次調(diào)用 loop 函數(shù)。這種調(diào)用等同于在 C 代碼中再次執(zhí)行一次循環(huán)。

每次遞歸調(diào)用 loop ，累積器的值都會(huì)被更新，并處理掉列表里的一個(gè)元素。這樣一直下去，最終輸入列表為空，遞歸調(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

[譯注：書本原來(lái)的代碼少了對(duì) Data.Char 的引用，會(huì)造成 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í)，它運(yùn)行得很好。不過(guò)，如果傳給它一些不合法的輸入，這個(gè)可憐的函數(shù)就沒辦法處理了：

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

在練習(xí)一，我們會(huì)想辦法解決這個(gè)問(wèn)題。

loop 函數(shù)是尾遞歸函數(shù)的一個(gè)例子：如果輸入非空，這個(gè)函數(shù)做的最后一件事，就是遞歸地調(diào)用自身。這個(gè)代碼還展示了另一個(gè)慣用法：通過(guò)研究列表的結(jié)構(gòu)，分別處理空列表和非空列表兩種狀況，這種方法稱之為結(jié)構(gòu)遞歸（structural recursion）。

非遞歸情形（列表為空）被稱為“基本情形”（有時(shí)也叫終止情形）。當(dāng)對(duì)函數(shù)進(jìn)行遞歸調(diào)用時(shí)，計(jì)算最終會(huì)回到基本情形上。在數(shù)學(xué)上，這也稱為“歸納情形”。

作為一項(xiàng)有用的技術(shù)，結(jié)構(gòu)遞歸并不僅僅局限于列表，它也適用于其他代數(shù)數(shù)據(jù)類型，稍后就會(huì)介紹更多這方面的例子。

對(duì)列表元素進(jìn)行轉(zhuǎn)換

考慮以下 C 函數(shù)， square ，它對(duì)數(shù)組中的所有元素執(zhí)行平方計(jì)算：

void square(double *out, const double *in, size_t length)
{
    for (size_t i = 0; i < length; i++) {
        out[i] = in[i] * in[i];
    }
}

這段代碼展示了一個(gè)直觀且常見的 loop 動(dòng)作，它對(duì)輸入數(shù)組中的所有元素執(zhí)行同樣的動(dòng)作。以下是 Haskell 版本的 square 函數(shù)：

-- file: ch04/square.hs

square :: [Double] -> [Double]

square (x:xs) = x*x : square xs
square []     = []

square 函數(shù)包含兩個(gè)模式匹配等式。第一個(gè)模式解構(gòu)一個(gè)列表，取出它的 head 部分和 tail 部分，并對(duì)第一個(gè)元素進(jìn)行加倍操作，然后將計(jì)算所得的新元素放進(jìn)列表里面。一直這樣做下去，直到處理完整個(gè)列表為止。第二個(gè)等式確保計(jì)算會(huì)在列表為空時(shí)順利終止。

square 產(chǎn)生一個(gè)和輸入列表一樣長(zhǎng)的新列表，其中每個(gè)新元素的值都是原本元素的平方：

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]

以下是另一個(gè) 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ù)，如果輸入字符是一個(gè)字母的話，那么函數(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ù)很相似：如果輸入是一個(gè)空列表，那么它就停止計(jì)算，返回一個(gè)空列表。另一方面，如果輸入不為空，那么它就對(duì)列表的第一個(gè)元素調(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"

以上兩個(gè)函數(shù)遵循了同一種處理列表的公共模式：基本情形處理（base case）空列表輸入。而遞歸情形（recursive case）則處理列表非空時(shí)的情況，它對(duì)列表的頭元素進(jìn)行某種操作，然后遞歸地處理列表余下的其他元素。

列表映射

前面定義的 square 和 upperCase 函數(shù)，都生成一個(gè)和輸入列表同等長(zhǎng)度的新列表，并且每次只對(duì)列表的一個(gè)元素進(jìn)行處理。因?yàn)檫@種用法非常常見，所以 Haskell 的 Prelude 庫(kù)定義了 map 函數(shù)來(lái)更方便地執(zhí)行這種操作。 map 函數(shù)接受一個(gè)函數(shù)和一個(gè)列表作為參數(shù)，將輸入函數(shù)應(yīng)用到輸入列表的每個(gè)元素上，并構(gòu)建出一個(gè)新的列表。

以下是使用 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ù)。]

來(lái)研究一下 map 是如何實(shí)現(xiàn)的。通過(guò)查看它的類型簽名，可以發(fā)現(xiàn)很多有意思的信息：

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

類型簽名顯示， map 接受兩個(gè)參數(shù)：第一個(gè)參數(shù)是一個(gè)函數(shù)，這個(gè)函數(shù)接受一個(gè) a 類型的值，并返回一個(gè) b 類型的值[譯注：這里只是說(shuō) a 和 b 類型可能不一樣，但不是必須的。]。

像 map 這種接受一個(gè)函數(shù)作為參數(shù)、又或者返回一個(gè)函數(shù)作為結(jié)果的函數(shù)，被稱為高階函數(shù)。

因?yàn)?map 的抽象出現(xiàn)在 square 和 upperCase 函數(shù)，所以可以通過(guò)觀察這兩個(gè)函數(shù)，找出它們之間的共同點(diǎn)，然后實(shí)現(xiàn)自己的 map 函數(shù)：

-- file: ch04/myMap.hs

myMap :: (a -> b) -> [a] -> [b]

myMap f (x:xs) = f x : myMap f xs
myMap _ [] = []

[譯注：在原文的代碼里，第二個(gè)等式的定義為 myMap_=[] ，這并不是完全正確的，因?yàn)樗梢赃m配于第二個(gè)參數(shù)不為列表的情況，比如 myMapf1 。因此，這里遵循標(biāo)準(zhǔn)庫(kù)里 map 的定義，將第二個(gè)等式修改為 myMap[]=[] 。]

在 ghci 測(cè)試這個(gè) 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"

通過(guò)觀察代碼，并從中提煉出重復(fù)的抽象，是復(fù)用代碼的一種良好方法。盡管對(duì)代碼進(jìn)行抽象并不是 Haskell 的“專利”，但高階函數(shù)使得這種抽象變得非常容易。
篩選列表元素 另一種對(duì)列表的常見操作是，對(duì)列表元素進(jìn)行篩選，只保留那些符合條件的元素。 以下函數(shù)接受一個(gè)列表作為參數(shù)，并返回這個(gè)列表里的所有奇數(shù)元素。代碼的遞歸情形比之前的 map 函數(shù)要復(fù)雜一些，它使用守衛(wèi)對(duì)元素進(jìn)行條件判斷，只有符合條件的元素，才會(huì)被加入進(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ù)的代碼一樣。]

測(cè)試：

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]

因?yàn)檫@種過(guò)濾模式也很常見，所以 Prelude 也定義了相應(yīng)的函數(shù) filter ：它接受一個(gè)謂詞函數(shù)，并將它應(yīng)用到列表里的每個(gè)元素，只有那些謂詞函數(shù)求值返回 True 的元素才會(huì)被保留：

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é)會(huì)介紹如何定義 filter 。

處理收集器并得出結(jié)果

將一個(gè)收集器（collection）簡(jiǎn)化（reduce）為一個(gè)值也是收集器的常見操作之一。

對(duì)列表的所有元素求和，就是其中的一個(gè)例子：

-- file: ch04/mySum.hs

mySum xs = helper 0 xs
    where helper acc (x:xs) = helper (acc + x) xs
          helper acc []     = acc

helper 函數(shù)通過(guò)尾遞歸進(jìn)行計(jì)算。 acc 是累積器參數(shù)，它記錄了當(dāng)前列表元素的總和。正如我們?cè)?asInt 函數(shù)看到的那樣，這種遞歸計(jì)算是純函數(shù)語(yǔ)言里表示 loop 最自然的方式。

以下是一個(gè)稍微復(fù)雜一些的例子，它是一個(gè) Adler-32 校驗(yàn)和的 JAVA 實(shí)現(xiàn)。Adler-32 是一個(gè)流行的校驗(yàn)和算法，它將兩個(gè) 16 位校驗(yàn)和串聯(lián)成一個(gè) 32 位校驗(yàn)和。第一個(gè)校驗(yàn)和是所有輸入比特之和，加上一。而第二個(gè)校驗(yàn)和則是第一個(gè)校驗(yàn)和所有中間值之和。每次計(jì)算時(shí)，校驗(yàn)和都需要取模 65521 。（如果你不懂 JAVA ，直接跳過(guò)也沒關(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 是一個(gè)簡(jiǎn)單的校驗(yàn)和算法，但這個(gè) JAVA 實(shí)現(xiàn)還是非常復(fù)雜，很難看清楚位操作之間的關(guān)系。

以下是 Adler-32 算法的 Haskell 實(shí)現(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ù)實(shí)現(xiàn)邏輯左移， (.&.) 實(shí)現(xiàn)二進(jìn)制位的并操作， (.|.) 實(shí)現(xiàn)二進(jìn)制位的或操作， ord 函數(shù)則返回給定字符對(duì)應(yīng)的編碼值。

helper 函數(shù)通過(guò)尾遞歸來(lái)進(jìn)行計(jì)算，每次對(duì)它的調(diào)用，都產(chǎn)生新的累積變量，效果等同于 JAVA 在 for 循環(huán)里對(duì)變量的賦值更新。當(dāng)列表處理完畢，遞歸終止時(shí)，程序計(jì)算出校驗(yàn)和并將它返回。

和前面抽取出 map 和 filter 函數(shù)類似，從 Adler32 函數(shù)里面，我們也可以抽取出一種通用的抽象，稱之為折疊（fold）：它對(duì)一個(gè)列表中的所有元素做某種處理，并且一邊處理元素，一邊更新累積器，最后在處理完整個(gè)列表之后，返回累積器的值。

有兩種不同類型的折疊，其中 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

[譯注：這個(gè)函數(shù)在載入 ghci 時(shí)會(huì)因?yàn)槊麤_突而被拒絕，編寫函數(shù)直接使用內(nèi)置的 foldl 就可以了。]

foldl 函數(shù)接受一個(gè)步驟（step）函數(shù)，一個(gè)累積器的初始化值，以及一個(gè)列表作為參數(shù)。步驟函數(shù)每次使用累積器和列表中的一個(gè)元素作為參數(shù)，并計(jì)算出新的累積器值，這個(gè)過(guò)程稱為步進(jìn)（stepper）。然后，將新的累積器作為參數(shù)，再次進(jìn)行同樣的計(jì)算，直到整個(gè)列表處理完為止。

以下是使用 foldl 重寫的 mySum 函數(shù)：

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

因?yàn)榇a里的 step 函數(shù)執(zhí)行的操作不過(guò)是相加起它的兩個(gè)輸入?yún)?shù)，因此，可以直接將一個(gè)加法函數(shù)代替 step 函數(shù)，并移除多余的 where 語(yǔ)句：

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

為了進(jìn)一步看清楚 foldl 的執(zhí)行模式，以下代碼展示了 niceSum[1,2,3] 執(zhí)行時(shí)的計(jì)算過(guò)程：

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)

注意對(duì)比新的 mySum 定義比剛開始的定義節(jié)省了多少代碼：新版本沒有使用顯式遞歸，因?yàn)?foldl 可以代替我們搞定了關(guān)于循環(huán)的一切。現(xiàn)在程序只要求我們回答兩個(gè)問(wèn)題：第一，累積器的初始化值是什么（foldl 的第二個(gè)參數(shù)）；第二，怎么更新累積器的值（(+) 函數(shù)）。

為什么使用 fold 、 map 和 filter ？

回顧一下之前的幾個(gè)例子，可以看出，使用 fold 和 map 等高階函數(shù)定義的函數(shù)，比起顯式使用遞歸的函數(shù)，并不總是能節(jié)約大量代碼。那么，我們?yōu)槭裁匆褂眠@些函數(shù)呢？

答案是，因?yàn)樗鼈冊(cè)?Haskell 中非常通用，并且這些函數(shù)都帶有正確的、可預(yù)見的行為。

這意味著，即使是一個(gè) Haskell 新手，他/她理解起 fold 通常都要比理解顯式遞歸要容易。一個(gè) fold 并不產(chǎn)生任何意外動(dòng)作，但一個(gè)顯式遞歸函數(shù)的所做作為，通常并不是那么顯而易見的。

以上觀點(diǎn)同樣適用于其他高階函數(shù)庫(kù)，包括前面介紹過(guò)的 map 和 filter 。因?yàn)檫@些函數(shù)都帶有定義良好的行為，我們只需要學(xué)習(xí)怎樣使用這些函數(shù)一次，以后每次碰到使用這些函數(shù)的代碼，這些知識(shí)都可以加快我們對(duì)代碼的理解。這種優(yōu)勢(shì)同樣體現(xiàn)在代碼的編寫上：一旦我們能熟練使用高階函數(shù)，那么寫出更簡(jiǎn)潔的代碼自然就不在話下。

從右邊開始折疊

和 foldl 相對(duì)應(yīng)的是 foldr ，它從一個(gè)列表的右邊開始進(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

[譯注：這個(gè)函數(shù)在載入 ghci 時(shí)會(huì)因?yàn)槊麤_突而被拒絕，編寫函數(shù)直接使用內(nèi)置的 foldr 就可以了。]

可以用 foldr 改寫在《左折疊》一節(jié)定義的 niceSum 函數(shù)：

-- file: ch04/niceSumFoldr.hs

niceSumFoldr :: [Int] -> Int
niceSumFoldr xs = foldr (+) 0 xs

這個(gè) niceSumFoldr 函數(shù)在輸入為 [1,2,3] 時(shí)，產(chǎn)生以下計(jì)算序列：

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))

可以通過(guò)觀察括號(hào)的包圍方式，以及累積器初始化值擺放的位置，來(lái)區(qū)分 foldl 和 foldr ：foldl 將處初始化值放在左邊，括號(hào)也是從左邊開始包圍。另一方面，foldr 將初始化值放在右邊，而括號(hào)也是從右邊開始包圍。

還記得當(dāng)年大明湖畔的 filter 函數(shù)嗎？它可以用顯式遞歸來(lái)定義：

-- 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

[譯注：這個(gè)函數(shù)在載入 ghci 時(shí)會(huì)因?yàn)槊麤_突而被拒絕，編寫函數(shù)直接使用內(nèi)置的 filter 就可以了。]

除此之外， filter 還可以通過(guò) foldr 來(lái)定義：

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

來(lái)仔細(xì)分析一下 myFilter 函數(shù)的定義：和 foldl 一樣， foldr 也接受一個(gè)函數(shù)、一個(gè)基本情形和一個(gè)列表作為參數(shù)。通過(guò)閱讀 filter 函數(shù)的類型簽名可以得知， myFilter 函數(shù)的輸入和輸出都使用同類型的列表，因此函數(shù)的基本情形，以及局部函數(shù) step ，都必須返回這個(gè)類型的列表。

myFilter 里的 foldr 每次取出列表中的一個(gè)元素，并對(duì)他進(jìn)行處理，如果這個(gè)元素經(jīng)過(guò)條件判斷為 True ，那么就將它放進(jìn)累積的新列表里面，否則，它就略過(guò)這個(gè)元素，繼續(xù)處理列表的其他剩余元素。

所有可以用 foldr 定義的函數(shù)，統(tǒng)稱為主遞歸（primitive recursive）。很大一部分列表處理函數(shù)都是主遞歸函數(shù)。比如說(shuō)， 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 來(lái)表示：

-- 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 的方式是，將它看成是對(duì)輸入列表的一種轉(zhuǎn)換（transform）：它的第一個(gè)參數(shù)決定了該怎么處理列表的 head 和 tail 部分；而它的第二個(gè)參數(shù)則決定了，當(dāng)遇到空列表時(shí)，該用什么值來(lái)代替這個(gè)空列表。

用 foldr 定義的恒等（identity）轉(zhuǎn)換，在列表為空時(shí)，返回空列表本身；如果列表不為空，那么它就將列表構(gòu)造器 (:) 應(yīng)用于每個(gè) head 和 tail 對(duì)（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í)返回的 [] 改為另一個(gè)列表，那么我們就得到了列表追加函數(shù) append ：

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

測(cè)試：

Prelude> :load append.hs
[1 of 1] Compiling Main             ( append.hs, interpreted )
Ok, modules loaded: Main.

*Main> append "the quick " "fox"
"the quick fox"

這個(gè)函數(shù)的效果等同于 (++) 操作符：

*Main> "the quick " ++ "fox"
"the quick fox"

append 函數(shù)依然對(duì)每個(gè)列表元素使用列表構(gòu)造器，但是，當(dāng)?shù)谝粋€(gè)輸入列表為空時(shí)，它將第二個(gè)輸入列表（而不是空列表元素）拼接到第一個(gè)輸入列表的表尾。

通過(guò)前面這些例子對(duì) foldr 的介紹，我們應(yīng)該可以了解到， foldr 函數(shù)和《列表處理》一節(jié)所介紹的基本列表操作函數(shù)一樣重要。由于 foldr 可以增量地處理和產(chǎn)生列表，所以它對(duì)于惰性數(shù)據(jù)處理也非常有用。

左折疊、惰性和內(nèi)存泄漏

為了簡(jiǎn)化討論，本節(jié)的例子通常都使用 foldl 來(lái)進(jìn)行，這對(duì)于普通的測(cè)試是沒有問(wèn)題的，但是，千萬(wàn)不要把 foldl 用在實(shí)際使用中。

這樣做是因?yàn)椋?Haskell 使用的是非嚴(yán)格求值。如果我們仔細(xì)觀察 foldl(+)[1,2,3] 的執(zhí)行過(guò)程，就可以會(huì)從中看出一些問(wèn)題：

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á)式不會(huì)被求值為 6 。在表達(dá)式被求值之前，它會(huì)被保存在塊里面。保存一個(gè)塊比保存單獨(dú)一個(gè)數(shù)字要昂貴得多，而被塊保存的表達(dá)式越復(fù)雜，這個(gè)塊占用的空間就越多。對(duì)于數(shù)值計(jì)算這樣的廉價(jià)操作來(lái)說(shuō)，塊保存這種表達(dá)式所需的計(jì)算量，比直接求值這個(gè)表達(dá)式所需的計(jì)算量還多。最終，我們既浪費(fèi)了時(shí)間，又浪費(fèi)了金錢。

在 GHC 中，對(duì)塊中表達(dá)式的求值在一個(gè)內(nèi)部棧中進(jìn)行。因?yàn)閴K中的表達(dá)式可能是無(wú)限大的，而 GHC 為棧設(shè)置了有限大的的容量，多得這個(gè)限制，我們可以在 ghci 里嘗試求值一個(gè)大的塊，而不必?fù)?dān)心消耗掉全部?jī)?nèi)存。

[譯注：使用棧來(lái)執(zhí)行一些可能無(wú)限大的操作，是一種常見優(yōu)化和保護(hù)技術(shù)。這種用法減少了操作系統(tǒng)顯式的上下文切換，而且就算計(jì)算量超出棧可以容納的范圍，那么最壞的結(jié)果就是棧崩潰，而如果直接使用系統(tǒng)內(nèi)存，一旦請(qǐng)求超出內(nèi)存可以容納的范圍，可能會(huì)造成整個(gè)程序崩潰，甚至影響系統(tǒng)的穩(wěn)定性。]

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

可以推測(cè)出，在上面的表達(dá)式被求值之前，它創(chuàng)建了一個(gè)保存 1000 個(gè)數(shù)字和 999 個(gè) (+) 操作的塊。單單為了表示一個(gè)數(shù)字，我們就用了非常多的內(nèi)存和 CPU ！

[譯注：這些塊到底有多大？算算就知道了：對(duì)于每一個(gè)加法表達(dá)式，比如 x+y ，都要使用一個(gè)塊來(lái)保存。而這種操作在 foldl(+)0[1..1000] 里要執(zhí)行 999 次，因此一共有 999 個(gè)塊被創(chuàng)建，這些塊都保存著像 x+y 這樣的表達(dá)式。]

對(duì)于一個(gè)更大的表達(dá)式 —— 盡管它并不是真的非常龐大， foldl 的執(zhí)行會(huì)失?。?/p>

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

對(duì)于小的表達(dá)式來(lái)說(shuō)， foldl 可以給出正確的答案，但是，因?yàn)檫^(guò)度的塊資源占用，它運(yùn)行非常緩慢。我們稱這種現(xiàn)象為內(nèi)存泄漏：代碼可以正確地執(zhí)行，但它占用了比實(shí)際所需多得多的內(nèi)存。

對(duì)于大的表達(dá)式來(lái)說(shuō)，帶有內(nèi)存泄漏的代碼會(huì)造成運(yùn)行失敗，就像前面例子展示的那樣。

內(nèi)存泄漏是 Haskell 新手常常會(huì)遇到的問(wèn)題，幸好的是，它非常容易避免。Data.List 模塊定義了一個(gè) 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

綜上所述，最好不要在實(shí)際代碼中使用 foldl ：即使計(jì)算不失敗，它的效率也好不到那里去。更好的辦法是，使用 Data.List 里面的 foldl' 來(lái)代替。 [譯注：在我的電腦上，超出內(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
已放棄

從錯(cuò)誤信息看， GHC/GHCi 處理 foldl 的方式應(yīng)該已經(jīng)發(fā)生了變化。

如果使用 foldl' 來(lái)執(zhí)行計(jì)算，就不會(huì)出現(xiàn)任何問(wè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)秀且深入的文章。它使用了很多例子來(lái)展示如何通過(guò)簡(jiǎn)單的系統(tǒng)化計(jì)算技術(shù)，將一些顯式遞歸的函數(shù)轉(zhuǎn)換成 fold 。
匿名（lambda）函數(shù) 在前面章節(jié)定義的函數(shù)中，很多函數(shù)都帶有一個(gè)簡(jiǎn)單的輔助函數(shù)：

-- file: ch04/isInAny.hs

import Data.List (isInfixOf)

isInAny needle haystack = any inSequence haystack
    where inSequence s = needle `isInfixOf` s

Haskell 允許我們編寫完全匿名的函數(shù)，這樣就不必再費(fèi)力地為輔助函數(shù)想名字了。因?yàn)槟涿瘮?shù)從 lambda 演算而來(lái)，所以匿名函數(shù)通常也被稱為 lambda 函數(shù)。

在 Haskell 中，匿名函數(shù)以反斜杠符號(hào) \ 為開始，后跟函數(shù)的參數(shù)（可以包含模式），而函數(shù)體定義在 -> 符號(hào)之后。其中， \ 符號(hào)讀作 lambda 。

以下是前面的 isInAny 函數(shù)用 lambda 改寫的版本：

-- file: ch04/isInAny2.hs

import Data.List (isInfixOf)

isInAny2 needle haystack = any (\s -> needle `isInfixOf` s) haystack

定義使用括號(hào)包裹了整個(gè)匿名函數(shù)，確保 Haskell 可以知道匿名函數(shù)體在那里結(jié)束。

匿名函數(shù)各個(gè)方面的行為都和帶名稱的函數(shù)基本一致，但是，匿名函數(shù)的定義受到幾個(gè)嚴(yán)格的限制，其中最重要的一點(diǎn)是：普通函數(shù)可以通過(guò)多條語(yǔ)句來(lái)定義，而 lambda 函數(shù)的定義只能有一條語(yǔ)句。

只能使用一條語(yǔ)句的局限性，限制了在 lambda 定義中可使用的模式。一個(gè)普通函數(shù)，通常要使用多條定義，來(lái)覆蓋各種不同的模式：

-- file: ch04/safeHead.hs

safeHead (x:_) = Just x
safeHead [] = Nothing

而 lambda 只能覆蓋其中一種情形：

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

如果一不小心，將這個(gè)函數(shù)應(yīng)用到錯(cuò)誤的模式上，它就會(huì)給我們帶來(lái)麻煩：

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

因?yàn)檫@個(gè) lambda 定義是完全合法的，它的類型也沒有錯(cuò)誤，所以它可以被順利編譯，而最終在運(yùn)行期產(chǎn)生錯(cuò)誤。這個(gè)故事說(shuō)明，如果你要在 lambda 函數(shù)里使用模式，請(qǐng)千萬(wàn)小心，必須確保你的模式不會(huì)匹配失敗。

另外需要注意的是，在前面定義的 isInAny 函數(shù)和 isInAny2 函數(shù)里，帶有輔助函數(shù)的 isInAny 要比使用 lambda 的 isInAny2 要更具可讀性。帶有名字的輔助函數(shù)不會(huì)破壞程序的代碼流（flow），而且它的名字也可以傳達(dá)更多的相關(guān)信息。

相反，當(dāng)在一個(gè)函數(shù)定義里面看到 lambda 時(shí)，我們必須慢下來(lái)，仔細(xì)閱讀這個(gè)匿名函數(shù)的定義，弄清楚它都干了些什么。為了程序的可讀性和可維護(hù)性考慮，我們?cè)诤芏嗲闆r下都會(huì)避免使用 lambda 。

當(dāng)然，這并不是說(shuō) lambda 函數(shù)完全沒用，只是在使用它們的時(shí)候，必須小心謹(jǐn)慎。

很多時(shí)候，部分應(yīng)用函數(shù)可以很好地代替 lambda 函數(shù)，避免不必要的函數(shù)定義，粘合起不同的函數(shù)，并產(chǎn)生更清晰和更可讀的代碼。下一節(jié)就會(huì)介紹部分應(yīng)用函數(shù)。

部分函數(shù)應(yīng)用和柯里化

類型簽名里的 -> 可能會(huì)讓人感到奇怪：

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

初看上去，似乎 -> 既用于隔開 dropWhile 函數(shù)的各個(gè)參數(shù)（比如括號(hào)里的 a 和 Bool ），又用于隔開函數(shù)參數(shù)和返回值的類型（(a->Bool)->[a] 和 [a]）。

但是，實(shí)際上 -> 只有一種作用：它表示一個(gè)函數(shù)接受一個(gè)參數(shù)，并返回一個(gè)值。其中 -> 符號(hào)的左邊是參數(shù)的類型，右邊是返回值的類型。

理解 -> 的含義非常重要：在 Haskell 中，所有函數(shù)都只接受一個(gè)參數(shù)。盡管 dropWhile 看上去像是一個(gè)接受兩個(gè)參數(shù)的函數(shù)，但實(shí)際上它是一個(gè)接受一個(gè)參數(shù)的函數(shù)，而這個(gè)函數(shù)的返回值是另一個(gè)函數(shù)，這個(gè)被返回的函數(shù)也只接受一個(gè)參數(shù)。

以下是一個(gè)完全合法的 Haskell 表達(dá)式：

Prelude> :module +Data.Char

Prelude Data.Char> :type dropWhile isSpace
dropWhile isSpace :: [Char] -> [Char]

表達(dá)式 dropWhile isSpace 的值是一個(gè)函數(shù)，這個(gè)函數(shù)移除一個(gè)字符串的所有前置空白。作為一個(gè)例子，可以將它應(yīng)用到一個(gè)高階函數(shù)：

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

每當(dāng)我們將一個(gè)參數(shù)傳給一個(gè)函數(shù)時(shí)，這個(gè)函數(shù)的類型簽名最前面的一個(gè)元素就會(huì)被“移除掉”。這里用函數(shù) zip3 來(lái)做例子，這個(gè)函數(shù)接受三個(gè)列表，并將它們壓縮成一個(gè)包含三元組的列表：

Prelude> :type zip3
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]

Prelude> zip3 "foo" "bar" "quux"
[('f','b','q'),('o','a','u'),('o','r','u')]

如果只將一個(gè)參數(shù)應(yīng)用到 zip3 函數(shù)，那么它就會(huì)返回一個(gè)接受兩個(gè)參數(shù)的函數(shù)。無(wú)論之后將什么參數(shù)傳給這個(gè)復(fù)合函數(shù)，之前傳給它的第一個(gè)參數(shù)的值都不會(huì)改變。

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ù)正被它的其中幾個(gè)參數(shù)所應(yīng)用。

在上面的例子中， zip3"foo" 就是一個(gè)部分應(yīng)用函數(shù)，它以 "foo" 作為第一個(gè)參數(shù)，部分應(yīng)用了 zip3 函數(shù)；而 zip3"foo""bar" 也是另一個(gè)部分應(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ù)要來(lái)得更有用?；仡欀暗?isInAny 函數(shù)，以下是一個(gè)部分應(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 變量作為第一個(gè)參數(shù)，傳給 isInfixOf ，并產(chǎn)生一個(gè)部分應(yīng)用函數(shù)，這個(gè)部分應(yīng)用函數(shù)的作用等同于 isInAny 定義的輔助函數(shù)，以及 isInAny2 定義的匿名函數(shù)。

部分函數(shù)應(yīng)用被稱為柯里化（currying），以邏輯學(xué)家 Haskell Curry 命名（Haskell 語(yǔ)言的命名也是來(lái)源于他的名字）。

以下是另一個(gè)使用柯里化的例子。先來(lái)回顧《左折疊》章節(jié)的 niceSum 函數(shù)：

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

實(shí)際上，并不需要完全應(yīng)用 foldl [譯注：完全應(yīng)用是指提供函數(shù)所需的全部參數(shù)]，niceSum 函數(shù)的 xs 參數(shù)，以及傳給 foldl 函數(shù)的 xs 參數(shù)，這兩者都可以被省略，最終得到一個(gè)更緊湊的函數(shù)，它的類型也和原本的一樣：

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

測(cè)試：

Prelude> :load niceSumPartial.hs
[1 of 1] Compiling Main             ( niceSumPartial.hs, interpreted )
Ok, modules loaded: Main.

*Main> niceSumPartial [1 .. 10]
55

節(jié)

Haskell 提供了一種方便的符號(hào)快捷方式，用于對(duì)中序函數(shù)進(jìn)行部分應(yīng)用：使用括號(hào)包圍一個(gè)操作符，通過(guò)在括號(hào)里面提供左操作對(duì)象或者右操作對(duì)象，可以產(chǎn)生一個(gè)部分應(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é)提供左操作對(duì)象，那么得出的部分函數(shù)就會(huì)將接收到的參數(shù)應(yīng)用為右操作對(duì)對(duì)象，反之亦然。

以下兩個(gè)表達(dá)式都計(jì)算 2 的 3 次方，但是第一個(gè)節(jié)接受的是左操作對(duì)象 2 ，而第二個(gè)節(jié)接受的則是右操作對(duì)象 3 。

Prelude> (2^) 3
8

Prelude> (^3) 2
8

之前提到過(guò)，通過(guò)使用反括號(hào)來(lái)包圍一個(gè)函數(shù)，可以將這個(gè)函數(shù)用作中序操作符。這種用法可以讓節(jié)使用函數(shù)：

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

上面的定義將 ['a'..'z'] 傳給 elem 作為第二個(gè)參數(shù)，表達(dá)式返回的函數(shù)可以用于檢查一個(gè)給定字符值是否屬于小寫字母：

Prelude> (`elem` ['a' .. 'z']) 'f'
True

Prelude> (`elem` ['a' .. 'z']) '1'
False

還可以將這個(gè)節(jié)用作 all 函數(shù)的輸入，這樣就得到了一個(gè)檢查給定字符串是否整個(gè)字符串都由小寫字母組成的函數(shù)：

Prelude> all (`elem` ['a' .. 'z']) "Haskell"
False

Prelude> all (`elem` ['a' .. 'z']) "haskell"
True

通過(guò)這種用法，可以再一次提升 isInAny3 函數(shù)的可讀性：

-- file: ch04/isInAny4.hs

import Data.List (isInfixOf)

isInAny4 needle haystack = any (needle `isInfixOf`) haystack

[譯注：根據(jù)前面部分函數(shù)部分提到的技術(shù)，這個(gè) isInAny4 的定義還可以進(jìn)一步精簡(jiǎn)，去除 haystack 參數(shù)：

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

]

As-模式

Data.List 模塊里定義的 tails 函數(shù)是 tail 的推廣，它返回一個(gè)列表的所有“尾巴”：

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 返回一個(gè)包含字符串的列表，這個(gè)列表保存了輸入字符串的所有后綴，以及一個(gè)額外的空列表（放在結(jié)果列表的最后）。tails 的返回值總是帶有額外的空列表，即使它的輸入為空時(shí)：

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

如果想要一個(gè)行為和 tails 類似，但是并不包含空列表后綴的函數(shù)，可以自己寫一個(gè)：

-- file: ch04/suffixes.hs

suffixes :: [a] -> [[a]]
suffixes xs@(_:xs') = xs : suffixes xs'
suffixes [] = []

[譯注：在稍后的章節(jié)就會(huì)看到，有簡(jiǎn)單得多的方法來(lái)完成這個(gè)目標(biāo)，這個(gè)例子主要用于展示 as-模式的作用。]

源碼里面用到了新引入的 @ 符號(hào)，模式 xs@(:xs') 被稱為 as-模式，它的意思是：如果輸入值能匹配 @ 符號(hào)右邊的模式（這里是 (:xs') ），那么就將這個(gè)值綁定到 @ 符號(hào)左邊的變量中（這里是 xs ）。

在這個(gè)例子里，如果輸入值能夠匹配模式 (:xs') ，那么這個(gè)輸入值這就被綁定為 xs ，它的 tail 部分被綁定為 xs' ，而它的 head 部分因?yàn)槭褂猛ㄅ浞? 進(jìn)行匹配，所以這部分沒有被綁定到任何變量。

*Main Data.List> tails "foo"
["foo","oo","o",""]

*Main Data.List> suffixes "foo"
["foo","oo","o"]

As-模式可以提升代碼的可讀性，作為對(duì)比，以下是一個(gè)沒有使用 as-模式的 suffixes 定義：

-- file: noAsPattern.hs

noAsPattern :: [a] -> [[a]]
noAsPattern (x:xs) = (x:xs) : noAsPattern xs
noAsPattern [] = []

可以看到，使用 as-模式的定義同時(shí)完成了模式匹配和變量綁定兩項(xiàng)工作。而不使用 as-模式的定義，則需要在對(duì)列表進(jìn)行結(jié)構(gòu)之后，在函數(shù)體里又重新對(duì)列表進(jìn)行組合。

除了增強(qiáng)可讀性之外， as-模式還有其他作用：它可以對(duì)輸入數(shù)據(jù)進(jìn)行共享，而不是復(fù)制它。在 noAsPattern 函數(shù)的定義中，當(dāng) (x:xs) 匹配時(shí)，在函數(shù)體里需要復(fù)制一個(gè) (x:xs) 的副本。這個(gè)動(dòng)作會(huì)引起內(nèi)存分配。雖然這個(gè)分配動(dòng)作可能很廉價(jià)，但它并不是免費(fèi)的。相反，當(dāng)使用 suffixes 函數(shù)時(shí)，我們通過(guò)變量 xs 重用匹配了 as-模式的輸入值，因此就避免了內(nèi)存分配。

通過(guò)組合函數(shù)來(lái)進(jìn)行代碼復(fù)用

前面的 suffixes 函數(shù)實(shí)際上有一種更簡(jiǎn)單的實(shí)現(xiàn)方式。

回憶前面在《使用列表》一節(jié)里介紹的 init 函數(shù)，它可以返回一個(gè)列表中除了最后一個(gè)元素之外的其他元素。而組合使用 init 和 tails ，可以給出一個(gè) suffixes 函數(shù)的更簡(jiǎn)單實(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ì)地觀察，就會(huì)發(fā)現(xiàn)這里隱含著一個(gè)模式：我們先應(yīng)用一個(gè)函數(shù)，然后又將這個(gè)函數(shù)得出的結(jié)果應(yīng)用到另一個(gè)函數(shù)?？梢詫⑦@個(gè)模式定義為一個(gè)函數(shù)：

-- file: ch04/compose.hs

compose :: (b -> c) -> (a -> b) -> a -> c
compose f g x = f (g x)

compose 函數(shù)可以用于粘合兩個(gè)函數(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

通過(guò)柯里化，可以丟掉 xs 函數(shù)：

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

更棒的是，其實(shí)我們并不需要自己編寫 compose 函數(shù)，因?yàn)?Haskell 已經(jīng)內(nèi)置在了 Prelude 里面，使用 (.) 操作符就可以組合起兩個(gè)函數(shù)：

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

(.) 操作符并不是什么特殊語(yǔ)法，它只是一個(gè)普通的操作符：

*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í)候，都可以通過(guò)使用 (.) 來(lái)組合函數(shù)，并產(chǎn)生新函數(shù)。組合鏈的長(zhǎng)度并沒有限制，只要 (.) 符號(hào)右邊函數(shù)的輸出值類型適用于 (.) 符號(hào)左邊函數(shù)的輸入值類型就可以了。

也即是，對(duì)于 f.g 來(lái)說(shuō)， g 的輸出值必須是 f 能接受的類型，這樣的組合就是合法的， (.) 的類型簽名也顯示了這一點(diǎn)。

作為例子，再來(lái)解決一個(gè)非常常見的問(wèn)題：計(jì)算字符串中以大寫字母開頭的單詞的個(gè)數(shù)：

Prelude> :module +Data.Char

Prelude Data.Char> let capCount = length . filter (isUpper . head) . words

Prelude Data.Char> capCount "Hello there, Mon!"
2

來(lái)逐步分析 capCount 函數(shù)的組合過(guò)程。因?yàn)?(.) 操作符是右關(guān)聯(lián)的，因此我們從組合鏈的最右邊開始研究：

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

words 返回一個(gè) [String] 類型值，因此 (.) 的左邊的函數(shù)必須能接受這個(gè)參數(shù)。

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

上面的組合函數(shù)在輸入字符串以大寫字母開頭時(shí)返回 True ，因此 filter(isUpper.head) 表達(dá)式會(huì)返回所有以大寫字母開頭的字符串：

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

因?yàn)檫@個(gè)表達(dá)式返回一個(gè)列表，而 length 函數(shù)用于統(tǒng)計(jì)列表的長(zhǎng)度，所以 length.filter(isUpper.head) 就計(jì)算出了所有以大寫字母開頭的字符串的個(gè)數(shù)。

以下是另一個(gè)例子，它從 libpcap —— 一個(gè)流行的網(wǎng)絡(luò)包過(guò)濾庫(kù)中提取 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 這種名字。以下是程序的定義，它將整個(gè)文件看作是一個(gè)字符串，先使用 lines 對(duì)文件進(jìn)行按行分割，再將 foldrstep[] 應(yīng)用到各行當(dāng)中，其中 step 輔助函數(shù)用于過(guò)濾和提取符合格式的宏名字：

-- 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

程序通過(guò)守衛(wèi)表達(dá)式來(lái)過(guò)濾輸入：如果輸入字符串符合給定格式，就將它加入到結(jié)果列表里；否則，就略過(guò)這個(gè)字符串，繼續(xù)處理剩余的輸入字符串。

至于 secondWord 函數(shù)，它先取出一個(gè)列表的 tail 部分，得出一個(gè)新列表。再取出新列表的 head 部分，等同于取出一個(gè)列表的第二個(gè)元素。

[譯注：書本的這個(gè)程序弱爆了，以下是 dlts 的一個(gè)更直觀的版本，它使用 filter 來(lái)過(guò)濾輸入，只保留符合格式的輸入，而不是使用復(fù)雜且難看的顯式遞歸和守衛(wèi)來(lái)進(jìn)行過(guò)濾：

-- file: ch04/dlts2.hs

import Data.List (isPrefixOf)

dlts2 :: String -> [String]
dlts2 = map (head . tail . words) . filter ("#define DLT_" `isPrefixOf`) . lines

]

編寫可讀代碼的提示

目前為止，我們知道 Haskell 有兩個(gè)非常誘人的特性：尾遞歸和匿名函數(shù)。但是，這兩個(gè)特性通常并不被使用。

對(duì)列表的處理操作一般可以通過(guò)組合庫(kù)函數(shù)比如 map 、 take 和 filter 來(lái)進(jìn)行。當(dāng)然，熟悉這些庫(kù)函數(shù)需要一定的時(shí)間，不過(guò)掌握這些函數(shù)之后，就可以使用它們寫出更快更好更少 bug 的代碼。

庫(kù)函數(shù)比尾遞歸更好的原因很簡(jiǎn)單：尾遞歸和命令式語(yǔ)言里的 loop 有同樣的問(wèn)題 —— 它們太通用（general）了。在一個(gè)尾遞歸里，你可以同時(shí)執(zhí)行過(guò)濾（filtering）、映射（mapping）和其他別的動(dòng)作。這強(qiáng)迫代碼的閱讀者（可能是你自己）必須弄懂整個(gè)遞歸函數(shù)的定義，才能理解這個(gè)函數(shù)到底做了些什么。與此相反，map 和其他很多列表函數(shù)，都只專注于做一件事。通過(guò)這些函數(shù)，我們可以很快理解某段代碼到底做了什么，以及整個(gè)程序想表達(dá)什么意思，而不是將時(shí)間浪費(fèi)在關(guān)注細(xì)節(jié)方面。

折疊（fold）操作處于（完全通用化的）尾遞歸和（只做一件事的）列表處理函數(shù)之間的中間地帶。折疊也很值得我們花時(shí)間去好好理解，它的作用跟組合起 map 和 filter 函數(shù)差不多，但比起顯式遞歸來(lái)說(shuō)，折疊的行為要來(lái)得更有規(guī)律，而且更可控。一般來(lái)說(shuō)，可以通過(guò)組合函數(shù)來(lái)解決的問(wèn)題，就不要使用折疊。另一方面，如果問(wèn)題用組合函數(shù)沒辦法解決，那么使用折疊要比使用顯式遞歸要好。

另一方面，匿名函數(shù)通常會(huì)對(duì)代碼的可讀性造成影響。一般來(lái)說(shuō)，匿名函數(shù)都可以用 let 或者 where 定義的局部函數(shù)來(lái)代替。而且?guī)值木植亢瘮?shù)可以達(dá)到一箭雙雕的效果：它使得代碼更具可讀性，且函數(shù)名本身也達(dá)到了文檔化的作用。

內(nèi)存泄漏和嚴(yán)格求值

前面介紹的 foldl 函數(shù)并不是 Haskell 代碼里唯一會(huì)造成內(nèi)存泄漏的地方。

在這一節(jié)，我們使用 foldl 來(lái)展示非嚴(yán)格求值在什么情況下會(huì)造成問(wèn)題，以及如何去解決這些問(wèn)題。

通過(guò) seq 函數(shù)避免內(nèi)存泄漏

我們稱非惰性求值的表達(dá)式為嚴(yán)格的（strict）。 foldl' 就是左折疊的嚴(yán)格版本，它使用特殊的 seq 函數(shù)來(lái)繞過(guò) 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ù)的類型簽名和之前看過(guò)的函數(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

]

實(shí)際上， seq 函數(shù)的行為并沒有那么神秘：它強(qiáng)迫（force）求值傳入的第一個(gè)參數(shù)，然后返回它的第二個(gè)參數(shù)。

比如說(shuō)，對(duì)于以下表達(dá)式：

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

它展開為：

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

它強(qiáng)迫 new 求值為 3 ，然后返回它的第二個(gè)參數(shù)：

foldl' (+) 3 []

最終得到結(jié)果 3 。

因?yàn)?seq 的存在，這個(gè)創(chuàng)建過(guò)程沒有用到任何塊。

seq 的用法

本節(jié)介紹一些更有效地使用 seq 的指導(dǎo)規(guī)則。

要正確地產(chǎn)生 seq 的作用，表達(dá)式中被求值的第一個(gè)必須是 seq ：

-- 錯(cuò)誤：因?yàn)楸磉_(dá)式中第一個(gè)被求值的是 someFunc