Haskell Tutorial(8)懶惰是美德之一


在〈Haskell Tutorial(7)filter、map、fold 模式〉看過了 Haskell 中 filtermap 等函式的實現概念,接下來要談 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());

表面看來,mapfilter 似乎得兩次走訪元素,實際上透過了 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 是 1100 的整數值,在 [] 中從 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 實作。

有時我們會需要計數,例如從 1100,然後又回到 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 來達到!)