第六章 Haskell高階函數(shù)

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

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

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

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

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

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

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

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

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

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]

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

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

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

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

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 :: (a -> b) -> [a] -> [b]   
map _ [] = []   
map f (x:xs) = f x : map f xs

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]

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

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"

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

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

要從小于 100000 的數(shù)中找出 3829 的最大的倍數(shù)，我們應(yīng)當(dāng)過濾一個(gè)結(jié)果可能所在的 List.

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

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

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

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

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

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

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

好的，我們想知道的是: 以 1 到 100 之間的所有數(shù)作為起始數(shù)，會(huì)有多少個(gè)鏈的長度大于 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，這便是邊界條件。標(biāo)準(zhǔn)的遞歸函數(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)在由這個(gè)函數(shù)來告訴我們結(jié)果:

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

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

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

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

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

取所得 List 的第五個(gè)元素可得一函數(shù)，與 (*4) 等價(jià)。 然后用 5 調(diào)用它，與 (* 4) 5 或 4*5 都是等價(jià)的.

lambda

lambda 就是匿名函數(shù)。有些時(shí)候我們需要傳給高階函數(shù)一個(gè)函數(shù)，而這函數(shù)我們只會(huì)用這一次，這就弄個(gè)特定功能的 lambda。編寫 lambda，就寫個(gè) \ (因?yàn)樗雌饋硐袷窍ＥD字母的 lambda -- 如果你斜視的厲害)，后面是用空格分隔的參數(shù)，-> 后面就是函數(shù)體。通常我們都是用括號將其括起，要不然它就會(huì)占據(jù)整個(gè)右邊部分。

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

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

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

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

和普通函數(shù)一樣，lambda 也可以取多個(gè)參數(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 中使用模式匹配，只是你無法為一個(gè)參數(shù)設(shè)置多個(gè)模式，如 [] 和 (x:xs)。lambda 的模式匹配若失敗，就會(huì)引發(fā)一個(gè)運(yùn)行時(shí)錯(cuò)誤，所以慎用！

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

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

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ù)體中都有 ->，這一來型別聲明的寫法就很明白了。當(dāng)然第一段代碼更易讀，不過第二個(gè)函數(shù)使得柯里化更容易理解。

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

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

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

關(guān)鍵字 fold

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

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

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

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

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

測試下，一二三～

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

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

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

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

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

呼呼，進(jìn)入右折疊前我們再實(shí)現(xiàn)個(gè)用到左折疊的函數(shù)。大家肯定都知道 elem 是檢查某元素是否屬于某 List 的函數(shù)吧，我就不再提了(唔，剛提了)。用左折疊實(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 時(shí)，累加值與最終結(jié)果的型別總是相同的。如果你不知道怎樣對待起始值，那我告訴你，我們先假設(shè)它不存在，以 False 開始。我們要是 fold 一個(gè)空 List，結(jié)果就是 False。然后我們檢查當(dāng)前元素是否為我們尋找的，如果是，就令累加值為 True，如果否，就保留原值不變。若 False，及表明當(dāng)前元素不是。若 True，就表明已經(jīng)找到了。

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

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

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

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

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

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

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

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

為了體會(huì) fold 的威力，我們就用它實(shí)現(xiàn)幾個(gè)庫函數(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)

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

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

scanl 和 scanr 與 foldl 和 foldr 相似，只是它們會(huì)記錄下累加值的所有狀態(tài)到一個(gè) 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]]

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

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

有$的函數(shù)調(diào)用

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

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

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

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

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

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

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

函數(shù)組合

在數(shù)學(xué)中，函數(shù)組合是這樣定義的：，表示組合兩個(gè)函數(shù)成為一個(gè)函數(shù)。以 x 調(diào)用這一函數(shù)，就與用 x 調(diào)用 g 再用所得的結(jié)果調(diào)用 f 等價(jià)。

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

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

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

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

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

注意下這個(gè) 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í)組合多個(gè)函數(shù)。表達(dá)式 f (g (z x))與 (f . g . z) x 等價(jià)。按照這個(gè)思路，我們可以將

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]

不過含多個(gè)參數(shù)的函數(shù)該怎么辦？好，我們可以使用不全調(diào)用使每個(gè)函數(shù)都只剩下一個(gè)參數(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。在這里會(huì)產(chǎn)生一個(gè)函數(shù)，它取與 max 6.7 同樣的參數(shù)，并使用結(jié)果調(diào)用 replicate 5 再用 sum 求和。最后用 8.9 調(diào)用該函數(shù)。不過一般你可以這么讀，用 8.9 調(diào)用 max 6.7，然后使它 replicate 5，再 sum 之。如果你打算用函數(shù)組合來替掉那堆括號，可以先在最靠近參數(shù)的函數(shù)后面加一個(gè) $，接著就用 . 組合其所有函數(shù)調(diào)用，而不用管最后那個(gè)參數(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]。如果表達(dá)式以 3 個(gè)括號結(jié)尾，就表示你可以將其修改為函數(shù)組合的形式。

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

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

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

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

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

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

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

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

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

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

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

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