微風夕語

[Haskell] 真的比較好懂和不容易出錯嗎？

int sumD (int [] list)
{
    int sum = 0;
    foreach (int element; list) {
        sum = sum + eelemnt;
    }
    return sum;
}

sumHaskell xs | null xs   = 0
              | otherwise = 
                    (head xs) +
                    sumHaskell (tail xs)

int sumHaskell (int [] list)
{
    if (list.length == 0) {
        return 0;
    }

    return list[0] + 
           sumHaskell (list[1..list.length]);
}

sumHaskell v lst | null lst = v
                 | otherwise = 
                       sumHaskell 
                           (v + (head lst))  
                           (tail lst)

int sumHaskell2 (int v, int [] list)
{
    if (list.length == 0) {
        return v;
    }

    return sumHaskell2 (
        v + list[0], 
        list[1..list.length]
    );
}

第 1 篇迴響

1. sumHaskell xs | null xs = 0 2. | otherwise = 3. (head xs) + 4. sumHaskell (tail xs)

可寫成 sumHaskell v, lst | null lst = v | otherwise = sumHaskell(v + (head lst), (tail lst))

第 2 篇迴響

先聲明一下，這篇文章裡，我並不是在強調 Functional Programming 或 Imperative Programming 哪個比較好。

我自己在很多程式裡也大量使用遞迴，而這篇文章也不是想挑 Haskell 或 Function Programming 的缺點。

至少從我學習的經驗看來，Functional Programming 確實是很有趣的東西，常常會有我意想不到的做法（例如怎樣不去改變一個變數的值，就能達到相同的效果），我很享受這樣的過程。

然而我所質疑的，是 Haskell 社群裡一直宣稱的（我幾乎在每一份告訴我為什麼要學 Haskell 的理由裡都會看到），能夠寫出比較不會出錯、比較好懂的程式是真的嗎？（簡潔這點我認同，遞迴在大部份情況下程式確實很短。）

在我看到的說法裡，Haskell 社群宣稱能夠寫出比較好懂，不容易出錯的程式的原因，是因為我們可以用更高階的角度來解問題。

但究竟是一個由小學五年級生都可以重覆出每一個計算步驟的程式比較好懂？還是一個需要極度抽象思考的程式比較好懂？

是一個可以向小學生解釋每一個步驟的演算法比較容易設計又不會出錯，或是一個需要用到大學演算法在教的 divide & conquer 或者是folding ，甚或是什麼 fixed-point function thereoy 觀念的演算法比較不會出錯？

至於會提到遞迴，只是因為這是我認為最明顯的一個例子－－比較高階的抽象層次，不代表一定比較容易懂和不會出錯。

我有太多用遞迴結果冒出 segmentation fault 錯誤訊息，或程式永遠跑不出來，而且還找不到錯在哪的慘痛經驗了。orz…

套一句朝倉啟太的話：請把我當做小學五年級生來解釋你的程式！不能用小學五年級生都能理解的言語解釋出的程式，不能算是真正容易懂的程式！

當然，這是一個 Open Question，對每個人來說，什麼叫好懂是因人而易的。有的人擅長抽象思考，自然會覺得遞迴很好懂，但我相信也有很多像我這種看到遞迴就想把每一個過程寫出來的人吧……囧。

對我而言，能夠讓我用人腦 CPU 跑出結果的程式比較好懂，至少我可以一個個步驟驗證我到底在做什麼，以及每一步是不是對的。

第 3 篇迴響

早上和 letoh 版友在 SayYa 個版上討論後，我對於【正確性】這件事又有以下的新的想法了……

我好像把『容易實作出正確的程式』和『容易設計出正確的演算法』兩件事情混在一起了。>_<

我忽然想推翻我之前的論述了，怎麼辦？XD

應該是正確的抽象思考的演算法比較難設計，可是實作比較簡單，但當演算法有問題時，找出問題點會比較難一點。

低階的演算法設計上比較簡單，但實作上可能會因為種種的原因造成程式的錯誤，而且程式撰寫上出現的錯誤比較難找（因為通常會比較冗長）。

但是如果是演算法本身的問題，低階的演算法則比較容易知道問題所在，因為你可以用人腦一個個部驟重覆出來，看問題到底出在哪。

我一直把寫程式和設計演算法這兩件事混在一起看了說……orz…

不過對於【容易懂】這件事，倒還是維持著上面那篇留言的看法：不能用小學五年級學生都懂的語言解釋出來的程式，不能算是容易懂的程式！

至少我自己不覺得用遞迴（高度抽象）的程式，一定就會比用迴圈（從低階做起）的程式來得好懂。上面的加總的例子，我想就是一個很好的反例。

當然，遞迴有的時候還是很好用的，例如你要算的東西本來就可以直接用數學的遞迴定義下去做（像費伯納西數列、阿克曼函數），反正什麼都不用去管，只要照抄就好，因為已經有人幫我們確認那個數學式是正確的了。:p

可是要想出河內塔的遞迴解法再寫出程式嘛……我們來考程設期中考吧！XD

第 4 篇迴響

遞迴是使用代入法去思考。

為啥會用 library 的函式？ 既然用 library 的函式還不如整計算直接用 library 的函式來完成，還用啥遞迴？

學了幾天 Haskell ，第一個版本，我會這樣寫：

sumHaskell [] = 0 sumHaskell x:xs = x + sumHaskell xs

如果不計算 null case ，亦即 List 的長度最小為 1 ，則可以這樣寫：

sumHaskell [x] = x sumHaskell x:xs = x + sumHaskell xs

第二個版本（tail-recursion 版）可以這樣： sumHaskell ls = sum2 0 ls where sum2 z xs = case xs of [] -> z y:ys -> sum2 (z + y) ys

幾天的學習，我看到 Haskell 相對 imperative language ，特別是像 C++ 和 Java 這類 OOP language ， Haskell 少用了很多不必要 state 變數和中間變數，這是因為 Haskell 簡潔的型別定義（C++ 、 Java 的 class 有很多 member variables），在短短一行型別定義內就把 constructors 定義了，大量使用 monads 、 >>= 、 >> 、 do notation 而隱藏了並 chaining 了內部的狀態和細節， 自然而簡潔的 Curry 語法可以使運算輕易細分並重用，pattern matching 可以直接指派結構中的資料到變數。

變數不可變其中一個是好處是天生就 thread-safe 。

我看到的文章是說 Haskell 可以直接用寫規格。 想一想，又好像是真的，因為沒有中間暫存變數，所以直即寫下想到的資料結構、界面就可以，因為沒有 side-effect ，所以直接寫下函式原型就可以表示函式的作用。

在 Haskell 中，資料結構定義和 interface （Haskell 中即是 class）是分離的，資料結構根本不用受到繼承問題的束縛。

第 5 篇迴響

這 blog 打出的空格都自動「壓縮」了，太 HTML 了，都不把空格替換成 &nbps; ，Haskell使用 layout system，換行和縮排會自動轉換成語法成份。

第 6 篇迴響

依學習到的命名慣例，第二個版本（tail-recursion 版）可以改成這樣： sumHaskell xs = sumHaskell’ 0 xs 　where sumHaskell’ z xs’ = case xs’ of 　　[] -> z 　　x:xs" -> sumHaskell’ (z + x) xs"

>> 我們寫出的程式是和直覺相反的！ 因為 Haskell 是 lazy evaluation 的，所以應該這樣想：

1. sumHaskell [3 , 5 , 7 , 9]
2. 3 + sumHaskell [5 , 7 , 9]
3. 3 + (5 + sumHaskell [7 , 9])
4. 3 + (5 + (7 + sumHaskell [9]))
5. 3 + (5 + (7 + (9 + sumHaskell [])))
6. 3 + (5 + (7 + (9 + 0)))

至於第二個版本的 sumHaskell’ z xs 的 z 是用來存放計算的結果：

1. sumHaskell’ 0 [3 , 5 , 7 , 9] → z = 0, 對應 int sum = 0
2. sumHaskell’ (0 + 3) [5 , 7 , 9] → z = z + 3 = 0 + 3, 對應 sum = sum + element
3. sumHaskell’ ((0 + 3) + 5) [7 , 9] → z = z + 5 = (0 + 3) + 5
4. sumHaskell’ (((0 + 3) + 5) + 7) [9]
5. sumHaskell’ ((((0 + 3) + 5) + 7) + 9) []
6. (((0 + 3) + 5) + 7) + 9 → 對應 [] -> z

第一個版本多出來的 0 和第二個版本要多一個參數的解釋： 遞迴使用的是事物的自相似性，即是事物的局部與整個事物相似，亦即是事物包含事物自己，因此有「遞迴步驟」（借用數學歸納法的「歸納步驟」這一術語）： sumHaskell x:xs = x + sumHaskell xs –第一個版本 sumHaskell’ z x:xs = sumHaskell’ (z + x) xs –第二個版本 但是遞迴結束時，事物已到終點，不再包含自己，因此遞迴結束是一個特殊情況，要加一個獨立的 case 表述： sumHaskell [x] = x sumHaskell x:xs = x + sumHaskell xs 而 sumHaskell [] 應該是 error 才是。 考慮到 sumHaskell [] 的情況的話，我們也可以給它一個數值： sumHaskell [] = undefined sumHaskell [x] = x sumHaskell x:xs = x + sumHaskell xs 而考慮到 sumHaskell [x] 是 sumHaskell [] 的前一個計算，所以可以把 sumHaskell [x] 結合到遞迴步驟中去而少寫一行，把sumHaskell [] 變做遞迴的終結情況，因而 sumHaskell [] 要顧慮到遞迴中尾二的計算，不能影響它，因而要使用加法單位元 0 ： sumHaskell [] = 0 sumHaskell x:xs = x + sumHaskell xs 而第二個版本在一串計算開頭加 0 明顯也是一個特殊情況，要在遞迴步驟之外處理，這裡有兩個問題： 1. 怎樣知道是在計算的開頭？ 2. 遞迴步驟的 pattern 是怎樣？每一次計算要計算甚麼？要返回甚麼？ 0 + firstElement + secondElement + thirdElement… = (…(((0 + firstElement) + secondElement) + thirdElement) + …) = (…((第一次計算結果 + secondElement) + thirdElement) + …) = (…(第二次計算結果 + thirdElement) + …) = (…第三次計算結果 + …) = let 今次計算結果 = 前一次計算結果 + element in 返回後一次的返回結果 問題是之後的計算要使用到今次計算結果，如果不使用額外的一個參數， code 就可能要寫成這樣（偽碼）： sumHaskell’ [] = "result" variableOf (scopeOf caller) sumHaskell’ x:xs = 　let result = if caller != sumHaskell 　　then 0 + x 　　else "result" variableOf (scopeOf caller) 　in sumHaskell’ xs 但 Haskell 是使用詞法有效範圍（lexical scope）的，而不是動態有效範圍，又怎樣讀取 caller中定義的變數？而且就算是動態有效範圍，也是被 shadow 了的變數。（而且這裡的 caller 明顯不是 referential transparent）因此，取代作為儲存結果的local變數 result ，就要加多一個參數： sumHaskell’ result [] = result sumHaskell’ result x:xs = sumHaskell’ (result + x):xs 而且這樣還不用判斷是否一串計算的開頭，計算的開頭結合到遞迴步驟中去，並由最開始的呼叫者餵給未開始計算之前的 result 參數一個 0 。

迴圈真的小學生也明白嗎？我依稀記得以前初學程式設計語言時，還不每次看到迴圈也都要在腦中 try run 。就算現在我看到一些複雜的嵌套迴圈，還不是要在腦中 try run 一兩次才瞭解作用？但迴圈有其常用的 patterns ，熟了之後就會覺得很易理解，遞迴不也是同樣道理嗎？

第 7 篇迴響

說真的，這麼長又是個人觀點的系列性的文章，建議您直接在發表在個人的網誌上，再發引用過來就好了，不需要一直用回響的方式留言，這裡畢竟不是討論區……orz

我想這樣子您的文章脈絡會更清晰，而且文章的 credit 也會更清楚地是屬於你的。

另外，我刪掉到數第二篇那篇不完整的留言了。

第 8 篇迴響

本來沒有打算這樣的，只是每次回響完，總覺得未想透，所以就變成這樣，抱歉。

我又發覺未想透，又有想補充的地方……

第 9 篇迴響

關於遞歸函數的寫法，提供一個觀點會比較自然 …

像是 list 的 length，一個是 [] 的情況，另一個是 x : xs 的情況，將他想作數學歸納法的 base case 跟 inductive case，就是說，length 是一個傳回 list 長度的函數。

在 base case 的時候，[] 的長度是 0。在 inductive case，假設我們已經有 length xs 是回傳 xs 的長度，那麼 length x:xs 要是一個 x:xs 長度。

這樣想避免我們去想遞歸時，那一層又一層的函數呼叫，好像把事情反轉，雖然是這樣算，但其實比較像推導骨牌，從底層往上推。

而是事實上也是如此，對於 type system 更強的語言來說（強到足以被用來作定理證明的程式），遞迴函數的確是被當作歸納法的證明。

第 10 篇迴響

嗯，很少看到这个角度的，对函数式和命令式语言的比较，所见略同，并深以为然。

我对此有自己的分析。在真实世界中，我们碰到的问题有些是关于“是什么”的问题，另一些是关于“如何做”的问题。前一个问题用函数式，逻辑式都是很直观的，后一个问题用命令式是直观的。

在如何结合声明式和命令式编程方面，如何在声明式代码和命令式代码之间建立等效关系，程序设计语言的领域还有大量的空白等着开拓。

第 11 篇迴響

你覺得很難對小五生解釋遞迴版的做法，是因為你想要一五一十描述整個演算的過程，讓你們變成機器ㄧ般照著指令去作。 遞迴的演算法本身就是把規模大的問題持續分解成較小的問題，直到小到你可以確定你能正確求出問題的答案，並在分解的過程作有助於逼近答案的事情(如果可以的話)。如果你以較高層面的描述方式去解釋遞迴版的求和問題，小五生不是沒有機會了解。

不曉得 D 的 foreach 應用在 array 是 iterator 的概念還是遞增 index 的概念？ foreach (int element; list) { sum = sum + eelemnt; }

如果上述的 foreach statement 實際上是以 index 來走訪，其與小五生手算的過程會比遞迴版演算來的更不自然。 因為一般人拿到一堆數字(在紙上)要求和時，並不會先去算總共有幾個，然後一值記著我目前加到第幾個直到加過全部的數。而是先拿出第一個數與 0 相加(當然這一步小五生會懂得不需要)，再拿出一個數來與目前的和相加，並刪掉已算過的數直到沒有剩下任何未刪掉的數。

我個人覺得這樣子的演算過程其實與遞迴版的演算法有很高的相似度。

public class Calculator { public static double sum(java.util.Queue numbers) { return sumImpl(0.0, numbers); }

private static double sumImpl(double acc, java.util.Queue numbers) {
    if (numbers.size() == 0)
        return acc;
    else
        return sumImpl(acc + numbers.poll().doubleValue(), numbers);
}

}

留下迴響