[TOC]  haskell中的函數可以作為參數和返回值傳來傳去，這樣的函數就被稱作高階函數。高階函數可不只是某簡單特性而已，它貫穿于haskell的方方面面。要拒絕循環與狀態的改變而通過定義問題"是什么"來解決問題，高階函數必不可少。它們是編碼的得力工具。 ## 柯里函數 本質上，haskell的所有函數都只有一個參數，那么我們先前編那么多含有多個參數的函數又是怎么回事? 呵，小伎倆! 所有多個參數的函數都是柯里函數。 什么意思呢? 取一個例子最好理解，就拿我們的好朋友`max`函數說事吧。它看起來像是取兩個參數，返回較大的那個數。 實際上，執行`max 4 5`時，它會首先返回一個取一個參數的函數，其返回值不是4就是該參數，取決于誰大。 然后，以5為參數調用它，并取得最終結果。 這聽著挺繞口的，不過這一概念十分的酷! 如下的兩個調用是等價的： ~~~ ghci>?max?4?5? 5? ghci>?(max?4)?5? 5 ~~~  把空格放到兩個東西之間，稱作**函數調用**。它有點像個運算符，并擁有最高的優先級。 看看max函數的類型:`max :: (Ord a) => a -> a -> a`。 也可以寫作:`max :: (Ord a) => a -> (a -> a)`。 可以讀作max取一個參數a，并返回一個函數(就是那個`->`)，這個函數取一個a類型的參數，返回一個a。 這便是為何只用箭頭來分隔參數和返回值類型。 這樣的好處又是如何? 簡言之，我們若以不全的參數來調用某函數，就可以得到一個**不全調用**的函數。 如果你高興，構造新函數就可以如此便捷，將其傳給另一個函數也是同樣方便。 看下這個函數，簡單至極: ~~~ multThree?::?(Num?a)?=>?a?->?a?->?a?->?a? multThree?x?y?z?=?x?*?y?*?z ~~~ 我們若執行`mulThree 3 5 9`或`((mulThree 3) 5) 9`，它背后是如何運作呢？ 首先，按照空格分隔，把`3`交給`mulThree`。 這返回一個返回函數的函數。 然后把`5`交給它，返回一個取一個參數并使之乘以`15`的函數。 最后把`9`交給這一函數，返回`135`。 想想，這個函數的類型也可以寫作`multThree :: (Num a) => a -> (a -> (a -> a))`，`->`前面的東西就是函數取的參數，后面的東西就是其返回值。 所以說，我們的函數取一個`a`，并返回一個類型為`(Num a) => a -> (a -> a)`的函數，類似，這一函數返回一個取一個`a`，返回一個類型為`(Num a) => a -> a`的函數。 而最后的這個函數就只取一個`a`并返回一個`a`，如下: ~~~ ghci>?let?multTwoWithNine?=?multThree?9? ghci>?multTwoWithNine?2?3? 54? ghci>?let?multWithEighteen?=?multTwoWithNine?2? ghci>?multWithEighteen?10? 180 ~~~ 前面提到，以不全的參數調用函數可以方便地創造新的函數。例如，搞個取一數與100比較大小的函數該如何? 大可這樣: ~~~ compareWithHundred?::?(Num?a，Ord?a)?=>?a?->?Ordering? compareWithHundred?x?=?compare?100?x ~~~ 用99調用它，就可以得到一個`GT`。 簡單。 注意下在等號兩邊都有x。 想想`compare 100`會返回什么？一個取一數與100比較的函數。 Wow，這不正是我們想要的? 這樣重寫: ~~~ compareWithHundred?::?(Num?a，Ord?a)?=>?a?->?Ordering? compareWithHundred?=?compare?100 ~~~ 類型聲明依然相同，因為`compare 100`返回函數。 compare的類型為`(Ord a) => a -> (a -> Ordering)`，用100調用它后返回的函數類型為`(Num a，Ord a) => a -> Ordering`，同時由于100還是`Num`類型類的實例，所以還得另留一個類約束。 Yo! 你得保證已經弄明白了柯里函數與不全調用的原理，它們很重要！ 中綴函數也可以不全調用，用括號把它和一邊的參數括在一起就行了。 這返回一個取一參數并將其補到缺少的那一端的函數。 一個簡單函數如下: ~~~ divideByTen?::?(Floating?a)?=>?a?->?a? divideByTen?=?(/10) ~~~ 調用`divideByTen 200`就是`(/10) 200`，和`200 / 10`等價。 一個檢查字符是否為大寫的函數: ~~~ isUpperAlphanum?::?Char?->?Bool? isUpperAlphanum?=?(`elem`?['A'..'Z']) ~~~ 唯一的例外就是`-`運算符，按照前面提到的定義，`(-4)`理應返回一個并將參數減4的函數，而實際上，處于計算上的方便，`(-4)`表示負`4`。 若你一定要弄個將參數減4的函數，就用`subtract`好了，像這樣`(subtract 4)`. 若不用_let_給它命名或傳到另一函數中，在ghci中直接執行`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`類型的函數，但它不知道該如何顯示它。 函數不是`Show`類型類的實例，所以我們不能得到表示一函數內容的字符串。 若在ghci中計算`1+1`，它會首先計算得`2`，然后調用`show 2`得到該數值的字符串表示，即"2"，再輸出到屏幕. ## 是時候了，來點高階函數！ haskell中的函數可以取另一個函數做參數，也可以返回函數。 舉個例子，我們弄個取一個函數并調用它兩次的函數. ~~~ applyTwice?::?(a?->?a)?->?a?->?a??? applyTwice?f?x?=?f?(f?x) ~~~  首先注意這類型聲明。 在此之前我們很少用到括號，因為`(->)`是自然的右結合，不過在這里括號是必須的。 它標明了首個參數是個參數與返回值類型都是a的函數，第二個參數與返回值的類型也都是a。 我們可以用柯里函數的思路來理解這一函數，不過免得自尋煩惱，我們姑且直接把它看作是取兩個參數返回一個值，其首個參數是個類型為`(a->a)`的函數,第二個參數是個`a`。 該函數的類型可以是`(Int->Int)`，也可以是`(String->String)`，但第二個參數必須與之一致。 > **Note**: 現在開始我們會直說某函數含有多個參數(除非它真的只有一個參數)。 以簡潔之名，我們會說(a->a->a)取兩個參數，盡管我們知道它在背后做的手腳. 這個函數是相當的簡單，就拿參數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`。 它取一個函數和兩個List做參數，并把兩個List交到一起(使相應的元素去調用該函數)。 如下就是我們的實現: ~~~ zipWith'?::?(a?->?b?->?c)?->?[a]?->?[b]?->?[c]??? zipWith'?_?[]?_?=?[]??? zipWith'?_?_?[]?=?[]??? zipWith'?f?(x:xs)?(y:ys)?=?f?x?y?:?zipWith'?f?xs?ys ~~~ 看下這個類型聲明，它的首個參數是個函數，取兩個參數處理交叉，其類型不必相同，不過相同也沒關系。 第二三個參數都是List，返回值也是個List。 第一個List中元素的類型必須是a，因為這個處理交叉的函數的第一個參數是a。 第二個List中元素的類型必為b，因為這個處理交叉的函數第二個參數的類型是b。 返回的List中元素類型為c。 如果一個函數說取一個類型為`a->b->c`的函數做參數，傳給它個`a->a->c`類型的也是可以的，但反過來就不行了。 可以記下，若在使用高階函數的時候不清楚其類型為何，就先忽略掉它的類型聲明，再到ghci下用`:t`命令來看下haskell的類型推導. 這函數的行為與普通的`zip`很相似，邊界條件也是相同，只不過多了個參數，即處理元素交叉的函數。它關不著邊界條件什么事兒，所以我們就只留一個_ 。后一個模式的函數體與zip也很像，只不過這里是`f x y`而非`(x,y)`。 只要足夠通用，一個簡單的高階函數可以在不同的場合反復使用。 如下便是我們`zipWith'`函數本領的冰山一角: ~~~ 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]] ~~~ 如你所見，一個簡單的高階函數就可以玩出很多花樣。 命令式語言使用for、while、賦值、狀態檢測來實現功能，再包起來留個接口，使之像個函數一樣調用。而函數式語言使用高階函數來抽象出常見的模式，像成對遍歷并處理兩個List或從中篩掉自己不需要的結果。 接下來實現標準庫中的另一個函數flip，flip簡單地取一個函數作參數并返回一個相似的函數，只是它們的兩個參數倒了個。 ~~~ flip'?::?(a?->?b?->?c)?->?(b?->?a?->?c)??? flip'?f?=?g??? ????where?g?x?y?=?f?y?x ~~~ 從這類型聲明中可以看出，它取一個函數，其參數類型分別為a和b，而它返回的函數的參數類型為b和a。 由于函數默認都是柯里化的，`->`為右結合，這里的第二對括號其實并無必要，`(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 ~~~ 在這里我們就利用了柯里函數的優勢，只要調用`flip' f`而不帶`y`和`x`，它就會返回一個倆參數倒個的函數。`flip`處理的函數往往都是用來傳給其他函數調用，于是我們可以發揮柯里函數的優勢，預先想好發生完全調用的情景并處理好返回值. ~~~ 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取一個函數和List做參數，遍歷該List的每個元素來調用該函數產生一個新的List。 看下它的類型聲明和實現: ~~~ map?::?(a?->?b)?->?[a]?->?[b]??? map?_?[]?=?[]??? map?f?(x:xs)?=?f?x?:?map?f?xs ~~~ 從這類型聲明中可以看出，它取一個取`a`返回`b`的函數和一組a的List，并返回一組b。 這就是haskell的有趣之處：有時只看類型聲明就能對函數的行為猜個大致。`map`函數多才多藝，有一百萬種用法。 如下是其中一小部分: ~~~ 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] ~~~ 你可能會發現，以上的所有代碼都可以用List Comprehension來替代。`map (+3) [1,5,3,1,6]`與`[x+3 | x <- [1,5,3,1,6]`完全等價。 filter函數取一個限制條件和一個List，返回該List中所有符合該條件的元素。 它的類型聲明及實現大致如下: ~~~ filter?::?(a?->?Bool)?->?[a]?->?[a]??? filter?_?[]?=?[]??? filter?p?(x:xs)???? ????|?p?x???????=?x?:?filter?p?xs??? ????|?otherwise?=?filter?p?xs ~~~ 很簡單。 只要`p x`所得的結果為真，就將這一元素加入新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的限制條件來實現。 并沒有教條規定你必須在什么情況下用`map`和`filter`還是_List Comprehension_，選擇權歸你，看誰舒服用誰就是。 如果有多個限制條件，只能連著套好幾個filter或用&&等邏輯函數的組合之，這時就不如list comprehension來得爽了。 還記得上一章的那個quicksort函數么? 我們用到了List Comprehension來過濾大于或小于錨的元素。 換做filter也可以實現，而且更加易讀： ~~~ 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是每個函數式程序員的面包黃油（呃，map和filter還是List Comprehension并不重要）。 想想前面我們如何解決給定周長尋找合適直角三角形的問題的? 在命令式編程中，我們可以套上三個循環逐個測試當前的組合是否滿足條件，若滿足，就打印到屏幕或其他類似的輸出。 而在函數式編程中，這行就都交給map和filter。 你弄個取一參數的函數，把它交給map過一遍List，再filter之找到合適的結果。 感謝haskell的惰性，即便是你多次map一個list也只會遍歷一遍該list，要找出小于100000的數中最大的3829的倍數，只需過濾結果所在的list就行了. 要找出**小于100000的3829的所有倍數**，我們應當過濾一個已知結果所在的list. ~~~ largestDivisible?::?(Integral?a)?=>?a??? largestDivisible?=?head?(filter?p?[100000,99999..])??? ????where?p?x?=?x?`mod`?3829?==?0 ~~~ 首先， 取一個降序的小于100000所有數的List，然后按照限制條件過濾它。 由于這個List是降序的，所以結果List中的首個元素就是最大的那個數。 惰性再次行動! 由于我們只取這結果List的首個元素，所以它并不關心這List是有限還是無限的，在找到首個合適的結果處運算就停止了。 接下來，我們就要**找出所有小于10000的奇數的平方和**，得先提下takeWhile函數，它取一個限制條件和List作參數，然后從頭開始遍歷這一List，并返回符合限制條件的元素。 而一旦遇到不符合條件的元素，它就停止了。 如果我們要取出字符串`"elephants know how to party"`中的首個單詞，可以`takeWhile (/=' ') "elephants know how to party"`，返回`"elephants"`。 okay，要求所有小于10000的奇數的平方的和，首先就用`(^2)`函數map掉這個無限的List`[1..]`。然后過濾之，只取奇數就是了。 在大于10000處將它斷開，最后前面的所有元素加到一起。 這一切連寫函數都不用，在ghci下直接搞定. ~~~ ghci>?sum?(takeWhile?(10000)?(filter?odd?(map?(^2)?[1..])))??? 166650 ~~~ 不錯! 先從幾個初始數據(表示所有自然數的無限list)，再map它，filter它，切它，直到它符合我們的要求，再將其加起來。 這用list comprehension也是可以的，而哪種方式就全看你的個人口味. ~~~ ghci>?sum?(takeWhile?(10000)?[m?|?m??[n^2?|?n??[1..]],?odd?m])??? 166650 ~~~ 感謝haskell的惰性特質，這一切才得以實現。 我們之所以可以map或filter一個無限list，是因為它的操作不會被立即執行，而是拖延一下。 只有我們要求haskell交給我們sum的結果的時候，sum函數才會跟takeWhile說，它要這些數。`takeWhile`就再去要求filter和map行動起來，并在遇到大于等于10000時候停止. 下個問題與Collatz序列有關，取一個自然數，若為偶數就除以2。 若為奇數就乘以3再加1。 再用相同的方式處理所得的結果，得到一組數字構成的的鏈。 它有個性質，無論任何以任何數字開始，最終的結果都會歸1。 所以若拿13當作起始數，就可以得到這樣一個序列_13，40，20，10，5，16，8，4，2，1_。13*3+1得40，40除2得20，如是繼續，得到一個10個元素的鏈。 好的，我們想知道的是: 以1到100之間的所有數作為起始數，會有多少個鏈的長度大于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，這便是邊界條件。 標準的遞歸函數: ~~~ 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! 貌似工作良好。 現在由這個函數來告訴我們結果: ~~~ numLongChains?::?Int??? numLongChains?=?length?(filter?isLong?(map?chain?[1..100]))??? ????where?isLong?xs?=?length?xs?>?15 ~~~ 我們把chain函數map到`[1..100]`，得到一組鏈的list，然后用個限制條件過濾長度大于15的鏈。 過濾完畢后就可以得出結果list中的元素個數. > **Note**: 這函數的類型為`numLongChains :: Int`。 這是由于歷史原因，`length`返回一個`Int`而非`Num`的成員類型，若要得到一個更通用的`Num a`，我們可以使用`fromInterval`函數來處理所得結果. 用map，我們可以寫出類似`map (*) [0..]`之類的代碼。 如果只是為了例證柯里函數和不全調用的函數是真正的值及其原理，那就是你可以把函數傳遞或把函數裝在list中(只是你還不能將它們轉換為字符串)。 迄今為止，我們還只是map單參數的函數到list，如`map (*2) [0..]`可得一組類型為`(Num a) => [a]`的list，而`map (*) [0..]`也是完全沒問題的。`*`的類型為`(Num a) -> a -> a -> a`，用單個參數調用二元函數會返回一個一元函數。 如果用`*`來map 一個`[0..]`的list，就會得到一組一元函數組成的list，即`(Num a) => [a->a]`。`map (*) [0..]`所得的結果寫起來大約就是`[(*0),(*1),(*2)..]` ~~~ ghci>?let?listOfFuns?=?map?(*)?[0..]??? ghci>?(listOfFuns?!!?4)?5??? 20 ~~~ 取所得list的第四個元素可得一函數，與`(*4)`等價。 然后用`5`調用它，與`(* 4) 5`或`4*5`都是等價的. ## lambda  lambda就是匿名函數。有些時候我們需要傳給高階函數一個函數，而這函數我們只會用這一次，這就弄個特定功能的lambda。編寫lambda，就寫個`\`（因為它看起來像是希臘字母的lambda--如果你斜視的厲害），后面是用空格分隔的參數，`->`后面就是函數體。通常我們都是用括號將其括起，要不然它就會占據整個右邊部分。 向上5英寸左右，你會看到我們在`numLongChain`函數中用where語句聲明了個`isLong`函數傳遞給了filter。好的，用lambda代替它。 ~~~ numLongChains?::?Int??? numLongChains?=?length?(filter?(\xs?->?length?xs?>?15)?(map?chain?[1..100])) ~~~  lambda是個表達式，因此我們可以任意傳遞。表達式`(\xs -> length xs > 15)`返回一個函數，它可以告訴我們一個list的長度是否大于15。 不熟悉柯里函數與不全調用的人們往往會寫出很多lambda，而實際上大部分都是沒必要的。例如，表達式`map (+3) [1,6,3,2]`與`map (\x -> x+3) [1,6,3,2]`等價，`(+3)`和`(\x -> x+3)`都是給一個數加上3。不用說，在這種情況下不用lambda要清爽的多。 和普通函數一樣，lambda也可以取多個參數。 ~~~ 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] ~~~ 同普通函數一樣，你也可以在lambda中使用模式匹配，只是你無法為一個參數設置多個模式，如`[]`和`(x:xs)`。lambda的模式匹配若失敗，就會引發一個運行時錯誤，所以慎用！ ~~~ ghci>?map?(\(a,b)?->?a?+?b)?[(1,2),(3,5),(6,3),(2,6),(2,5)]??? [3,8,9,8,7] ~~~ 一般情況下，lambda都是括在括號中，除非我們想要后面的整個語句都作為lambda的函數體。很有趣，由于有柯里化，如下的兩段是等價的： ~~~ 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 ~~~ 這樣的函數聲明與函數體中都有`->`，這一來類型聲明的寫法就很明白了。當然第一段代碼更易讀，不過第二個函數使得柯里化更容易理解。 有些時候用這種語句寫還是挺酷的，我覺得這應該是最易讀的flip函數實現了： ~~~ flip'?::?(a?->?b?->?c)?->?b?->?a?->?c??? flip'?f?=?\x?y?->?f?y?x ~~~ 盡管這與`flip' f x y = f y x`等價，但它可以更明白地表示出它會產生一個新的函數。flip常用來處理一個函數，再將返回的新函數傳遞給map或filter。所以如此使用lambda可以更明確地表現出返回值是個函數，可以用來傳遞給其他函數作參數。 ## 折疊紙鶴  回到當初我們學習遞歸的情景。我們會發現處理list的許多函數都有固定的模式，通常我們會將邊界條件設置為空list，再引入(x:xs)模式，對單個元素和余下的list做些事情。這一模式是如此常見，因此haskell引入了一組函數來使之簡化，也就是fold。它們與map有點像，只是它們返回的是單個值。 一個fold取一個二元函數，一個初始值（我喜歡管它叫累加值）和一個需要fold（折疊）的list。這個二元函數有兩個參數，即累加值和list的首項（或尾項），返回值是新的累加值。然后，以新的累加值和新的list首項調用該函數，如是繼續。到list遍歷完畢時，只剩下一個累加值，也就是最終的結果。 首先看下foldl函數，也叫做左折疊。它從list的左端開始折疊，用初始值和list的頭部調用這二元函數，得一新的累加值，并用新的累加值與list的下一個元素調用二元函數。如是繼續。 我們再實現下sum，這次用fold替代那復雜的遞歸： ~~~ sum'?::?(Num?a)?=>?[a]?->?a??? sum'?xs?=?foldl?(\acc?x?->?acc?+?x)?0?xs ~~~ 測試下，一二三～ ~~~ ghci>?sum'?[3,5,2,1]??? 11 ~~~  我們深入看下fold的執行過程：`\acc x-> acc + x`是個二元函數，`0`是初始值，`xs`是待折疊的list。一開始，累加值為`0`，當前項為`3`，調用二元函數`0+3`得`3`，作新的累加值。接著來，累加值為`3`，當前項為`5`，得新累加值`8`。再往后，累加值為`8`，當前項為`2`，得新累加值`10`。最后累加值為`10`，當前項為`1`，得`11`。恭喜，你完成了一次折疊(fold)！ 左邊的這個圖表示了折疊的執行過程，一步又一步（一天又一天!）。淺棕色的數字都是累加值，你可以從中看出list是如何從左端一點點加到累加值上的。唔對對對！如果我們考慮到函數的柯里化，可以寫出更簡單的實現： ~~~ sum'?::?(Num?a)?=>?[a]?->?a??? sum'?=?foldl?(+)?0 ~~~ 這個lambda函數`(\acc x -> acc + x )`與(+)等價。我們可以把xs等一應參數省略掉，反正調用`foldl (+) 0`會返回一個取list作參數的函數。通常，如果你的函數類似`foo a = bar b a`， 大可改為`foo = bar b`。有柯里化嘛。 呼呼，進入右折疊前我們再實現個用到左折疊的函數。大家肯定都知道elem是檢查某元素是否屬于某list的函數吧，我就不再提了（唔，剛提了）。用左折疊實現它: ~~~ elem'?::?(Eq?a)?=>?a?->?[a]?->?Bool??? elem'?y?ys?=?foldl?(\acc?x?->?if?x?==?y?then?True?else?acc)?False?ys ~~~ 好好好，這里我們有什么？起始值與累加值都是布爾值。在處理fold時，累加值與最終結果的類型總是相同的。如果你不知道怎樣對待起始值，那我告訴你，我們先假設它不存在，以False開始。我們要是fold一個空list，結果就是False。然后我們檢查當前元素是否為我們尋找的，如果是，就令累加值為True，如果否，就保留原值不變。若False，及表明當前元素不是。若True，就表明已經找到了。 右折疊foldr的行為與左折疊相似，只是累加值是從list的右邊開始。同樣，左折疊的二元函數取累加值作首個參數，當前值為第二個參數（即`\acc x -> ...`），而右折疊的二元函數參數的順序正好相反（即`\x acc -> ...`）。這倒也正常，畢竟是從右端開始折疊。 累加值可以是任何類型，可以是數值，布爾值，甚至一個新的list。我們可以用右fold實現map函數，累加值就是個list。將map處理過的元素一個一個連到一起。很容易想到，起始值就是空list。 ~~~ map'?::?(a?->?b)?->?[a]?->?[b]??? map'?f?xs?=?foldr?(\x?acc?->?f?x?:?acc)?[]?xs ~~~ 如果我們用`(+3)`來映射`[1,2,3]`，它就會先到達list的右端，我們取最后那個元素，也就是`3`來調用`(+3)`，得`6`。追加`(:)`到累加值上，`6:[]`得`[6]`并成為新的累加值。用`2`調用`(+3)`，得`5`，追加到累加值，于是累加值成了`[5,6]`。再對`1`調用`(+3)`，并將結果4追加到累加值，最終得結果`[4,5,6]`。 當然，我們也完全可以用左折疊來實現它，`map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs`就行了。不過問題是，使用`(++)`往list后面追加元素的效率要比使用`(:)`低得多。所以在生成新list的時候人們一般都是使用右折疊。  反轉一個list，既也可以通過右折疊，也可以通過左折疊。有時甚至不需要管它們的分別，如sum函數的左右折疊實現都是十分相似。不過有個大的不同，那就是右折疊可以處理無限長度的數據結構，而左折疊不可以。將無限list從中斷開執行左折疊是可以的，不過若是向右，就永遠到不了頭了。 **所有遍歷list中元素并據此返回一個值的操作都可以交給fold實現**。無論何時需要遍歷list并返回某值，都可以嘗試下fold。因此，fold的地位可以說與map和filter并駕齊驅，同為函數式編程中最常用的函數之一。 foldl1與foldr1的行為與`foldl`和`foldr`相似，只是你無需明確提供初始值。他們假定list的首個（或末尾）元素作為起始值，并從旁邊的元素開始折疊。這一來，`sum`函數大可這樣實現：`sum = foldl1 (+)`。這里待折疊的list中至少要有一個元素，若使用空list就會產生一個運行時錯誤。不過foldl和foldr與空list相處的就很好。所以在使用fold前，應該先想下它會不會遇到空list，如果不會遇到，大可放心使用`foldr1`和`foldl1`。 為了體會fold的威力，我們就用它實現幾個庫函數： ~~~ 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) ~~~ 僅靠模式匹配就可以實現head函數和last函數，而且效率也很高。這里只是為了演示，用fold的實現方法。我覺得我們這個reverse'定義的相當聰明，用一個空list做初始值，并向左展開list，從左追加到累加值，最后得到一個反轉的新list。`\acc x -> x : acc`有點像`:`函數，只是參數順序相反。所以我們可以改成`foldl (flip (:)) []`。 有個理解折疊的思路：假設我們有個二元函數f，起始值z，如果從右折疊`[3,4,5,6]`，實際上執行的就是`f 3 (f 4 (f 5 (f 6 z)))`。f會被list的尾項和累加值調用，所得的結果會作為新的累加值傳入下一個調用。假設f是`(+)`，起始值z是`0`，那么就是`3 + (4 + (5 + (6 + 0)))`，或等價的前綴形式：`(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))`。相似，左折疊一個list，以g為二元函數，z為累加值，它就與`g (g (g (g z 3) 4) 5) 6`等價。如果用`flip (:)`作二元函數，`[]`為累加值（看得出，我們是要反轉一個list），這就與`flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6`等價。顯而易見，執行該表達式的結果為`[6,5,4,3]`。 scanl和scanr與`foldl`和`foldr`相似，只是它們會記錄下累加值的所有狀態到一個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時，最終結果就是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函數的執行過程。想想這個問題，**取所有自然數的平方根的和，尋找在何處超過1000**？先`map sqrt [1..]`，然后用個fold來求它們的和。但在這里我們想知道求和的過程，所以使用`scan`，`scan`完畢時就可以得到小于1000的所有和。所得結果list的第一個元素為1，第二個就是1+根2，第三個就是1+根2+根3。若有x個和小于1000，那結果就是x+1。 ## 有$的函數調用 好的，接下來看看$函數。它也叫作**函數調用符**。先看下它的定義： ~~~ ($)?::?(a?->?b)?->?a?->?b??? f?$?x?=?f?x ~~~  什么鬼東西？這沒啥意義的操作符？它只是個函數調用符罷了？好吧，不全是，但差不多。普通的函數調用符有最高的優先級，而`$`的優先級則最低。用空格的函數調用符是左結合的，如f a b c與((f a) b) c等價，而$則是右結合的。 聽著不錯。但有什么用？它可以減少我們代碼中括號的數目。試想有這個表達式：`sum (map sqrt [1..130])`。由于低優先級的$，我們可以將其改為`sum $ map sqrt [1..130]`，可以省敲不少鍵！`sqrt 3 + 4 + 9`會怎樣？這會得到9，4和根3的和。若要取`(3+4+9)`的平方根，就得`sqrt (3+4+9)`或用`$`：`sqrt $ 3+4+9`。因為`$`有最低的優先級，所以你可以把$看作是在右面寫一對括號的等價形式。 `sum (filter (> 10) (map (*2) [2..10]))`該如何？嗯，$是右結合，`f (g (z x))`與`f $ g $ z x`等價。所以我么可以將`sum (filter (> 10) (map (*2) [2..10])`重寫為`sum $ filter (> 10) $ map (*2) [2..10]`。 除了減少括號外，$還可以將數據作為函數使用。例如映射一個函數調用符到一組函數組成的list： ~~~ ghci>?map?($?3)?[(4+),(10*),(^2),sqrt]??? [7.0,30.0,9.0,1.7320508075688772] ~~~ ## 函數組合 在數學中，函數組合是這樣定義的：，表示組合兩個函數成為一個函數。以x調用這一函數，就與用x調用g再用所得的結果調用f等價。 haskell中的函數組合與之很像，即.函數。其定義為： ~~~ (.)?::?(b?->?c)?->?(a?->?b)?->?a?->?c??? f?.?g?=?\x?->?f?(g?x) ~~~  注意下這類型聲明，`f`的參數類型必須與`g`的返回類型相同。所以得到的組合函數的參數類型與`g`相同，返回類型與`f`相同。表達式`negate . (*3)`返回一個求一數字乘以3后的負數的函數。 函數組合的用處之一就是生成新函數，并傳遞給其它函數。當然我們可以用lambda實現，但大多數情況下，使用函數組合無疑更直白。假設我們有一組由數字組成的list，要將其全部轉為負數，很容易就想到應先取其絕對值，再取負數，像這樣： ~~~ ghci>?map?(\x?->?negate?(abs?x))?[5,-3,-6,7,-3,2,-19,24]??? [-5,-3,-6,-7,-3,-2,-19,-24] ~~~ 注意下這個lambda與那函數組合是多么的相像。用函數組合，我們可以將代碼改為： ~~~ ghci>?map?(negate?.?abs)?[5,-3,-6,7,-3,2,-19,24]??? [-5,-3,-6,-7,-3,-2,-19,-24] ~~~ 漂亮！函數組合是右結合的，我們同時組合多個函數。表達式`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] ~~~ 不過含多個參數的函數該怎么辦？好，我們可以使用不全調用使每個函數都只剩下一個參數。`sum (replicate 5 (max 6.7 8.9))`可以重寫為`(sum . replicate 5 . max 6.7) 8.9`或`sum . replicate 5 . max 6.7 $ 8.9`。在這里會產生一個函數，它取與`max 6.7`同樣的參數，并使用結果調用`replicate 5`再用`sum`求和。最后用`8.9`調用該函數。不過一般你可以這么讀，用8.9調用`max 6.7`，然后使它`replicate 5`，再sum之。如果你打算用函數組合來替掉那堆括號，可以先在最靠近參數的函數后面加一個`$`，接著就用`.`組合其所有函數調用，而不用管最后那個參數。如果有這樣一段代碼：`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個括號結尾，就表示你可以將其修改為函數組合的形式。 函數組合的另一用途就是定義point free style（也稱作pointless style）的函數。就拿我們之前寫的函數作例子： ~~~ sum'?::?(Num?a)?=>?[a]?->?a?????? sum'?xs?=?foldl?(+)?0?xs ~~~ 等號的兩端都有個xs。由于有柯里化（Currying），我們可以省掉兩端的xs。`foldl (+) 0`返回的就是一個取一list作參數的函數，我們把它修改為`sum' = foldl (+) 0`，這就是point free style。下面這個函數又該如何改成point free style呢？ ~~~ fn?x?=?ceiling?(negate?(tan?(cos?(max?50?x)))) ~~~ 像剛才那樣簡單去掉兩端的x是不行的，函數體中x的右邊還有括號。cos (max 50)是有錯誤的，你不能求一個函數的余弦。我們的解決方法就是，使用函數組合。 ~~~ fn?=?ceiling?.?negate?.?tan?.?cos?.?max?50 ~~~ 漂亮！point free style會令你去思考函數的組合方式，而非數據的傳遞方式，更加簡潔直白。你可以將一組簡單的函數組合在一起，使之形成一個復雜的函數。不過函數若過于復雜，再使用point free style往往會適得其反，因此構造較長的函數組合鏈是不被鼓勵的（雖然我本人熱衷于函數組合）。更好的解決方法，就是使用let語句給中間的運算結果綁定一個名字，或者說把問題分解成幾個小問題再組合到一起。這樣一來我們代碼的讀者就可以輕松些，不必要糾結那巨長的函數組合鏈了。 在map和filter那節中，我們求了小于10000的所有奇數的平方的和。如下就是將其置于一個函數中的樣子： ~~~ oddSquareSum?::?Integer??? oddSquareSum?=?sum?(takeWhile?(10000)?(filter?odd?(map?(^2)?[1..]))) ~~~ 身為函數組合狂人，我可能會這么寫： ~~~ 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 ~~~ 這段代碼可贏不了代碼花樣大賽，不過我們的讀者可能會覺得它比函數組合鏈更好看。