2012年12月29日 星期六

Haskell: 無盡的路上有foldr真好!

在讀Learn you a haskell for great good時(附帶一提,這本書的插圖好可愛,看的時候會開心^^),和某位苦主(看這裡)一樣有個疑問:為什麼foldr可以處理無限長的串列但是foldl卻不行?

看了好幾次foldlfoldr的定義,都還沒參透的,資質駑鈍的我,只好求助於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就有說明了...
下次要沉住氣!

沒有留言:

張貼留言