http://wiki.jikexueyuan.com/project/haskell-guide/images/sun.png" alt="" />

Haskell 中的函數(shù)可以作為參數(shù)和回傳值傳來傳去，這樣的函數(shù)就被稱作高階函數(shù)。高階函數(shù)可不只是某簡單特性而已，它貫穿于 Haskell 的方方面面。要拒絕循環(huán)與狀態(tài)的改變而通過定義問題"是什么"來解決問題，高階函數(shù)必不可少。它們是編碼的得力工具。

Curried functions

本質(zhì)上，Haskell 的所有函數(shù)都只有一個參數(shù)，那么我們先前編那么多含有多個參數(shù)的函數(shù)又是怎么回事? 呵，小伎倆! 所有多個參數(shù)的函數(shù)都是 Curried functions。 什么意思呢? 取一個例子最好理解，就拿我們的好朋友 max 函數(shù)說事吧。它看起來像是取兩個參數(shù)，回傳較大的那個數(shù)。 實際上，執(zhí)行 max 4 5 時，它會首先回傳一個取一個參數(shù)的函數(shù)，其回傳值不是 4 就是該參數(shù)，取決于誰大。 然后，以 5 為參數(shù)呼叫它，并取得最終結(jié)果。 這聽著挺繞口的，不過這一概念十分的酷! 如下的兩個呼叫是等價的：

ghci> max 4 5
5
ghci> (max 4) 5
5

http://wiki.jikexueyuan.com/project/haskell-guide/images/curry.png" alt="" />

把空格放到兩個東西之間，稱作函數(shù)呼叫。它有點像個運算符，并擁有最高的優(yōu)先順序。 看看 max 函數(shù)的型別: max :: (Ord a) => a -> a -> a。 也可以寫作: max :: (Ord a) => a -> (a -> a)。 可以讀作 max 取一個參數(shù) a，并回傳一個函數(shù)(就是那個 ->)，這個函數(shù)取一個 a 型別的參數(shù)，回傳一個a。 這便是為何只用箭頭來分隔參數(shù)和回傳值型別。

這樣的好處又是如何? 簡言之，我們?nèi)粢圆蝗膮?shù)來呼叫某函數(shù)，就可以得到一個不全呼叫的函數(shù)。 如果你高興，構(gòu)造新函數(shù)就可以如此便捷，將其傳給另一個函數(shù)也是同樣方便。

看下這個函數(shù)，簡單至極:

multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z

我們?nèi)魣?zhí)行 mulThree 3 5 9 或 ((mulThree 3) 5) 9，它背后是如何運作呢？ 首先，按照空格分隔，把 3 交給 mulThree。 這回傳一個回傳函數(shù)的函數(shù)。 然后把 5 交給它，回傳一個取一個參數(shù)并使之乘以 15 的函數(shù)。 最后把 9 交給這一函數(shù)，回傳 135。 想想，這個函數(shù)的型別也可以寫作 multThree :: (Num a) => a -> (a -> (a -> a))，-> 前面的東西就是函數(shù)取的參數(shù)，后面的東西就是其回傳值。所以說，我們的函數(shù)取一個 a，并回傳一個型別為 (Num a) => a -> (a -> a) 的函數(shù)，類似，這一函數(shù)回傳一個取一個 a，回傳一個型別為 (Num a) => a -> a 的函數(shù)。 而最后的這個函數(shù)就只取一個 a 并回傳一個 a，如下:

ghci> let multTwoWithNine = multThree 9
ghci> multTwoWithNine 2 3
54
ghci> let multWithEighteen = multTwoWithNine 2
ghci> multWithEighteen 10
180

前面提到，以不全的參數(shù)呼叫函數(shù)可以方便地創(chuàng)造新的函數(shù)。例如，搞個取一數(shù)與 100 比較大小的函數(shù)該如何? 大可這樣:

compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x

用 99 呼叫它，就可以得到一個 GT。 簡單。 注意下在等號兩邊都有 x。 想想 compare 100 會回傳什么？一個取一數(shù)與 100 比較的函數(shù)。 Wow，這不正是我們想要的? 這樣重寫:

compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100

型別聲明依然相同，因為 compare 100 回傳函數(shù)。compare 的型別為 (Ord a) => a -> (a -> Ordering)，用 100 呼叫它后回傳的函數(shù)型別為 (Num a, Ord a) => a -> Ordering，同時由于 100 還是 Num 型別類的實例，所以還得另留一個類約束。

Yo! 你得保證已經(jīng)弄明白了 Curried functions 與不全呼叫的原理，它們很重要！

中綴函數(shù)也可以不全呼叫，用括號把它和一邊的參數(shù)括在一起就行了。 這回傳一個取一參數(shù)并將其補到缺少的那一端的函數(shù)。 一個簡單函數(shù)如下:

divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

呼叫 divideByTen 200 就是 (/10) 200，和 200 / 10 等價。

一個檢查字元是否為大寫的函數(shù):

isUpperAlphanum :: Char -> Bool
isUpperAlphanum = (`elem` ['A'..'Z'])

唯一的例外就是 - 運算符，按照前面提到的定義，(-4) 理應回傳一個并將參數(shù)減 4 的函數(shù)，而實際上，處于計算上的方便，(-4) 表示負 4。 若你一定要弄個將參數(shù)減 4 的函數(shù)，就用 subtract 好了，像這樣 (subtract 4).

若不用 let 給它命名或傳到另一函數(shù)中，在 ghci 中直接執(zhí)行 multThree 3 4 會怎樣?

ghci> multThree 3 4
:1:0:
No instance for (Show (t -> t))
arising from a use of `print' at :1:0-12
Possible fix: add an instance declaration for (Show (t -> t))
In the expression: print it
In a 'do' expression: print it

ghci 說，這一表達式回傳了一個 a -> a 型別的函數(shù)，但它不知道該如何顯示它。 函數(shù)不是 Show 型別類的實例，所以我們不能得到表示一函數(shù)內(nèi)容的字串。 若在 ghci 中計算 1+1，它會首先計算得 2，然后呼叫 show 2 得到該數(shù)值的字串表示，即 "2"，再輸出到屏幕.

是時候了，來點高階函數(shù)！

Haskell 中的函數(shù)可以取另一個函數(shù)做參數(shù)，也可以回傳函數(shù)。 舉個例子，我們弄個取一個函數(shù)并呼叫它兩次的函數(shù).

applyTwice :: (a -> a) -> a -> a  
applyTwice f x = f (f x)  

http://wiki.jikexueyuan.com/project/haskell-guide/images/bonus.png" alt="" />

首先注意這型別聲明。 在此之前我們很少用到括號，因為 (->) 是自然的右結(jié)合，不過在這里括號是必須的。 它標明了首個參數(shù)是個參數(shù)與回傳值型別都是a的函數(shù)，第二個參數(shù)與回傳值的型別也都是a。 我們可以用 Curried functions 的思路來理解這一函數(shù)，不過免得自尋煩惱，我們姑且直接把它看作是取兩個參數(shù)回傳一個值，其首個參數(shù)是個型別為 (a->a) 的函數(shù),第二個參數(shù)是個 a。 該函數(shù)的型別可以是 (Int->Int)，也可以是 (String->String)，但第二個參數(shù)必須與之一致。

*Note*: 現(xiàn)在開始我們會直說某函數(shù)含有多個參數(shù)(除非它真的只有一個參數(shù))。 以簡潔之名，我們會說 ``(a->a->a)`` 取兩個參數(shù)，盡管我們知道它在背后做的手腳.

這個函數(shù)是相當?shù)暮唵危湍脜?shù) f 當函數(shù)，用 x 呼叫它得到的結(jié)果再去呼叫它。也就可以這樣玩:

ghci> applyTwice (+3) 10  
16  
ghci> applyTwice (++ " HAHA") "HEY"  
"HEY HAHA HAHA"  
ghci> applyTwice ("HAHA " ++) "HEY"  
"HAHA HAHA HEY"  
ghci> applyTwice (multThree 2 2) 9  
144  
ghci> applyTwice (3:) [1]  
[3,3,1]  

看，不全呼叫多神奇! 如果有個函數(shù)要我們給它傳個一元函數(shù)，大可以不全呼叫一個函數(shù)讓它剩一個參數(shù)，再把它交出去。

接下來我們用高階函數(shù)的編程思想來實現(xiàn)個標準庫中的函數(shù)，它就是 zipWith。 它取一個函數(shù)和兩個 List 做參數(shù)，并把兩個 List 交到一起(使相應的元素去呼叫該函數(shù))。 如下就是我們的實現(xiàn):

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]  
zipWith' _ [] _ = []  
zipWith' _ _ [] = []  
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys  

看下這個型別聲明，它的首個參數(shù)是個函數(shù)，取兩個參數(shù)處理交叉，其型別不必相同，不過相同也沒關(guān)系。 第二三個參數(shù)都是 List，回傳值也是個 List。 第一個 List中元素的型別必須是a，因為這個處理交叉的函數(shù)的第一個參數(shù)是a。 第二個 List 中元素的型別必為 b，因為這個處理交叉的函數(shù)第二個參數(shù)的型別是 b。 回傳的 List 中元素型別為 c。 如果一個函數(shù)說取一個型別為 a->b->c 的函數(shù)做參數(shù)，傳給它個 a->a->c 型別的也是可以的，但反過來就不行了。 可以記下，若在使用高階函數(shù)的時候不清楚其型別為何，就先忽略掉它的型別聲明，再到 ghci 下用 :t 命令來看下 Haskell 的型別推導.

這函數(shù)的行為與普通的 zip 很相似，邊界條件也是相同，只不過多了個參數(shù)，即處理元素交叉的函數(shù)。它關(guān)不著邊界條件什么事兒，所以我們就只留一個 _。后一個模式的函數(shù)體與 zip 也很像，只不過這里是 f x y 而非 (x,y)。 只要足夠通用，一個簡單的高階函數(shù)可以在不同的場合反復使用。 如下便是我們 zipWith' 函數(shù)本領(lǐng)的冰山一角:

ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]  
[6,8,7,9]  
ghci> zipWith' max [6,3,2,1] [7,3,1,5]  
[7,3,2,5]  
ghci> zipWith' (++) ["foo "，"bar "，"baz "] ["fighters"，"hoppers"，"aldrin"]  
["foo fighters","bar hoppers","baz aldrin"]  
ghci> zipWith' (*) (replicate 5 2) [1..]  
[2,4,6,8,10]  
ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]  
[[3,4,6],[9,20,30],[10,12,12]]  

如你所見，一個簡單的高階函數(shù)就可以玩出很多花樣。命令式語言使用 for、while、賦值、狀態(tài)檢測來實現(xiàn)功能，再包起來留個介面，使之像個函數(shù)一樣呼叫。而函數(shù)式語言使用高階函數(shù)來抽象出常見的模式，像成對遍歷并處理兩個 List 或從中篩掉自己不需要的結(jié)果。

接下來實現(xiàn)標準庫中的另一個函數(shù) flip，flip簡單地取一個函數(shù)作參數(shù)并回傳一個相似的函數(shù)，只是它們的兩個參數(shù)倒了個。

flip' :: (a -> b -> c) -> (b -> a -> c)  
flip' f = g  
    where g x y = f y x  

從這型別聲明中可以看出，它取一個函數(shù)，其參數(shù)型別分別為 a 和 b，而它回傳的函數(shù)的參數(shù)型別為 b 和 a。 由于函數(shù)預設(shè)都是柯里化的，-> 為右結(jié)合，這里的第二對括號其實并無必要，(a -> b -> c) -> (b -> a -> c) 與 (a -> b -> c) -> (b -> (a -> c)) 等價,也與 (a -> b -> c) -> b -> a -> c 等價。 前面我們寫了 g x y = f y x，既然這樣可行，那么 f y x = g x y 不也一樣? 這一來我們可以改成更簡單的寫法:

flip' :: (a -> b -> c) -> b -> a -> c  
flip' f y x = f x y  

在這里我們就利用了 Curried functions 的優(yōu)勢，只要呼叫 flip' f 而不帶 y和x，它就會回傳一個倆參數(shù)倒個的函數(shù)。 flip 處理的函數(shù)往往都是用來傳給其他函數(shù)呼叫，于是我們可以發(fā)揮 Curried functions 的優(yōu)勢，預先想好發(fā)生完全呼叫的情景并處理好回傳值.

ghci> flip' zip [1,2,3,4,5] "hello"  
[('h',1),('e',2),('l',3),('l',4),('o',5)]  
ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]  
[5,4,3,2,1]

map 與 filter

map 取一個函數(shù)和 List 做參數(shù)，遍歷該 List 的每個元素來呼叫該函數(shù)產(chǎn)生一個新的 List。 看下它的型別聲明和實現(xiàn):

map :: (a -> b) -> [a] -> [b]  
map _ [] = []  
map f (x:xs) = f x : map f xs

從這型別聲明中可以看出，它取一個取 a 回傳 b 的函數(shù)和一組 a 的 List，并回傳一組 b。 這就是 Haskell 的有趣之處：有時只看型別聲明就能對函數(shù)的行為猜個大致。map 函數(shù)多才多藝，有一百萬種用法。如下是其中一小部分:

ghci> map (+3) [1,5,3,1,6]  
[4,8,6,4,9]  
ghci> map (++ "!") ["BIFF"，"BANG"，"POW"]  
["BIFF!","BANG!","POW!"]  
ghci> map (replicate 3) [3..6]  
[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]  
ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]  
[[1,4],[9,16,25,36],[49,64]]  
ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)]  
[1,3,6,2,2]  

你可能會發(fā)現(xiàn)，以上的所有程式碼都可以用 List Comprehension 來替代。map (+3) [1,5,3,1,6] 與 [x+3 | x <- [1,5,3,1,6] 完全等價。

filter 函數(shù)取一個限制條件和一個 List，回傳該 List 中所有符合該條件的元素。它的型別聲明及實現(xiàn)大致如下:

filter :: (a -> Bool) -> [a] -> [a]  
filter _ [] = []  
filter p (x:xs)   
    | p x       = x : filter p xs  
    | otherwise = filter p xs  

很簡單。只要 p x 所得的結(jié)果為真，就將這一元素加入新 List，否則就無視之。幾個使用范例:

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]  
[5,6,4]  
ghci> filter (==3) [1,2,3,4,5]  
[3]  
ghci> filter even [1..10]  
[2,4,6,8,10]  
ghci> let notNull x = not (null x) in filter notNull [[1,2,3],[],[3,4,5],[2,2],[],[],[]]  
[[1,2,3],[3,4,5],[2,2]]  
ghci> filter (`elem` ['a'..'z']) "u LaUgH aT mE BeCaUsE I aM diFfeRent"  
"uagameasadifeent"  
ghci> filter (`elem` ['A'..'Z']) "i lauGh At You BecAuse u r aLL the Same"  
"GAYBALLS"  

同樣，以上都可以用 List Comprehension 的限制條件來實現(xiàn)。并沒有教條規(guī)定你必須在什么情況下用 map 和 filter 還是 List Comprehension，選擇權(quán)歸你，看誰舒服用誰就是。 如果有多個限制條件，只能連著套好幾個 filter 或用 && 等邏輯函數(shù)的組合之，這時就不如 List comprehension 來得爽了。

還記得上一章的那個 quicksort 函數(shù)么? 我們用到了 List Comprehension 來過濾大于或小于錨的元素。 換做 filter 也可以實現(xiàn)，而且更加易讀：

quicksort :: (Ord a) => [a] -> [a]    
quicksort [] = []    
quicksort (x:xs) =     
    let smallerSorted = quicksort (filter (<=x) xs)
        biggerSorted = quicksort (filter (>x) xs)   
    in  smallerSorted ++ [x] ++ biggerSorted  

http://wiki.jikexueyuan.com/project/haskell-guide/images/map.png" alt="" />

map 和 filter 是每個函數(shù)式程序員的面包黃油(呃，map 和 filter 還是 List Comprehension 并不重要)。 想想前面我們?nèi)绾谓鉀Q給定周長尋找合適直角三角形的問題的? 在命令式編程中，我們可以套上三個循環(huán)逐個測試當前的組合是否滿足條件，若滿足，就打印到屏幕或其他類似的輸出。 而在函數(shù)式編程中，這行就都交給 map 和 filter。 你弄個取一參數(shù)的函數(shù)，把它交給 map 過一遍 List，再 filter 之找到合適的結(jié)果。 感謝 Haskell 的惰性，即便是你多次 map 一個 `List 也只會遍歷一遍該 List，要找出小于 100000 的數(shù)中最大的 3829 的倍數(shù)，只需過濾結(jié)果所在的 List 就行了.

要找出小于 100000 的 3829 的所有倍數(shù)，我們應當過濾一個已知結(jié)果所在的 List.

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0  

首先，取一個降序的小于 100000 所有數(shù)的 List，然后按照限制條件過濾它。 由于這個 List 是降序的，所以結(jié)果 List 中的首個元素就是最大的那個數(shù)。惰性再次行動! 由于我們只取這結(jié)果 List 的首個元素，所以它并不關(guān)心這 List 是有限還是無限的，在找到首個合適的結(jié)果處運算就停止了。

接下來，我們就要找出所有小于 10000 的奇數(shù)的平方和，得先提下 takeWhile 函數(shù)，它取一個限制條件和 List 作參數(shù)，然后從頭開始遍歷這一 List，并回傳符合限制條件的元素。 而一旦遇到不符合條件的元素，它就停止了。 如果我們要取出字串 "elephants know how to party" 中的首個單詞，可以 takeWhile (/=' ') "elephants know how to party"，回傳 "elephants"。okay，要求所有小于 10000 的奇數(shù)的平方的和，首先就用 (^2) 函數(shù) map 掉這個無限的 List [1..] 。然后過濾之，只取奇數(shù)就是了。 在大于 10000 處將它斷開，最后前面的所有元素加到一起。 這一切連寫函數(shù)都不用，在 ghci 下直接搞定.

ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))  
166650  

不錯! 先從幾個初始數(shù)據(jù)(表示所有自然數(shù)的無限 List)，再 map 它，filter 它，切它，直到它符合我們的要求，再將其加起來。 這用 List comprehension 也是可以的，而哪種方式就全看你的個人口味.

ghci> sum (takeWhile (<10000) [m | m <- [n^2 | n <- [1..]], odd m])  
166650  

感謝 Haskell 的惰性特質(zhì)，這一切才得以實現(xiàn)。 我們之所以可以 map 或 filter 一個無限 List，是因為它的操作不會被立即執(zhí)行，而是拖延一下。只有我們要求 Haskell 交給我們 sum 的結(jié)果的時候，sum 函數(shù)才會跟 takeWhile 說，它要這些數(shù)。takeWhile 就再去要求 filter 和 map 行動起來，并在遇到大于等于 10000 時候停止. 下個問題與 Collatz 序列有關(guān)，取一個自然數(shù)，若為偶數(shù)就除以 2。 若為奇數(shù)就乘以 3 再加 1。 再用相同的方式處理所得的結(jié)果，得到一組數(shù)字構(gòu)成的的鏈。它有個性質(zhì)，無論任何以任何數(shù)字開始，最終的結(jié)果都會歸 1。所以若拿 13 當作起始數(shù)，就可以得到這樣一個序列 13，40，20，10，5，16，8，4，2，1。13*3+1 得 40，40 除 2 得 20，如是繼續(xù)，得到一個 10 個元素的鏈。

好的，我們想知道的是: 以 1 到 100 之間的所有數(shù)作為起始數(shù)，會有多少個鏈的長度大于 15?

chain :: (Integral a) => a -> [a]  
chain 1 = [1]  
chain n  
    | even n =  n:chain (n `div` 2)  
    | odd n  =  n:chain (n*3 + 1)  

該鏈止于 1，這便是邊界條件。標準的遞歸函數(shù):

ghci> chain 10  
[10,5,16,8,4,2,1]  
ghci> chain 1  
[1]  
ghci> chain 30  
[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]  

yay! 貌似工作良好。 現(xiàn)在由這個函數(shù)來告訴我們結(jié)果:

numLongChains :: Int  
numLongChains = length (filter isLong (map chain [1..100]))  
    where isLong xs = length xs > 15  

我們把 chain 函數(shù) map 到 [1..100]，得到一組鏈的 List，然后用個限制條件過濾長度大于 15 的鏈。過濾完畢后就可以得出結(jié)果list中的元素個數(shù).

*Note*: 這函數(shù)的型別為 ``numLongChains :: Int``。這是由于歷史原因，``length`` 回傳一個 ``Int`` 而非 ``Num`` 的成員型別，若要得到一個更通用的 ``Num a``，我們可以使用 ``fromIntegral`` 函數(shù)來處理所得結(jié)果.

用 map，我們可以寫出類似 map (*) [0..] 之類的程式碼。 如果只是為了例證 Curried functions 和不全呼叫的函數(shù)是真正的值及其原理，那就是你可以把函數(shù)傳遞或把函數(shù)裝在 List 中(只是你還不能將它們轉(zhuǎn)換為字串)。 迄今為止，我們還只是 map 單參數(shù)的函數(shù)到 List，如 map (*2) [0..] 可得一組型別為 (Num a) => [a] 的 List，而 map (*) [0..] 也是完全沒問題的。* 的型別為 (Num a) => a -> a -> a，用單個參數(shù)呼叫二元函數(shù)會回傳一個一元函數(shù)。如果用 * 來 map 一個 [0..] 的 List，就會得到一組一元函數(shù)組成的 List，即 (Num a) => [a->a]。map (*) [0..] 所得的結(jié)果寫起來大約就是 [(0*),(1*),(2*)..].

ghci> let listOfFuns = map (*) [0..]  
ghci> (listOfFuns !! 4) 5  
20

取所得 List 的第四個元素可得一函數(shù)，與 (*4) 等價。 然后用 5 呼叫它，與 (* 4) 5 或 4*5 都是等價的.

lambda

http://wiki.jikexueyuan.com/project/haskell-guide/images/lamb.png" alt="" />

lambda 就是匿名函數(shù)。有些時候我們需要傳給高階函數(shù)一個函數(shù)，而這函數(shù)我們只會用這一次，這就弄個特定功能的 lambda。編寫 lambda，就寫個 \ (因為它看起來像是希臘字母的 lambda -- 如果你斜視的厲害)，后面是用空格分隔的參數(shù)，-> 后面就是函數(shù)體。通常我們都是用括號將其括起，要不然它就會占據(jù)整個右邊部分。

向上 5 英吋左右，你會看到我們在 numLongChain 函數(shù)中用 where 語句聲明了個 isLong 函數(shù)傳遞給了 filter。好的，用 lambda 代替它。

numLongChains :: Int  
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))  

http://wiki.jikexueyuan.com/project/haskell-guide/images/lambda.png" alt="" />

lambda 是個表達式，因此我們可以任意傳遞。表達式 (\xs -> length xs > 15) 回傳一個函數(shù)，它可以告訴我們一個 List 的長度是否大于 15。

不熟悉 Curried functions 與不全呼叫的人們往往會寫出很多 lambda，而實際上大部分都是沒必要的。例如，表達式 map (+3) [1,6,3,2] 與 map (\x -> x+3) [1,6,3,2] 等價，(+3) 和 (\x -> x+3) 都是給一個數(shù)加上 3。不用說，在這種情況下不用 lambda 要清爽的多。

和普通函數(shù)一樣，lambda 也可以取多個參數(shù)。

ghci> zipWith (\a b -> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5]  
[153.0,61.5,31.0,15.75,6.6] 

同普通函數(shù)一樣，你也可以在 lambda 中使用模式匹配，只是你無法為一個參數(shù)設(shè)置多個模式，如 [] 和 (x:xs)。lambda 的模式匹配若失敗，就會引發(fā)一個運行時錯誤，所以慎用！

ghci> map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]  
[3,8,9,8,7]  

一般情況下，lambda 都是括在括號中，除非我們想要后面的整個語句都作為 lambda 的函數(shù)體。很有趣，由于有柯里化，如下的兩段是等價的：

addThree :: (Num a) => a -> a -> a -> a  
addThree x y z = x + y + z  

addThree :: (Num a) => a -> a -> a -> a  
addThree = \x -> \y -> \z -> x + y + z 

這樣的函數(shù)聲明與函數(shù)體中都有 ->，這一來型別聲明的寫法就很明白了。當然第一段程式碼更易讀，不過第二個函數(shù)使得柯里化更容易理解。

有些時候用這種語句寫還是挺酷的，我覺得這應該是最易讀的 flip 函數(shù)實現(xiàn)了：

flip' :: (a -> b -> c) -> b -> a -> c  
flip' f = \x y -> f y x  

盡管這與 flip' f x y = f y x 等價，但它可以更明白地表示出它會產(chǎn)生一個新的函數(shù)。flip 常用來處理一個函數(shù)，再將回傳的新函數(shù)傳遞給 map 或 filter。所以如此使用 lambda 可以更明確地表現(xiàn)出回傳值是個函數(shù)，可以用來傳遞給其他函數(shù)作參數(shù)。

關(guān)鍵字 fold

http://wiki.jikexueyuan.com/project/haskell-guide/images/origami.png" alt="" />

回到當初我們學習遞歸的情景。我們會發(fā)現(xiàn)處理 List 的許多函數(shù)都有固定的模式，通常我們會將邊界條件設(shè)置為空 List，再引入 (x:xs) 模式，對單個元素和余下的 List 做些事情。這一模式是如此常見，因此 Haskell 引入了一組函數(shù)來使之簡化，也就是 fold。它們與map有點像，只是它們回傳的是單個值。

一個 fold 取一個二元函數(shù)，一個初始值(我喜歡管它叫累加值)和一個需要折疊的 List。這個二元函數(shù)有兩個參數(shù)，即累加值和 List 的首項(或尾項)，回傳值是新的累加值。然后，以新的累加值和新的 List 首項呼叫該函數(shù)，如是繼續(xù)。到 List 遍歷完畢時，只剩下一個累加值，也就是最終的結(jié)果。

首先看下 foldl 函數(shù)，也叫做左折疊。它從 List 的左端開始折疊，用初始值和 List 的頭部呼叫這二元函數(shù)，得一新的累加值，并用新的累加值與 List 的下一個元素呼叫二元函數(shù)。如是繼續(xù)。

我們再實現(xiàn)下 sum，這次用 fold 替代那復雜的遞歸：

sum' :: (Num a) => [a] -> a  
sum' xs = foldl (\acc x -> acc + x) 0 xs  

測試下，一二三～

ghci> sum' [3,5,2,1]  
11

http://wiki.jikexueyuan.com/project/haskell-guide/images/foldl.png" alt="" />

我們深入看下 fold 的執(zhí)行過程：\acc x-> acc + x 是個二元函數(shù)，0 是初始值，xs 是待折疊的 List。一開始，累加值為 0，當前項為 3，呼叫二元函數(shù) 0+3 得 3，作新的累加值。接著來，累加值為 3，當前項為 5，得新累加值 8。再往后，累加值為 8，當前項為 2，得新累加值 10。最后累加值為 10，當前項為 1，得 11。恭喜，你完成了一次折疊 (fold)！

左邊的這個圖表示了折疊的執(zhí)行過程，一步又一步(一天又一天!)。淺棕色的數(shù)字都是累加值，你可以從中看出 List 是如何從左端一點點加到累加值上的。唔對對對！如果我們考慮到函數(shù)的柯里化，可以寫出更簡單的實現(xiàn)：

sum' :: (Num a) => [a] -> a  
sum' = foldl (+) 0  

這個 lambda 函數(shù) (\acc x -> acc + x ) 與 (+) 等價。我們可以把 xs 等一應參數(shù)省略掉，反正呼叫 foldl (+) 0 會回傳一個取 List 作參數(shù)的函數(shù)。通常，如果你的函數(shù)類似 foo a = bar b a， 大可改為 foo = bar b。有柯里化嘛。

呼呼，進入右折疊前我們再實現(xiàn)個用到左折疊的函數(shù)。大家肯定都知道 elem 是檢查某元素是否屬于某 List 的函數(shù)吧，我就不再提了(唔，剛提了)。用左折疊實現(xiàn)它:

elem' :: (Eq a) => a -> [a] -> Bool  
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys  

好好好，這里我們有什么？起始值與累加值都是布爾值。在處理 fold 時，累加值與最終結(jié)果的型別總是相同的。如果你不知道怎樣對待起始值，那我告訴你，我們先假設(shè)它不存在，以 False 開始。我們要是 fold 一個空 List，結(jié)果就是 False。然后我們檢查當前元素是否為我們尋找的，如果是，就令累加值為 True，如果否，就保留原值不變。若 False，及表明當前元素不是。若 True，就表明已經(jīng)找到了。

右折疊 foldr 的行為與左折疊相似，只是累加值是從 List 的右邊開始。同樣，左折疊的二元函數(shù)取累加值作首個參數(shù)，當前值為第二個參數(shù)(即 \acc x -> ...)，而右折疊的二元函數(shù)參數(shù)的順序正好相反(即 \x acc -> ...)。這倒也正常，畢竟是從右端開始折疊。

累加值可以是任何型別，可以是數(shù)值，布爾值，甚至一個新的 List。我們可以用右 fold 實現(xiàn) map 函數(shù)，累加值就是個 List。將 map 處理過的元素一個一個連到一起。很容易想到，起始值就是空 List。

map' :: (a -> b) -> [a] -> [b]  
map' f xs = foldr (\x acc -> f x : acc) [] xs  

如果我們用 (+3) 來映射 [1,2,3]，它就會先到達 List 的右端，我們?nèi)∽詈竽莻€元素，也就是 3 來呼叫 (+3)，得 6。追加 (:) 到累加值上，6:[] 得 [6] 并成為新的累加值。用 2 呼叫 (+3)，得 5，追加到累加值，于是累加值成了 [5,6]。再對 1 呼叫 (+3)，并將結(jié)果 4 追加到累加值，最終得結(jié)果 [4,5,6]。

當然，我們也完全可以用左折疊來實現(xiàn)它，map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs 就行了。不過問題是，使用 (++) 往 List 后面追加元素的效率要比使用 (:) 低得多。所以在生成新 List 的時候人們一般都是使用右折疊。

http://wiki.jikexueyuan.com/project/haskell-guide/images/washmachine.png" alt="" />

反轉(zhuǎn)一個 List，既也可以通過右折疊，也可以通過左折疊。有時甚至不需要管它們的分別，如 sum 函數(shù)的左右折疊實現(xiàn)都是十分相似。不過有個大的不同，那就是右折疊可以處理無限長度的資料結(jié)構(gòu)，而左折疊不可以。將無限 List 從中斷開執(zhí)行左折疊是可以的，不過若是向右，就永遠到不了頭了。

所有遍歷 List 中元素并據(jù)此回傳一個值的操作都可以交給 fold 實現(xiàn)。無論何時需要遍歷 List 并回傳某值，都可以嘗試下 fold。因此，fold的地位可以說與 map和 filter并駕齊驅(qū)，同為函數(shù)式編程中最常用的函數(shù)之一。

foldl1 與 foldr1 的行為與 foldl 和 foldr 相似，只是你無需明確提供初始值。他們假定 List 的首個(或末尾)元素作為起始值，并從旁邊的元素開始折疊。這一來，sum 函數(shù)大可這樣實現(xiàn)：sum = foldl1 (+)。這里待折疊的 List 中至少要有一個元素，若使用空 List 就會產(chǎn)生一個運行時錯誤。不過 foldl 和 foldr 與空 List 相處的就很好。所以在使用 fold 前，應該先想下它會不會遇到空 List，如果不會遇到，大可放心使用 foldr1 和 foldl1。

為了體會 fold 的威力，我們就用它實現(xiàn)幾個庫函數(shù)：

maximum' :: (Ord a) => [a] -> a  
maximum' = foldr1 (\x acc -> if x > acc then x else acc)  

reverse' :: [a] -> [a]  
reverse' = foldl (\acc x -> x : acc) []  

product' :: (Num a) => [a] -> a  
product' = foldr1 (*)  

filter' :: (a -> Bool) -> [a] -> [a]  
filter' p = foldr (\x acc -> if p x then x : acc else acc) []  

head' :: [a] -> a  
head' = foldr1 (\x _ -> x)  

last' :: [a] -> a  
last' = foldl1 (\_ x -> x)  

僅靠模式匹配就可以實現(xiàn) head 函數(shù)和 last 函數(shù)，而且效率也很高。這里只是為了演示，用 fold 的實現(xiàn)方法。我覺得我們這個 reverse' 定義的相當聰明，用一個空 List 做初始值，并向左展開 List，從左追加到累加值，最后得到一個反轉(zhuǎn)的新 List。\acc x -> x : acc 有點像 : 函數(shù)，只是參數(shù)順序相反。所以我們可以改成 foldl (flip (:)) []。

有個理解折疊的思路：假設(shè)我們有個二元函數(shù) f，起始值 z，如果從右折疊 [3,4,5,6]，實際上執(zhí)行的就是 f 3 (f 4 (f 5 (f 6 z)))。f 會被 List 的尾項和累加值呼叫，所得的結(jié)果會作為新的累加值傳入下一個呼叫。假設(shè) f 是 (+)，起始值 z 是 0，那么就是 3 + (4 + (5 + (6 + 0)))，或等價的首碼形式：(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))。相似，左折疊一個 List，以 g 為二元函數(shù)，z 為累加值，它就與 g (g (g (g z 3) 4) 5) 6 等價。如果用 flip (:) 作二元函數(shù)，[] 為累加值(看得出，我們是要反轉(zhuǎn)一個 List)，這就與 flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6 等價。顯而易見，執(zhí)行該表達式的結(jié)果為 [6,5,4,3]。

scanl 和 scanr 與 foldl 和 foldr 相似，只是它們會記錄下累加值的所有狀態(tài)到一個 List。也有 scanl1 和 scanr1。

ghci> scanl (+) 0 [3,5,2,1]  
[0,3,8,10,11]  
ghci> scanr (+) 0 [3,5,2,1]  
[11,8,3,1,0]  
ghci> scanl1 (\acc x -> if x > acc then x else acc) [3,4,5,3,7,9,2,1]  
[3,4,5,5,7,9,9,9]  
ghci> scanl (flip (:)) [] [3,2,1]  
[[],[3],[2,3],[1,2,3]]  

當使用 scanl 時，最終結(jié)果就是 List 的最后一個元素。而在 scanr 中則是第一個。

sqrtSums :: Int  
sqrtSums = length (takeWhile (<1000) (scanl1 (+) (map sqrt [1..]))) + 1  

ghci> sqrtSums  
131  
ghci> sum (map sqrt [1..131])  
1005.0942035344083  
ghci> sum (map sqrt [1..130])  
993.6486803921487  

scan 可以用來跟蹤 fold 函數(shù)的執(zhí)行過程。想想這個問題，取所有自然數(shù)的平方根的和，尋找在何處超過 1000？ 先map sqrt [1..]，然后用個 fold 來求它們的和。但在這里我們想知道求和的過程，所以使用 scan，scan 完畢時就可以得到小于 1000 的所有和。所得結(jié)果 List 的第一個元素為 1，第二個就是 1+根2，第三個就是 1+根2+根3。若有 x 個和小于 1000，那結(jié)果就是 x+1。

有$的函數(shù)呼叫

好的，接下來看看 $ 函數(shù)。它也叫作函數(shù)呼叫符。先看下它的定義：

($) :: (a -> b) -> a -> b  
f $ x = f x  

http://wiki.jikexueyuan.com/project/haskell-guide/images/dollar.png" alt="" />

什么鬼東西？這沒啥意義的操作符？它只是個函數(shù)呼叫符罷了？好吧，不全是，但差不多。普通的函數(shù)呼叫符有最高的優(yōu)先順序，而 $ 的優(yōu)先順序則最低。用空格的函數(shù)呼叫符是左結(jié)合的，如 f a b c 與 ((f a) b) c 等價，而 $ 則是右結(jié)合的。

聽著不錯。但有什么用？它可以減少我們程式碼中括號的數(shù)目。試想有這個表達式： sum (map sqrt [1..130])。由于低優(yōu)先順序的 $，我們可以將其改為 sum $ map sqrt [1..130]，可以省敲不少鍵！sqrt 3 + 4 + 9 會怎樣？這會得到 9，4 和根3 的和。若要取 (3+4+9) 的平方根，就得 sqrt (3+4+9) 或用 $：sqrt $ 3+4+9。因為 $ 有最低的優(yōu)先順序，所以你可以把$看作是在右面寫一對括號的等價形式。

sum (filter (> 10) (map (*2) [2..10])) 該如何？嗯，$ 是右結(jié)合，f (g (z x)) 與 f $ g $ z x 等價。所以我么可以將 sum (filter (> 10) (map (*2) [2..10]) 重寫為 sum $ filter (> 10) $ map (*2) [2..10]。

除了減少括號外，$ 還可以將數(shù)據(jù)作為函數(shù)使用。例如映射一個函數(shù)呼叫符到一組函數(shù)組成的 List：

ghci> map ($ 3) [(4+),(10*),(^2),sqrt]  
[7.0,30.0,9.0,1.7320508075688772]  

Function composition

在數(shù)學中，函數(shù)組合是這樣定義的： http://wiki.jikexueyuan.com/project/haskell-guide/images/composition.png" alt="" />，表示組合兩個函數(shù)成為一個函數(shù)。以 x 呼叫這一函數(shù)，就與用 x 呼叫 g 再用所得的結(jié)果呼叫 f 等價。

Haskell 中的函數(shù)組合與之很像，即 . 函數(shù)。其定義為：

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

http://wiki.jikexueyuan.com/project/haskell-guide/images/notes.png" alt="" />

注意下這型別聲明，f 的參數(shù)型別必須與 g 的回傳型別相同。所以得到的組合函數(shù)的參數(shù)型別與 g 相同，回傳型別與 f 相同。表達式 negate . (*3) 回傳一個求一數(shù)字乘以 3 后的負數(shù)的函數(shù)。

函數(shù)組合的用處之一就是生成新函數(shù)，并傳遞給其它函數(shù)。當然我們可以用 lambda 實現(xiàn)，但大多數(shù)情況下，使用函數(shù)組合無疑更清楚。假設(shè)我們有一組由數(shù)字組成的 List，要將其全部轉(zhuǎn)為負數(shù)，很容易就想到應先取其絕對值，再取負數(shù)，像這樣：

ghci> map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]  
[-5,-3,-6,-7,-3,-2,-19,-24]  

注意下這個 lambda 與那函數(shù)組合是多么的相像。用函數(shù)組合，我們可以將程式碼改為：

ghci> map (negate . abs) [5,-3,-6,7,-3,2,-19,24]  
[-5,-3,-6,-7,-3,-2,-19,-24]  

漂亮！函數(shù)組合是右結(jié)合的，我們同時組合多個函數(shù)。表達式 f (g (z x))與 (f . g . z) x 等價。按照這個思路，我們可以將

ghci> map (\xs -> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]  
[-14,-15,-27]  

改為：

ghci> map (negate . sum . tail) [[1..5],[3..6],[1..7]]  
[-14,-15,-27]  

不過含多個參數(shù)的函數(shù)該怎么辦？好，我們可以使用不全呼叫使每個函數(shù)都只剩下一個參數(shù)。sum (replicate 5 (max 6.7 8.9)) 可以重寫為 (sum . replicate 5 . max 6.7) 8.9 或 sum . replicate 5 . max 6.7 $ 8.9。在這里會產(chǎn)生一個函數(shù)，它取與 max 6.7 同樣的參數(shù)，并使用結(jié)果呼叫 replicate 5 再用 sum 求和。最后用 8.9 呼叫該函數(shù)。不過一般你可以這么讀，用 8.9 呼叫 max 6.7，然后使它 replicate 5，再 sum 之。如果你打算用函數(shù)組合來替掉那堆括號，可以先在最靠近參數(shù)的函數(shù)后面加一個 $，接著就用 . 組合其所有函數(shù)呼叫，而不用管最后那個參數(shù)。如果有這樣一段程式碼：replicate 100 (product (map (*3) (zipWith max [1,2,3,4,5] [4,5,6,7,8])))，可以改為：replicate 100 . product . map (*3) . zipWith max [1,2,3,4,5] $ [4,5,6,7,8]。如果表達式以 3 個括號結(jié)尾，就表示你可以將其修改為函數(shù)組合的形式。

函數(shù)組合的另一用途就是定義 point free style (也稱作 pointless style) 的函數(shù)。就拿我們之前寫的函數(shù)作例子：

sum' :: (Num a) => [a] -> a     
sum' xs = foldl (+) 0 xs    

等號的兩端都有個 xs。由于有柯里化 (Currying)，我們可以省掉兩端的 xs。foldl (+) 0 回傳的就是一個取一 List 作參數(shù)的函數(shù)，我們把它修改為 sum' = foldl (+) 0，這就是 point free style。下面這個函數(shù)又該如何改成 point free style 呢？

fn x = ceiling (negate (tan (cos (max 50 x))))  

像剛才那樣簡單去掉兩端的 x 是不行的，函數(shù)定義中 x 的右邊還有括號。cos (max 50) 是有錯誤的，你不能求一個函數(shù)的余弦。我們的解決方法就是，使用函數(shù)組合。

fn = ceiling . negate . tan . cos . max 50  

漂亮！point free style 會令你去思考函數(shù)的組合方式，而非數(shù)據(jù)的傳遞方式，更加簡潔明了。你可以將一組簡單的函數(shù)組合在一起，使之形成一個復雜的函數(shù)。不過函數(shù)若過于復雜，再使用 point free style 往往會適得其反，因此構(gòu)造較長的函數(shù)組合鏈是不被鼓勵的(雖然我本人熱衷于函數(shù)組合)。更好的解決方法，就是使用 let 語句給中間的運算結(jié)果綁定一個名字，或者說把問題分解成幾個小問題再組合到一起。這樣一來我們程式碼的讀者就可以輕松些，不必要糾結(jié)那巨長的函數(shù)組合鏈了。

在 map 和 filter 那節(jié)中，我們求了小于 10000 的所有奇數(shù)的平方的和。如下就是將其置于一個函數(shù)中的樣子：

oddSquareSum :: Integer  
oddSquareSum = sum (takeWhile (<10000) (filter odd (map (^2) [1..])))    

身為函數(shù)組合狂人，我可能會這么寫：

oddSquareSum :: Integer  
oddSquareSum = sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]  

不過若是給別人看，我可能就這么寫了：

oddSquareSum :: Integer  
oddSquareSum =   
    let oddSquares = filter odd $ map (^2) [1..]  
        belowLimit = takeWhile (<10000) oddSquares  
    in  sum belowLimit  

這段程式碼可贏不了程式碼花樣大賽，不過我們的讀者可能會覺得它比函數(shù)組合鏈更好看。