Haskell Tutorial(9)最代表宣告式的 List Comprehension


在數學中,會使用一些 集合建構式符號 來描述一個集合(Set),像是有 10 個元素的 5 倍數集合可以表示為 {5 * x | x ∈ N, x ≤ 10},這也稱為 Set Comprehension。

如果有個需求是產生一個 List,其中的元素就是 {5 * x | x ∈ N, x ≤ 10},根據〈Haskell Tutorial(8)懶惰是美德之一〉的說明,你可以使用 take 10 $ [5, 10 ..],這就會建立 [5,10,15,20,25,30,35,40,45,50],不過,若寫成 [5 * x | x <- [1 .. 10]],也可以得到相同的結果,寫法與 Set Comprehension 類似,一看就懂,因為產生的結果是個 List,因而稱之為 List Comprehension。

不過,List Comprehension 終究不是 Set Comprehension,對於 {5 * x | x ∈ N, x ≤ 10},你不能真的寫成 [5 * x | x <- [1 ..], x <= 10],這在需要求值時不會產生 [5,10,15,20,25,30,35,40,45,50] 後就收工,而是無止盡地求值下去,因此,想使用 List Comprehension 來表達 Set Comprehension,你還是得做一些轉換。

實際上,讓你能表達 Set Comprehension,並不是 List Comprehension 之目的,就如從 Set Comprehension 可一眼就看出集合定義,某些 Haskell 程式碼你可以改寫為 List Comprehension,讓程式的意圖更明顯,這才是 List Comprehension 的目的,就像方才將 take 10 $ [5, 10 ..] 改為 [5 * x | x <- [1 .. 10]] 那樣。

基本的 map 與 filter

顯然地,少了條件式的 List Comprehension,就能做到 map 函式的功能,例如 map (+ 3) [1, 2, 3, 4, 5],也可以使用 [x + 3 | x <- [1, 2, 3, 4, 5]]。你也能使用 List Comprehension 來實作一個 map' 函式:

map' :: (Int -> Int) -> [Int] -> [Int]
map' mapper lt = [mapper elem | elem <- lt]

如果 List Comprehension 加上條件式,也可以達到單純過濾元素的功能,例如 filter (> 3) [1, 2, 3, 4, 5],也可以使用 [x | x <- [1, 2, 3, 4, 5], x > 3] 來得到,也能使用 List Comprehension 來實作一個 filter' 函式:

filter' :: (Int -> Bool) -> [Int] -> [Int]
filter' predicate lt = [elem | elem <- lt, predicate elem]

當然,就簡單的對應與過濾來說,使用 [x + 3 | x <- [1, 2, 3, 4, 5]][x | x <- [1, 2, 3, 4, 5], x > 3],並不會使用 map (+ 3) [1, 2, 3, 4, 5]filter (> 3) [1, 2, 3, 4, 5] 來得清楚,不過,如果是 map (+ 3) $ filter (> 3) [1, 2, 3, 4, 5][x + 3 | x <- [1, 2, 3, 4, 5], x > 3] 相比,那後者倒是就清楚許多。

更多 List Comprehension

來看看更多 List Comprehension 的語法,如果在取得 List 中的元素時,實際上不需要元素值,那麼 <- 左邊可以使用 _,例如,[1 | x <- [1, 2, 3, 4, 5]],可以寫成 [1 | _ <- [1, 2, 3, 4, 5]],嗯?這是什麼?例如,來用 List Comprehension 寫個 length' 函式:

length' :: [Int] -> Int
length' lt = sum [1 | _ <- lt]

每取得一個元素就計數 1,最後加總就是 List 的長度,夠簡單!如果要取得三邊長不大於 10 的直角三角形呢?三角不等式定義是兩邊之和大於第三邊,而直角三角型是兩邊的平方和等於斜邊平方。如果你要用 filtermap 兜出這個需求可不容易(我是不太想兜,你可以試試),如果用 List Comprehension,三邊長不大於 10,可以使用三個 [1..10] 列舉,若以其中一個 [1..10] 作為最長邊,依三角不等式定義,使用 List Comprehension 可以寫成:

[[a, b, c] | 
    a <- [1..10], b <- [1..10], c <- [1..10],
    a <= b, b <= c]

List Comprehension 可以列舉多個 List,只要以 , 做區隔,接下來加上直角三角型定義:

[[a, b, c] | 
    a <- [1..10], b <- [1..10], c <- [1..10],
    a <= b, b <= c, 
    a ^2 + b ^ 2 == c ^ 2]

最後得到 [[3,4,5],[6,8,10]] 的結果,只要寫下問題定義,Haskell 就會為你求解。

命令式?宣告式?

只要寫下問題定義,Haskell 就會為你求解,這樣的風格就是宣告式(Declarative),這是函數式程式設計,一直強調它與命令式(Imperative)程式設計不同之處,在宣告式的設計中,你著重的是 WHAT,而不是 HOW,就像上面求直角三角形的例子,你著重的是「直角三角形是什麼?」,而不是「如何找出直角三角形」,如果是命令式求解,例如 Java 的話,會像是這樣:

List<List<Integer>> tris = new ArrayList<>();
range(1, 11).forEach(a -> {
    range(1, 11).forEach(b -> {
        range(1, 11).forEach(c -> {
            if(a <= b && b <= c && a * a + b * b == c * c) {
                tris.add(asList(a, b, c));
            }
        });
    });
});

程式碼變成著重在 List 要如何建立,儘管已經使用了 Java 8 的 Lambda 相關功能,程式碼仍不見得好懂。

來舉另一個例子,〈阿姆斯壯數〉,其定義為在 n 位的整數中,加總每個數字的 n 次方後等於該整數,例如 153 是個阿姆斯壯數,因為 13 + 53 + 33 = 153

如果你的需求是,找出 3 位數的阿姆斯壯數有哪些,那你要定義(宣告)「什麼」是 3 位數的阿姆斯壯數,也就是「在 3 位的整數中,加總每個數字的 3 次方後等於該整數」。

在 〈阿姆斯壯數的 Haskell 程式實作〉,已經示範了一種定義方式,其中需要將 n 位整數分解為各數字,再判斷加總每個數字的 n 次方後等於該整數,這邊可以換另一個方向,首先定義 3 位的整數:

[x * 100 + y * 10 + z| 
    x <- [1..9], y <- [0..9], z <- [0..9]]

接下來,加入加總每個數字的 3 次方後等於該整數的定義:

[x * 100 + y * 10 + z| 
    x <- [1..9], y <- [0..9], z <- [0..9], 
    x ^ 3 + y ^ 3 + z ^ 3 == x * 100 + y * 10 + z]

List Comprehension 中可以使用 let,例如,你可以令 x * 100 + y * 10 + znumber,這樣就不用重複計算這個算式了:

[number| 
    x <- [1..9], y <- [0..9], z <- [0..9], 
    let number = x * 100 + y * 10 + z, 
    x ^ 3 + y ^ 3 + z ^ 3 == number]

跟命令式比較一下,例如 Java 的實作,哪個比較清楚呢?

List<Integer> numbers = new ArrayList<>();
range(1, 10).forEach(x -> {
    range(0, 10).forEach(y -> {
        range(0, 10).forEach(z -> {
            int number = x * 100 + y * 10 + z;
            if(x * x * x + y * y * y + z * z * z == number) {
                numbers.add(number);
            }
        });
    });
});