forked from MnO2/learnyouahaskell-zh
/
recursion.html
95 lines (93 loc) · 16.5 KB
/
recursion.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style>
@import url(css/style.css);
@import url(css/feedback.css);
</style>
<script src="js/jquery.js"></script>
<script src="js/jquery.chili-2.2.js"></script>
<script src="js/script.js"></script>
<script src="js/html2canvas.js"></script>
<script src="js/jsfeedback.js"></script>
<script>
ChiliBook.recipeFolder = "js/chili/";
ChiliBook.automaticSelector = "pre";
</script>
<script>
$(function(){
$('#feedback').click(function(){
$('body').feedback();
})
});
</script>
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-32830659-1']);
_gaq.push(['_trackPageview']);
(function() {
var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>
<title>遞迴</title>
</head>
<body>
<div id="header">
<img id="beta" alt="beta" src="img/beta.png" />
</div>
<div id="main">
<ul class="nav">
<li class="left"> <img src="img/prv.png"></img><a href="syntax-on-function.html">函數的語法</a></li>
<li class="center"><a href="chapters.html">Index</a></li>
<li class="right"> <a href="high-order-function.html">高階函數</a><img src="img/nxt.png"></img></li>
</ul>
<a name="遞迴"></a><h1>遞迴</h1><a name="你好，遞迴！"></a><h2>你好，遞迴！</h2><img src="img/recursion.png" style="float:right"></img><p>前面的章節中我們簡要談了一下遞迴。而在本章，我們會深入地瞭解到它為何在haskell中是如此重要，能夠以遞迴思想寫出簡潔優雅的程式碼。</p><p>如果你還不知道什麼是遞迴，就讀這個句子。哈哈！開個玩笑而已！遞迴實際上是定義函數以呼叫自身的方式。在數學定義中，遞迴隨處可見，如斐波那契數列（fibonacci）。它先是定義兩個非遞迴的數：<i>F(0)=0,F(1)=1</i>，表示斐波那契數列的前兩個數為0和 1。然後就是對其他自然數，其斐波那契數就是它前面兩個數字的和，即<i>F(N)=F(N-1)+F(N-2)</i>。這樣一來，<i>F(3)</i>就是<i>F(2)+F(1)</i>，進一步便是<i>(F(1)+F(0))+F(1)</i>。已經下探到了前面定義的非遞迴斐波那契數，可以放心地說<i>F(3)</i>就是2了。在遞迴定義中聲明的一兩個非遞迴的值（如<i>F(0)</i>和<i>F(1)</i>）也可以稱作<b>邊界條件</b>，這對遞迴函數的正確求值至關重要。要是前面沒有定義<i>F(0)</i>和<i>F(1)</i>的話，它下探到0之後就會進一步到負數，你就永遠都得不到結果了。一不留神它就算到了<i>F(-2000)=F(-2001)+F(-2002)</i>，並且永遠都算不到頭！</p><p>遞迴在haskell中非常重要。命令式語言要求你提供求解的步驟，haskell則傾向于讓你提供問題的描述。這便是haskell沒有while或for循環的原因，遞迴是我們的替代方案。</p><a name="實做Maximum"></a><h2>實做Maximum</h2><p><code>maximum</code>函數取一組可排序的List（屬於 Ord Typeclass）做參數，並回傳其中的最大值。想想，在命令式風格中這一函數該怎麼實現。很可能你會設一個變數來存儲當前的最大值，然後用循環遍歷該 List，若存在比這個值更大的元素，則修改變數為這一元素的值。到最後，變數的值就是運算結果。唔！描述如此簡單的算法還頗費了點口舌呢！</p><p>現在看看遞迴的思路是如何：我們先定下一個邊界條件，即處理單個元素的List時，回傳該元素。如果該List的頭部大於尾部的最大值，我們就可以假定較長 的List的最大值就是它的頭部。而尾部若存在比它更大的元素，它就是尾部的最大值。就這麼簡單！現在，我們在haskell中實現它</p><pre class="code">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</pre><p>如你所見，模式匹配與遞迴簡直就是天造地設！大多數命令式語言中都沒有模式匹配，於是你就得造一堆if-else來測試邊界條件。而在這裡，我們僅需要使用 模式將其表示出來。第一個模式說，如果該List為空，崩潰！就該這樣，一個空List的最大值能是啥？我不知道。第二個模式也表示一個邊緣條件，它說， 如果這個List僅包含單個元素，就回傳該元素的值。</p><p>現在是第三個模式，執行動作的地方。 通過模式匹配，可以取得一個List的頭部和尾部。這在使用遞迴處理List時是十分常見的。出於習慣，我們用個where語句來表示<code>maxTail</code>作為該List中尾部的最大值，然後檢查頭部是否大於尾部的最大值。若是，回傳頭部；若非，回傳尾部的最大值。</p><p>我們取個List<code>[2,5,1]</code>做例子來看看它的工作原理。當呼叫<code>maximum'</code>處理它時，前兩個模式不會被匹配，而第三個模式匹配了它並將其分為<code>2</code>與<code>[5,1]</code>。 where子句再取<code>[5,1]</code>的最大值。於是再次與第三個模式匹配，並將<code>[5,1]</code>分割為<code>5</code>和<code>[1]</code>。繼續，where子句取<code>[1]</code>的最大值，這時終於到了邊緣條件！回傳<code>1</code>。進一步，將<code>5</code>與<code>[1]</code>中的最大值做比較，易得5，現在我們就得到了<code>[5,1]</code>的最大值。再進一步，將<code>2</code>與<code>[5,1]</code>中的最大值相比較，可得<code>5</code>更大，最終得<code>5</code>。</p><p>改用<code>max</code>函數會使程式碼更加清晰。如果你還記得，<code>max</code>函數取兩個值做參數並回傳其中較大的值。如下便是用<code>max</code>函數重寫的<code>maximun'</code></p><pre class="code">maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)</pre><p>太漂亮了！一個List的最大值就是它的首個元素與它尾部中最大值相比較所得的結果，簡明扼要。</p><img src="img/maxs.png" style="float:none"></img><a name="來看幾個遞迴函數"></a><h2>來看幾個遞迴函數</h2><p>現在我們已經瞭解了遞迴的思路,接下來就使用遞迴來實現幾個函數. 先實現下<code>replicate</code>函數, 它取一個<code>Int</code>值和一個元素做參數, 回傳一個包含多個重複元素的List, 如<code>replicate 3 5</code>回傳<code>[5,5,5]</code>. 考慮一下, 我覺得它的邊界條件應該是負數. 如果要replicate重複某元素零次, 那就是空List. 負數也是同樣, 不靠譜.</p><pre class="code">replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
| n <= 0 = []
| otherwise = x:replicate' (n-1) x</pre><p>在這裡我們使用了guard而非模式匹配, 是因為這裡做的是布林判斷. 如果n小於0就回傳一個空List, 否則, 回傳以x作首個元素並後接重複n-1次x的List. 最後, (n-1)的那部分就會令函數抵達邊緣條件.</p><blockquote><p><b>Note</b>: Num不是Ord的子集, 表示數字不一定得拘泥于排序, 這就是在做加減法比較時要將Num與Ord類型約束區別開來的原因.</p></blockquote><p>接下來實現<code>take</code>函數, 它可以從一個List取出一定數量的元素. 如<code>take 3 [5,4,3,2,1]</code>,得<code>[5,4,3]</code>. 若要取零或負數個的話就會得到一個空List. 同樣, 若是從一個空List中取值, 它會得到一個空List. 注意, 這兒有兩個邊界條件, 寫出來:</p><pre class="code">take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs</pre><img src="img/painter.png" style="float:right"></img><p>首個模式辨認若為0或負數, 回傳空List. 同時注意這裡用了一個guard卻沒有指定otherwise部分, 這就表示n若大於0, 會轉入下一模式. 第二個模式指明了若試圖從一個空List中取值, 則回傳空List. 第三個模式將List分割為頭部和尾部, 然後表明從一個list中取多個元素等同於令x作頭部後接從尾部取n-1個元素所得的List. 假如我們要從<code>[4,3,2,1]</code>中取3個元素, 試着從紙上寫出它的推導過程</p><p><code>reverse</code>函數簡單地反轉一個List, 動腦筋想一下它的邊界條件! 該怎樣呢? 想想...是空List! 空List的反轉結果還是它自己. Okay , 接下來該怎麼辦? 好的, 你猜的出來. 若將一個List分割為頭部與尾部, 那它反轉的結果就是反轉後的尾部與頭部相連所得的List.</p><pre class="code">reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]</pre><p>繼續進發!</p><p>haskell支持無限List，所以我們的遞迴就不必添加邊界條件。這樣一來，它可以對某值計算個沒完, 也可以產生一個無限的資料結構，如無限List。而無限List的好處就在於我們可以在任意位置將它斷開.</p><p><code>repeat</code>函數取一個元素作參數, 回傳一個僅包含該元素的無限List. 它的遞迴實現簡單的很, 看:</p><pre class="code">repeat' :: a -> [a]
repeat' x = x:repeat' x</pre><p>呼叫<code>repeat 3</code>會得到一個以3為頭部並無限數量的3為尾部的List, 可以說<code>repeat 3</code>運行起來就是<code>3:repeat 3</code>, 然後<code>3:3:3:3</code>等等. 若執行<code>repeat 3</code>, 那它的運算永遠都不會停止。而<code>take 5 (repeat 3)</code>就可以得到5個3, 與<code>replicate 5 3</code>差不多.</p><p>zip取兩個List作參數並將其捆在一起。<code>zip [1,2,3] [2,3]</code>回傳<code>[(1,2),(2,3)]</code>, 它會把較長的List從中間斷開, 以匹配較短的List. 用zip處理一個List與空List又會怎樣? 嗯, 會得一個空List, 這便是我們的限制條件, 由於zip取兩個參數, 所以要有兩個邊緣條件</p><pre class="code">zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys</pre><p>前兩個模式表示兩個List中若存在空List, 則回傳空List. 第三個模式表示將兩個List捆綁的行為, 即將其頭部配對並後跟捆綁的尾部. 用zip處理<code>[1,2,3]</code>與<code>['a','b']</code>的話, 就會在<code>[3]</code>與<code>[]</code>時觸及邊界條件, 得到<code>(1,'a'):(2,'b'):[]</code>的結果,與<code>[(1,'a'),(2,'b')]</code>等價.</p><p>再實現一個標準庫函數--elem! 它取一個元素與一個List作參數, 並檢測該元素是否包含于此List. 而邊緣條件就與大多數情況相同, 空List. 大家都知道空List中不包含任何元素, 便不必再做任何判斷</p><pre class="code">elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem'` xs</pre><p>這很簡單明瞭。若頭部不是該元素, 就檢測尾部, 若為空List就回傳False</p><a name=""快速"排序"></a><h2>"快速"排序</h2><img src="img/quickman.png" style="float:right"></img><p>假定我們有一個可排序的List,其中元素的類型為Ord Typeclass的成員. 現在我們要給它排序! 有個排序算法非常的酷, 就是快速排序(<i>quick sort</i>), 睿智的排序方法. 儘管它在命令式語言中也不過10行, 但在haskell下邊要更短,更漂亮, 儼然已經成了haskell的招牌了. 嗯, 我們在這裡也實現一下. 或許會顯得很俗氣, 因為每個人都用它來展示haskell究竟有多優雅!</p><p>它的類型聲明應為<code>quicksort :: (Ord a) => [a] -> [a]</code>, 沒啥奇怪的. 邊界條件呢? 如料，空List。排過序的空List還是空List。接下來便是算法的定義：<b>排過序的List就是令所有小於等於頭部的元素在先(它們已經排過了序), 後跟大於頭部的元素(它們同樣已經拍過了序)</b>。 注意定義中有兩次排序，所以就得遞迴兩次！同時也需要注意算法定義的動詞為"是"什麼而非"做"這個,"做"那個,再"做"那個...這便是函數式編程之美！如何才能從List中取得比頭部小的那些元素呢？List Comprehension。好，動手寫出這個函數！</p><pre class="code">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</pre><p>小小的測試一下, 看看結果是否正確~</p><pre class="code">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"</pre><p>booyah! 如我所說的一樣! 若給<code>[5,1,9,4,6,7,3]</code>排序，這個算法就會取出它的頭部，即5。 將其至于分別比它大和比它小的兩個List中間，得<code>[1,4,3] ++ [5] ++ [9,6,7]</code>，我們便知道了當排序結束之時，5會在第四位，因為有3個數比它小每，也有三個數比它大。好的，接着排<code>[1,4,3]</code>與<code>[9,6,7]</code>，結果就出來了！對它們的排序也是使用同樣的函數，將它們分成許多小塊，最終到達臨界條件，即空List經排序依然為空，有個插圖：</p><p>橙色的部分表示已定位並不再移動的元素。從左到右看，便是一個排過序的List。在這裡我們將所有元素與head作比較，而實際上就快速排序算法而言，選擇任意元素都是可以的。被選擇的元素就被稱作錨（<i>pivot</i>），以方便模式匹配。小於錨的元素都在淺綠的部分，大於錨都在深綠部分，這個黃黃的坡就表示了快速排序的執行方式：</p><img src="img/quicksort.png" style="float:none"></img><a name="用遞迴來思考"></a><h2>用遞迴來思考</h2><p>我們已經寫了不少遞迴了，也許你已經發覺了其中的固定模式：先定義一個邊界條件，再定義個函數，讓它從一堆元素中取一個並做點事情後，把餘下的元素重新交給這個函數。 這一模式對List、Tree等資料結構都是適用的。例如，sum函數就是一個List頭部與其尾部的sum的和。一個List的積便是該List的頭與其尾部的積相乘的積，一個List的長度就是1與其尾部長度的和. 等等</p><img src="img/brain.png" style="float:right"></img><p>再者就是邊界條件。一般而言，邊界條件就是為避免程序出錯而設置的保護措施，處理List時的邊界條件大部分都是空List，而處理Tree時的邊界條件就是沒有子元素的節點。</p><p>處理數字時也與之相似。函數一般都得接受一個值並修改它。早些時候我們編寫過一個計算Fibonacci的函數，它便是某數與它減一的Fibonacci數的積。讓它乘以零就不行了， Fibonacci數又都是非負數，邊界條件便可以定為1，即乘法的單位元。 因為任何數乘以1的結果還是這個數。而在sum中，加法的單位元就是0。在快速排序中，邊界條件和單位元都是空List，因為任一List與空List相加的結果依然是原List。</p><p>使用遞迴來解決問題時應當先考慮遞迴會在什麼樣的條件下不可用, 然後再找出它的邊界條件和單位元, 考慮參數應該在何時切開(如對List使用模式匹配), 以及在何處執行遞迴.</p>
<ul class="nav">
<li class="left"> <img src="img/prv.png"></img><a href="syntax-on-function.html">函數的語法</a></li>
<li class="center"><a href="chapters.html">Index</a></li>
<li class="right"> <a href="high-order-function.html">高階函數</a><img src="img/nxt.png"></img></li>
</ul>
</div>
<div id="footer">
</div>
<div id="feedback">Send feedback</div>
</body>
</html>