Haskell Tutorial（7）filter、map、fold 模式 << 前情

在〈Haskell Tutorial（7）filter、map、fold 模式〉看過了 Haskell 中 filter、map 等函式的實現概念，接下來要談 Haskell 中一個重要的特性 – 惰性（Laziness）。先來個簡單的問題，令 addOne = map (+1)，如果執行 addOne $ addOne $ addOne [1, 2, 3, 4, 5] 的話，會有什麼結果呢？你會先得到一個清單 [2, 3, 4, 5, 6] 後，傳給 addOne 函式再得到一個最後的結果清單 [4, 5, 6, 7, 8] 嗎？

惰性求值

方才問題的答案是「不！Haskell 在你真正要取得結果之前，並不會執行函式。」

在執行 addOne $ addOne $ addOne [1, 2, 3, 4, 5] 時，最右邊的 addOne 函式並不會立刻執行，它只會說：「嘿！我知道我該做些什麼，不過待會有需要再做！」第二個 addOne 也是如此，當最左邊的 addOne 函式必須對清單第一個元素加 1 時，第二個 addOne 函式就會要求最右邊的 addOne 函式傳回一個計算後的元素，當最左邊的 addOne 函式要對下個元素加 1 時，相同的過程又會再發生一次。

Haskell 是惰性的（Lazy），所以最終只會走訪一次清單，而不是走訪三個清單，藉此改進效能。

在一些主流語言中，開發者撰寫程式時，遇到迴圈走訪 List 處理的問題時，通常會為了自我想像的效能改進，可以在一次迴圈中處理完的動作，就全部塞到一個迴圈，因而經常造成迴圈中的程式碼異常難懂，一次迴圈做了很多事情。

難道不是這樣的嗎？如果你要對一個 List 的元素全部加 5，然後再過濾出大於 100 的值，走一次迴圈就完成，總比先全部加 5 後得到一個 List，再從這 List 中過濾一個 List 出來快吧？

表面上看來是如此，不過實際上，一次處理一件事，之後透過評測與設計來改進效能的機會與效益，往往會比斤斤計較少用幾次迴圈來得好！例如，Java 8 之後的 Stream API，可以這麼做：

List<Integer> result = list.stream()
                           .map(elem -> elem + 5)
                           .filter(elem -> elem > 100)
                           .collect(toList());

表面看來，map、filter 似乎得兩次走訪元素，實際上透過了 Stream 的惰性設計，只會走訪一次元素，如果你的清單很大，而你的電腦擁有多核 CPU，那麼還可以試著將 stream 改為 parallelStream，嘗試平行處理改進效能的可能性。

在 Haskell 中，惰性是與生俱來的，來看看以下這個範例：

filter (> 100) $ map (+ 5) lt 不會馬上求值，只有在 GHCI 要求要取得 List 以顯示時，filter 才會被要求執行，而此時 filter 才會進一步要求 map 執行。Haskell 中到處都是函式，因此，就算你只是寫個 1 + 2，它也不會馬上執行，例如有個函式 doSome 接受一個值，而你以 addSome (1 + 2) 呼叫，實際上，它不會馬上計算 3 來以呼叫 addSome，只是將 1 + 2 傳進去，當 addSome 內部真的需要引數值時，才會真的求得 3 這個值。

可以無上限的 Range

在〈Haskell Tutorial（6）從 List 處理初試函數式風格〉中，你知道可以使用 [1, 2, 3] 來建立一個 List，也知道其實這不過是 1:2:3:[] 的語法蜜糖，現在如果你要有個 List 是 1 到 100 的整數值，在 [] 中從 1 打到 100 太傻了，也許你想到了，可以寫個 range 函式：

range :: Int -> Int -> [Int]
range first last =
    if first > last then []
    else first : range (first + 1) last

這樣就可以用 range 1 100 來產生你要的 List，好吧！這不過是要讓你再練習一次函數式的思考罷了，Haskell 中不用自己寫這個函式，只要寫 [1 .. 100] 就可以了，而且可以指定間隔，倒著指定也可以，例如：

實際上，如果要產生 'A' 到 'Z' 的字母，也只要寫 ['A' .. 'B'] 就可以了，

簡單來說，只要你的值有實現 Enum 這個 Typeclass 的行為，就可以使用這個方式來產生 List。最有趣的是，如果不指定上限，你可以產生一個無限長的 Range，例如：

沒問題！因為 Range 是惰性的，在真正需要值之前，並不會真正產生內容。你可以試著在 GHCI 中顯示 naturals 的值，這時就會一直求值下去，沒完沒了！

take、cycle、repeat

一個沒有上限的 Range 可以做什麼？也許你想求得一些數值，像是〈阿姆斯壯數 （Armstrong number）〉，你想取得 10 個阿姆斯壯數，只是不知道這些數會在哪出現，那麼就可以這麼寫：

take 函式會從 List 中取得指定的前幾個元素，因為惰性的關係，如果你寫 take 10 [1 ..]，即使 [1 ..] 代表無限長的 Range，那就只會取得 [1,2,3,4,5,6,7,8,9,10]。

類似地，take 10 $ filter isNarcissistic [100 ..] 時，並不會馬上對 [1 ..] 執行 filter，只有 take 函式逐一要求取得下個數時，才會去要求 filter 執行，因此實際上，只會從 [100 ..] 取得 93084 - 99 個值！對了，isNarcissistic 這函式是來自〈阿姆斯壯數 （Armstrong number）〉中的 Haskell 實作。

有時我們會需要計數，例如從 1 到 100，然後又回到 1 重新計數至 100，一直重複下去，這類需求在 Haskell 中也許可以 cycle 函式，給他一個 List，它會將這個 List 的元素循環地產生，一樣地，因為惰性的關係，不會馬上求值，搭配 take 的話，像是 take 10 $ cycle [1, 2, 3] 就會產生 [1,2,3,1,2,3,1,2,3,1]。

如果只是要重複一個數，可以使用 repeat，例如 repeat 10 會產生無限的 10，當然，它是惰性的，因此可以搭配其它函式來設定終止條件，像是 take 100 $ repeat 10，就會產生 100 個元素的 List，每個元素都是 10。

（實際上，有個 replicate 函式，take 100 $ repeat 10 這需求，可以使用 replicate 100 10 來達到！）

後續 >> Haskell Tutorial（9）最代表宣告式的 List Comprehension