Re: [問題] Lazy Evaluation?

作者: Favonia (00010110110001101010100)   2011-11-15 01:14:36
※ 引述《slyfox (klanloss)》之銘言:
: 失敗版:
: sequenceWhile :: Monad m => (a -> Bool) -> [m a] -> m [a]
: sequenceWhile f ms = sequence ms >>= return . takeWhile f
: getCharUntil' c = sequenceWhile (/=c) $ repeat getChar
: 失敗版會一直讀不停
: Lazy evaluation 很耐死的,一定是有什麼誤會…
: → slyfox:但在此例 sequence 被 >>= 規定要"算到底"吧? 11/14 15:10
(不好意思違反版規建議,請幫我把推文刪掉 orz)
>>= 需要判斷左邊有沒有會導致錯誤的指令,而 sequence ms
要如何決定有沒有會導致錯誤的指令?只能全部看過一次!可惜這
個串列怎麼看都看不完。
題外話是 sequence 為了檢查會不會產生錯誤時不需要把每個
指令的結果都「展開到最後」,也就是「算到底」。實際上除非用
deepseq 之類的東西惡搞否則很難算到底...
=== 真相版 ===
上面的理解有個作弊的地方,就是我假設 sequenceWhile 要
算到至少 Weak head normal form (WHNF). 實際上得從 main 開
始逆推才知道什麼是非算不可的...
Haskell 各個函數計算上的意義比較像是「如何拖人下水」
(下水 = 變身成 WHNF)或「如何變身」。理論上有人要拖
sequence ms 下水時,它可以先用 pattern matching 拖人下水,
然後再根據定義變身成 foldr. 可惜這樣還不夠(還不是 WHNF
所以還沒掉到水裡),所以變身成 foldr 後繼續被拖。接著
foldr 可以再用 pattern matching 拖他的參數下水... 文章中
拖來拖去的關係恰好會嘗試把串列中每個元素都拖下去,所以跑
不完。
凡是總要有起頭,基本上一開始 main 就會直接被拖下水,
看看多少人會一起掉下去。喔,然後編譯器會在盡量保留語意的
情況下(理想上是完全保留語意,但是...)用比較有效率方法
實作這種拖人下水的機制;尤其 GHC 實作一堆奇怪的最佳化,
最後真正跑的程式碼可能跟你在 Prelude.hs 翻到的相去甚遠...
作者: godfat (godfat 真常)   2010-01-15 11:01:00
謝謝 :) 是否修改推文則由原作者決定吧
作者: slyfox (klanloss)   2010-01-15 12:06:00
了解 感謝~ 魚好吃 釣竿有好推薦嗎?

Links booklink

Contact Us: admin [ a t ] ucptt.com