What have you found for these years?

2011-05-07

structural or sequential?

讓我覺得很困惑的東西在上一篇裡忘記講了。

在傳統的 imperative 程式裡,我們很自然會去想 flow, 會去想
程式是怎麼執行的。一行一行地執行,最簡單的說法大概是這樣。

而在 haskell 的程式裡,因為所有的東西都是 immutable, 再加上
所謂 lazy evaluation, call-by-need, whatever, 因此我們變得要
去描述問題,而非撰寫「步驟」去解決問題。也因此,我們無法
預測 runtime 上程式到底是怎麼執行的。到底是先算 A, 還是先算 B?

之前我還一直無法從這種「順序」的概念中逃離,所以對於 foldr
和 foldl, 我的理解一直變成 foldr 是從右邊開始,反之則從左邊開始。
這樣想很容易理解,因為我(們)寫程式太習慣「順序」了。在簡單的
例子中,大概也看不太出很大的差別。但如果試著用 IO 去觀察其真正的
執行順序的話,就會注意到這完全是無法解釋的。因為事實上,foldr
和 foldl 的結果是一種結構,而非一連串的順序。

foldr (-) 0 [1,2,3,4,5] 展開會是 1 - (2 - (3 - (4 - (5 - 0))))
foldl (-) 0 [1,2,3,4,5] 展開會是 ((((0 - 1) - 2) - 3) - 4) - 5

foldr 是向右結合,foldl 則是向左結合。cons list 也是一種向右結合的結構,
因此我們也會說,foldr 在 cons list 上,其實只是把 constructor 換掉而已。
我們不能把 fold 的結果看成一個數值,而應該是一種結構才對。一個很
簡單的例子,試著把 [1,2,3,4,5] 用 foldr 印出來看看:

foldr (curry (print . fst)) (return ()) [1..5]
updated 2011-05-14 22:44 或
foldr (const . print) (return ()) [1..5]
如果這樣寫不好懂的話,這是寫成 lambda 的樣子:
foldr (\i io -> print i) (return ()) [1..5]

如果我們試著去 evaluate 這個,也就是餵給 ghci 這個「結構」,
結果是我們只會得到一個 1, 而不是這個:
5
4
3
2
1

難道這樣應該說,foldr 其實是從左邊開始算才對嗎!?

回頭看剛剛的展開:1 - (2 - (3 - (4 - (5 - 0))))
用想像的,把裡面的 - 改成 curry (print . fst)
可以注意到,其實我們根本不在乎 print 後的結果 ( IO () ),
因此 evaluate 這個結構,就好像我們對一個 cons list 呼叫 head 一樣,
拿了第一個值,然後後面的根本就不需要,於是全部不會執行。

正確的寫法是這樣:
foldr (\i io -> io >> print i) (return ()) [1..5]
updated 2011-05-14 22:44 或
foldr (flip (>>) . print) (return ()) [1..5]

我們必須強迫算出 1 之前,必須先算出後面的東西。這整個展開來,就會變成...
return () >> print 5 >> print 4 >> print 3 >> print 2 >> print 1
monad law 告訴我們 bind 是 associative 的,所以這邊括號省略了。

而 foldl 的話則是:
foldl (\io i -> io >> print i) (return ()) [1..5]
updated 2011-05-14 22:44 或
foldl (flip (flip (>>) . print)) (return ()) [1..5]
展開來則是:
return () >> print 1 >> print 2 >> print 3 >> print 4 >> print 5
印出來就會是:
1
2
3
4
5

也就是說,唯一真正可以控制順序的,只有 IO monad 的 bind...

或是我們可以這麼說,我們總要有一個地方,可以說我們需要某個值?
不然程式要怎麼「開始」跑呢..? 或許可以這樣想像,haskell 的程式
就是一個巨大的 term, 所謂的執行程式,其實就是開始 reduce 的意思。
而這個神秘的開始 reduce, 大概就是 main 吧..


等等看 Josh 在 facebook 上說他要解釋 T-algebra,
說不定有助於理解 IO monad XDD 或是我真的該讀一讀這篇..
The Haskell Programmer's Guide to the IO Monad --- Don't Panic


其實這篇本來想說 strict or non-strict? 結果寫到這裡很累了,
乾脆就停在這,等下一篇再講...

0 retries:

Post a Comment

All texts are licensed under CC Attribution 3.0