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? 結果寫到這裡很累了，
乾脆就停在這，等下一篇再講...