第五章 Haskell遞歸

你好，遞歸！

前面的章節(jié)中我們簡要談了一下遞歸。而在本章，我們會深入地了解到它為何在haskell中是如此重要，能夠以遞歸思想寫出簡潔優(yōu)雅的代碼。

如果你還不明白什么是遞歸，就讀這個句子。哈哈！玩笑而已！遞歸實(shí)際上是定義函數(shù)以調(diào)用自身的方式。在數(shù)學(xué)定義中，遞歸隨處可見，如斐波那契數(shù)列（fibonacci）。它先是定義兩個非遞歸的數(shù)：F(0)=0,F(1)=1，表示斐波那契數(shù)列的前兩個數(shù)為0和 1。然后就是對其他自然數(shù)，其斐波那契數(shù)就是它前面兩個數(shù)字的和，即F(N)=F(N-1)+F(N-2)。這樣一來，_F(3)_就是F(2)+F(1)，進(jìn)一步便是(F(1)+F(0))+F(1)。已經(jīng)下探到了前面定義的非遞歸斐波那契數(shù)，可以放心地說_F(3)_就是2了。在遞歸定義中聲明的一兩個非遞歸的值（如_F(0)_和F(1)）也可以稱作邊界條件，這對遞歸函數(shù)的正確求值至關(guān)重要。要是前面沒有定義_F(0)_和_F(1)_的話，它下探到0之后就會進(jìn)一步到負(fù)數(shù)，你就永遠(yuǎn)都得不到結(jié)果了。一不留神它就算到了F(-2000)=F(-2001)+F(-2002)，并且永遠(yuǎn)都算不到頭！

遞歸在haskell中至關(guān)重要。命令式語言要求你提供求解的步驟，haskell則傾向于讓你提供問題的描述。這便是haskell沒有while或for循環(huán)的原因，遞歸是我們的替代方案。

實(shí)作 Maximum

maximum函數(shù)取一組可排序的List（屬于 Ord類型類）做參數(shù)，并返回其中的最大值。想想，在命令式風(fēng)格中這一函數(shù)該怎么實(shí)現(xiàn)。很可能你會設(shè)一個變量來存儲當(dāng)前的最大值，然后用循環(huán)遍歷該 List，若存在比這個值更大的元素，則修改變量為這一元素的值。到最后，變量的值就是運(yùn)算結(jié)果。唔！描述如此簡單的算法還頗費(fèi)了點(diǎn)口舌呢！

現(xiàn)在看看遞歸的思路是如何：我們先定下一個邊緣條件，即處理單個元素的List時(shí)，返回該元素。如果該List的頭部大于尾部的最大值，我們就可以假定較長 的List的最大值就是它的頭部。而尾部若存在比它更大的元素，它就是尾部的最大值。就這么簡單！現(xiàn)在，我們在haskell中實(shí)現(xiàn)它

maximum' :: (Ord a) => [a] -> a   
maximum' [] = error "maximum of empty list"   
maximum' [x] = x   
maximum' (x:xs)    
    | x > maxTail = x   
    | otherwise = maxTail   
    where maxTail = maximum' xs

如你所見，模式匹配與遞歸簡直就是天造地設(shè)！大多數(shù)命令式語言中都沒有模式匹配，于是你就得造一堆if-else來測試邊界條件。而在這里，我們僅需要使用 模式將其表示出來。第一個模式說，如果該List為空，崩潰！就該這樣，一個空List的最大值能是啥？我不知道。第二個模式也表示一個邊緣條件，它說， 如果這個List僅包含單個元素，就返回該元素的值。

現(xiàn)在是第三個模式，執(zhí)行動作的地方。 通過模式匹配，可以取得一個List的頭部和尾部。這在使用遞歸處理List時(shí)是十分常見的。出于習(xí)慣，我們用個where語句來表示maxTail作為該List中尾部的最大值，然后檢查頭部是否大于尾部的最大值。若是，返回頭部；若非，返回尾部的最大值。

我們?nèi)€List[2,5,1]做例子來看看它的工作原理。當(dāng)調(diào)用maximum'處理它時(shí)，前兩個模式不會被匹配，而第三個模式匹配了它并將其分為2與[5,1]。 where子句再取[5,1]的最大值。于是再次與第三個模式匹配，并將[5,1]分割為5和[1]。繼續(xù)，where子句取[1]的最大值，這時(shí)終于到了邊緣條件！返回1。進(jìn)一步，將5與[1]中的最大值做比較，易得5，現(xiàn)在我們就得到了[5,1]的最大值。再進(jìn)一步，將2與[5,1]中的最大值相比較，可得5更大，最終得5。

改用max函數(shù)會使代碼更加清晰。如果你還記得，max函數(shù)取兩個值做參數(shù)并返回其中較大的值。如下便是用max函數(shù)重寫的maximun'

maximum' :: (Ord a) => [a] -> a   
maximum' [] = error "maximum of empty list"   
maximum' [x] = x   
maximum' (x:xs) = max x (maximum' xs)

太漂亮了！一個List的最大值就是它的首個元素與它尾部中最大值相比較所得的結(jié)果，簡明扼要。

幾個遞歸函數(shù)

現(xiàn)在我們已經(jīng)了解了遞歸的思路,接下來就使用遞歸來實(shí)現(xiàn)幾個函數(shù). 先實(shí)現(xiàn)下replicate函數(shù), 它取一個Int值和一個元素做參數(shù), 返回一個包含多個重復(fù)元素的List, 如replicate 3 5返回[5,5,5]. 考慮一下, 我覺得它的邊界條件應(yīng)該是負(fù)數(shù). 如果要replicate重復(fù)某元素零次, 那就是空List. 負(fù)數(shù)也是同樣, 不靠譜.

replicate' :: (Num i, Ord i) => i -> a -> [a]   
replicate' n x   
    | n <= 0    = []   
    | otherwise = x:replicate' (n-1) x

在這里我們使用了門衛(wèi)而非模式匹配, 是因?yàn)檫@里做的是布爾判斷. 如果n小于0就返回一個空List, 否則, 返回以x作首個元素并后接重復(fù)n-1次x的List. 最后, (n-1)的那部分就會令函數(shù)抵達(dá)邊緣條件.

Note: Num不是Ord的子集, 表示數(shù)字不一定得拘泥于排序, 這就是在做加減法比較時(shí)要將Num與Ord類型約束區(qū)別開來的原因.

接下來實(shí)現(xiàn)take函數(shù), 它可以從一個List取出一定數(shù)量的元素. 如take 3 [5,4,3,2,1],得[5,4,3]. 若要取零或負(fù)數(shù)個的話就會得到一個空List. 同樣, 若是從一個空List中取值, 它會得到一個空List. 注意, 這兒有兩個邊界條件, 寫出來:

take' :: (Num i, Ord i) => i -> [a] -> [a]   
take' n _   
    | n<=0   = []   
take' _ []     = []   
take' n (x:xs) = x : take' (n-1) xs

"快速"排序

假定我們有一個可排序的List,其中元素的類型為Ord類型類的成員. 現(xiàn)在我們要給它排序! 有個排序算法非常的酷, 就是快速排序(quick sort), 睿智的排序方法. 盡管它在命令式語言中也不過10行, 但在haskell下邊要更短,更漂亮, 儼然已經(jīng)成了haskell的招牌了. 嗯, 我們在這里也實(shí)現(xiàn)一下. 或許會顯得很俗氣, 因?yàn)槊總€人都用它來展示haskell究竟有多優(yōu)雅!

它的類型聲明應(yīng)為quicksort :: (Ord a) => [a] -> [a], 沒啥奇怪的. 邊界條件呢? 如料，空List。排過序的空List還是空List。接下來便是算法的定義：排過序的List就是令所有小于等于頭部的元素在先(它們已經(jīng)排過了序), 后跟大于頭部的元素(它們同樣已經(jīng)拍過了序)。 注意定義中有兩次排序，所以就得遞歸兩次！同時(shí)也需要注意算法定義的動詞為"是"什么而非"做"這個,"做"那個,再"做"那個...這便是函數(shù)式編程之美！如何才能從List中取得比頭部小的那些元素呢？List Comprehension。好，動手寫出這個函數(shù)！

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

小小的測試一下, 看看結(jié)果是否正確~

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]   
[1,2,2,3,3,4,4,5,6,7,8,9,10]   
ghci> quicksort "the quick brown fox jumps over the lazy dog"   
" abcdeeefghhijklmnoooopqrrsttuuvwxyz"

booyah! 如我所說的一樣! 若給[5,1,9,4,6,7,3]排序，這個算法就會取出它的頭部，即5。 將其至于分別比它大和比它小的兩個List中間，得[1,4,3] ++ [5] ++ [9,6,7]，我們便知道了當(dāng)排序結(jié)束之時(shí)，5會在第四位，因?yàn)橛?個數(shù)比它小每，也有三個數(shù)比它大。好的，接著排[1,4,3]與[9,6,7]，結(jié)果就出來了！對它們的排序也是使用同樣的函數(shù)，將它們分成許多小塊，最終到達(dá)臨界條件，即空List經(jīng)排序依然為空，有個插圖：

橙色的部分表示已定位并不再移動的元素。從左到右看，便是一個排過序的List。在這里我們將所有元素與head作比較，而實(shí)際上就快速排序算法而言，選擇任意元素都是可以的。被選擇的元素就被稱作錨（pivot），以方便模式匹配。小于錨的元素都在淺綠的部分，大于錨都在深綠部分，這個黃黃的坡就表示了快速排序的執(zhí)行方式：

遞歸地思考

我們已經(jīng)遞不少歸了，也許你已經(jīng)發(fā)覺了其中的固定模式：先定義一個邊界條件，再定義個函數(shù)，讓它從一堆元素中取一個并做點(diǎn)事情后，把余下的元素重新交給這個函數(shù)。 這一模式對List、Tree等數(shù)據(jù)結(jié)構(gòu)都是適用的。例如，sum函數(shù)就是一個List頭部與其尾部的sum的和。一個List的積便是該List的頭與其尾部的積相乘的積，一個List的長度就是1與其尾部長度的和. 等等

再者就是邊界條件。一般而言，邊界條件就是為避免程序出錯而設(shè)置的保護(hù)措施，處理List時(shí)的邊界條件大部分都是空List，而處理Tree時(shí)的邊界條件就是沒有子元素的節(jié)點(diǎn)。

處理數(shù)字時(shí)也與之相似。函數(shù)一般都得接受一個值并修改它。早些時(shí)候我們編寫過一個計(jì)算斐波納契的函數(shù)，它便是某數(shù)與它減一的斐波納契數(shù)的積。讓它乘以零就不行了， 斐波納契數(shù)又都是非負(fù)數(shù)，邊界條件便可以定為1，即乘法的單位元。 因?yàn)槿魏螖?shù)乘以1的結(jié)果還是這個數(shù)。而在sum中，加法的單位元就是0。在快速排序中，邊界條件和單位元都是空List，因?yàn)槿我籐ist與空List相加的結(jié)果依然是原List。

使用遞歸來解決問題時(shí)應(yīng)當(dāng)先考慮遞歸會在什么樣的條件下不可用, 然后再找出它的邊界條件和單位元, 考慮參數(shù)應(yīng)該在何時(shí)切開(如對List使用模式匹配), 以及在何處執(zhí)行遞歸.