在讀Learn you a haskell for great good時(附帶一提,這本書的插圖好可愛,看的時候會開心^^),和某位苦主(看這裡)一樣有個疑問:為什麼foldr
可以處理無限長的串列但是foldl
卻不行?
看了好幾次foldl
和foldr
的定義,都還沒參透的,資質駑鈍的我,只好求助於Google大神。
首先瞧的第一筆資料是這個。這裡講解得很仔細,但是被蠢所纏住的我沒有竟然略過了關鍵點...
foldl is: Left associative: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn ... foldr is: Right associative: f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))其實這段話就解釋了一切。
接著的下一筆結果是這個。打開後看解答的兩段程式碼比較之後,才覺得有點開竅了:
The key here is laziness. If the function you're using for folding the list is strict, then neither a left fold nor a right fold will terminate, given an infinite list. Prelude> foldr (+) 0 [1..] ^CInterrupted. However, if you try folding a less strict function, you can get a terminating result. Prelude> foldr (\x y -> x) 0 [1..] 1把這裡的這兩個例子,對照上一篇所說的內容,就可以發現在
foldr
中,如果在計算f xi (...)
的時候就可以給出結果,那麼,即使遇到了無限長的串列,foldr
就可以把結果交出去。相反的,foldl
必須要逛完整個串列才會開始進行結果的運算。也因此foldl
的結果只能在整個串列被看完之後才能完成。
Haskell wiki上面有一篇文章討論到本文所說的東西。有時間的話,不妨去讀一下喔^^
12/30補記:
其實再稍微往後翻一點(Learn you a haskell),在第六章的Another way to look at folds和Folding infinite lists就有說明了...
下次要沉住氣!
沒有留言:
張貼留言