lethevert is a programmer このページをアンテナに追加 RSSフィード

4/9/2006 (Mon) 晴れ

[]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は全然全く違うものであったりするかもしれません。(そんなことはないと思うけど。)

あと、「評価が正格に行われる ≠ 実行が順番に行われる」です。「評価が正格に行われることが決まっていれば、実行順序を制御しやすい」というのが正しいかな。