Haskell Tutorial（8）懶惰是美德之一


在〈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

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] 就可以了，而且可以指定間隔，倒著指定也可以，例如：

使用 Range

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

使用 Range

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

無限長的 Range

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

take、cycle、repeat

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

take 函式

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 來達到！）