Haskell : モナドの実行順序

（追記:9/5 4:41）
このエントリーの内容は、間違っていることが分かりました。詳細はコメント欄にて。

• • • • -

[id:sshi:20060903:p3], [id:lethevert:20060903:p4], g:hatena:id:jmk:20060903:1157298199の続き。
私はちょっと勘違いしていたことに気づきました。
モナドは、そのクラス定義からして、評価が正格に行われることが（ほぼ）決まっています。

class  Monad m  where
    (>>=)   :: m a -> (a -> m b) -> m b
    (>>)    :: m a -> m b -> m b
    return  :: a -> m a
    fail    :: String -> m a

    m >> k  =  m >>= \_ -> k
    fail s  = error s

という定義だそうですが、bindの定義を見ると

(>>=)   :: m a -> (a -> m b) -> m b

「m a」という入力を「a -> m b」という関数に適用させているところが見て取れます。
ここで、bindを適用するには、まず「m a」というデータから「a」を取り出して「a -> m b」に適用しなければならないわけですが、この「a」を取り出すタイミングで必ず評価が行われるわけで、逆にいえば、評価を行わなければ「a -> m b」に適用できないということで、つまり正格評価になっています。

lookup k lst >>= f >>= g >>= h

という例（Maybeモナド）を見ると、bindを使って書き直せば、

bind h (bind g (bind f (lookup k lst)))

となるわけですが、最左最外簡約の手順に従って評価を考えてみると、まず「h」を「bind g (bind f (lookup k lst))」に適用しようとするわけですが、これはモナドなので、ここから値を取り出さなければ「h」に適用できません。そこで、「g」を「bind f (lookup k lst)」に適用しようとするわけですが、やはりこれもモナドなので、値を取り出すためには、さらに「f」を「lookup k lst」に適用しようとします。もちろん「lookup k lst」もモナドなので、ここから値を取り出すために、「lookup k lst」を評価します。「lookup k lst」を評価すると、結果は「Just x」もしくは「Nothing」なので、

    Just x  >>= k = k x
    Nothing >>= k = Nothing

に従って、「Just x」の場合だけ「f x」として適用が行われます。
ということでまとめると、

1. lookup k lst
2. bind f (1.の結果)
3. bind g (2.の結果)
4. bind h (3.の結果)

というように評価が進みます。

• • • -

ところで、

do v <- lookup k lst
   return 0

の場合は、bindがつながっていないので、lookup k lstが評価されないのは当然なのですが、do記法を通常のeagerな言語の連想で考えると、不思議なように感じるかもしれません。

• • • -

あ、でも、この辺の考察は、基本的にCleanの評価戦略に関する知識をベースにしているので、Haskellは全然全く違うものであったりするかもしれません。（そんなことはないと思うけど。）
あと、「評価が正格に行われる ≠ 実行が順番に行われる」です。「評価が正格に行われることが決まっていれば、実行順序を制御しやすい」というのが正しいかな。