LoginSignup
18
13

More than 5 years have passed since last update.

HaskellスペースリークAdvent Calendar 2015Day 4
@ruicc(Ruichi Kos)

正格評価と遅延評価（モナド編）

Last updated at Posted at 2015-12-03

モナドの挙動は少しわかりにくいためもう少し詳しく扱うことにしました。

モナドと遅延評価とその周辺

モナドはMonadクラスのinstanceになっている（かつモナド則を満たす）データ型を指しますが、それだけで構成されているわけではありません。

  • return
  • (>>=)
  • モナド固有のアクション

モナドを用いた関数では、「モナドアクション」とそれらを結合する(>>=)で構成されていると言えます。
モナドの評価順序を考慮する際に厄介なのは、これらを両方考慮しないといけないということです。

アクションの評価とアクションの返り値の評価

モナドにおいては、「アクションの評価」と「アクションの返り値の評価」を別に考える必要があります。

n :: IO ()
n = do

    let return1 x = trace "return 1" $ return x
        return2 x = trace "return 2" $ return x
        return3 x = trace "return 3" $ return x

        succ1 x = trace "succ 1" $ succ x
        succ2 x = trace "succ 2" $ succ x
        succ3 x = trace "succ 3" $ succ x

    x <- return1 $ succ1 42
    y <- return2 $ succ2 x
    z <- return3 $ succ3 y

    print z

returnとsuccそれぞれにtraceを仕込んでみたものです。結果は以下です。

return 1
return 2
return 3
succ 3
succ 2
succ 1
45
  • アクションが並べた順に評価され、
  • そのあとにsuccが順々に(Leftmost outermost)発火しています。

succの評価はprintの要求から発生しており、「アクションの評価」と「アクションの返り値の評価」が分かれていることが確認出来ます。

個々のモナドとアクションの評価

アクションの評価とアクションの返り値を個々のモナド別に考えていきます。

例えば(Lazy)Stateモナドを見てみます。

instance (Monad m) => Monad (StateT s m) where
    return a = state $ \ s -> (a, s)
    m >>= k  = StateT $ \ s -> do
        ~(a, s') <- runStateT m s
        runStateT (k a) s'

(>>=)の定義に着目してみると、パターンマッチしてる箇所が1箇所しかないことがわかります。
~はLazy pattern matchと言って、パターンマッチを遅延させるものです。ここではaを評価する部分が存在しないことに注目してください。

(Strict)Stateでは一箇所だけ異なっています。

instance (Monad m) => Monad (StateT s m) where
    return a = state $ \ s -> (a, s)
    m >>= k  = StateT $ \ s -> do
        (a, s') <- runStateT m s
        runStateT (k a) s'

こちらにもタプルのパターンマッチが見て取れます。しかしそれ以上評価はされないはずで、どちらのStateモナドにおいても、(>>=)によってaに相当する値は評価されないように思われます。
固有のアクションgetとputを確認します。

get :: (Monad m) => StateT s m s
get = state $ \ s -> (s, s)

put :: (Monad m) => s -> StateT s m ()
put s = state $ \ _ -> ((), s)

固有アクションを見ても、aに相当するアクションの結果も、加えてsの状態の値も評価されないように見えます。caseとかseqとか書いてないですから。パラメータ化された型の値のサンクを潰している箇所がモナドの定義内に存在しません。
この性質はどのモナドでも同様なのでしょうか？

Parametricityと遅延評価

Parametricityを、Parametric Polymorphismに基づく性質としましょう。
JavaやC#を触っている人はジェネリクスを想像してください。これが面白い性質をいろいろ持っていますが、ここでは遅延評価との関係性を見ていきます。

まずパラメータ化された型を持つ値には触れません。
JavaのCollectionsを考えてみてください。例としてList<T>を考えましょう。List<T>の中身（ここではT）はジェネリクスでパラメータ化されています。
Listクラスにとっては、その中身に触ることができません。なぜなら、Listクラスは任意の(arbitrary)型を取らなければならないからです。任意の型を内部に保持するためにはどうすればいいでしょうか？それはIntegerかもしれないしStringかもしれないしList<Integer>やHashMap<Int,HashMap<Int,List<String>>>かもしれません。何が来るかわからないのだから、Listクラスはその値には触ることができません。

具体的に中身のオブジェクトをobjとすると、 obj.show(); とか呼べないわけです。showメソッドを持ってなかったらエラーが出てしまいます。実際は型エラーで弾かれますが。パラメータ化された型をもつ値には、一切触れないし、触ってはいけません。ではもし全ての型で存在するメソッドなら呼び出してもいいのでしょうか？そんな異常な仮定は出来ればしないでほしいのですが、理屈としてはその通りです。

Haskellの話に戻ります。全ての型が持っているメソッドは存在しません。自然ですね。なのでparametricな型を持つ値には、触ることは出来ません。そして触ることができない値のサンクは潰せません。これは非常に便利な性質です。

...残念ながら例外があります。seqという特殊な関数は、型が何であろうともWHNFに潰すことができてしまいます...BangPatternsを用いても同様です。しかし、型がわからないということはWHNFがどういう状態であるかがわからないということです。そういう何が起こるか分からない状況下でseqやBangPattensを使うモチベーションはあまり発生しないでしょう。「そんなことをする人がこれからGHCにStrictプラグマが導入された時に無限ループを頻発させるのです」1。以降parametricな型を持つ値に関してseqで評価するようなことはないとして話を進めます。

Monadクラスを考えてみましょう。

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

mはclassで明示的にparametrizeされているとしても、他にもa, bと出てきます。Monadはこれらの型の値に触れません。

それを確認するために簡単なプログラムを走らせてみます。

parametricity :: (Monad m, Num a) => a -> m a
parametricity n = do
    let
        ret i x = trace ("action : " ++ show i) $ return x

    n'   <- ret 1 $ trace "value : succ" (n + 1)
    n''  <- ret 2 $ trace "value : twice" (2 * n')
    n''' <- ret 3 $ trace "value : minus3" (n'' - 3)

    return n'''

まずretはreturnにtraceを仕込んだものです。アクションが評価される時に出力します。
この関数は任意のモナドに対して動かすことが出来ます。なので色んなモナドで実際に走らせてみましょう。

main :: IO ()
main = do

    putStrLn "------ IO --------------"
    x <- parametricity 8
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Lazy State ------"
    x <- return $ L.evalState (parametricity 8) 5
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Strict State ----"
    x <- return $ S.evalState (parametricity 8) 5
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Lazy Writer -------"
    (x, _ :: Sum Int) <- return $ W.runWriter (parametricity 8)
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Strict Writer -----"
    (x, _ :: Sum Int) <- return $ SW.runWriter (parametricity 8)
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Reader ------------"
    x <- return $ R.runReader (parametricity 8) 5
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Cont --------------"
    x <- return $ C.runCont (parametricity 8) id
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Lazy StateT IO ----"
    (x, _) <- L.runStateT (parametricity 8) 5
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Strict StateT IO --"
    (x, _) <- S.runStateT (parametricity 8) 5
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Lazy WriterT IO ---"
    (x, _) :: (Int, Sum Int) <- W.runWriterT (parametricity 8)
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ Strict Writer -----"
    (x, _ :: Sum Int) <- return $ SW.runWriter (parametricity 8)
    putStrLn " * Eval "
    x `seq` return ()

    putStrLn "------ ContT IO ----------"
    x <- C.runContT (parametricity 8) return
    putStrLn " * Eval "
    x `seq` return ()

    return ()

色んなモナドでparametricityを実行し、その「アクションの返り値」のサンクを明示的にseqで潰すというプログラムです。

長くなりますが、結果を全て載せます。

------ IO --------------
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ
------ Lazy State ------
 * Eval
action : 3
value : minus3
action : 2
value : twice
action : 1
value : succ
------ Strict State ----
 * Eval
action : 1
action : 2
action : 3
value : minus3
value : twice
value : succ
------ Lazy Writer -------
 * Eval
action : 3
value : minus3
action : 2
value : twice
action : 1
value : succ
------ Strict Writer -----
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ
------ Reader ------------
 * Eval
action : 3
value : minus3
action : 2
value : twice
action : 1
value : succ
------ Cont --------------
 * Eval
action : 1
action : 2
action : 3
value : minus3
value : twice
value : succ
------ Lazy StateT IO ----
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ
------ Strict StateT IO --
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ
------ Lazy WriterT IO ---
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ
------ Strict Writer IO -----
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ
------ ContT IO ----------
action : 1
action : 2
action : 3
 * Eval
value : minus3
value : twice
value : succ

全てのvalueの評価が、* Evalの後に来ていることに着目してください。それはつまり、(>>=)が「アクションの返り値」の評価をしていないことを意味しています。
また、モナド変換子を用いて下にIOを置いた場合、全てのアクションは* Evalより前に実行され、IOモナドと同じような挙動となっています。IOが絡んでいないモナドは、評価時にactionとvalueが混ざったりしています。

モナドの評価順序まとめ

まとめます。

モナドの評価は、IOか純粋かで分けて考えるといいでしょう。

  • IOが絡んだモナドでは、アクションは並べたら並べた順番で実行されます。
  • アクションとアクションをつなぐ(>>=)が「アクションの返り値」を評価することは基本ありません。

誤解のないように付け加えると、あるアクションが「他のアクションの返り値」を引数にとり、結果として評価することは普通にあります。

o :: IO ()
o = do
    x <- action1
    action2 x

action1の返り値xをaction2が引数にとり、action2の内部でxが評価される、というシナリオです。

以上のことから、IO関連のモナドは、評価順序に関して床下(>>=)を見なくても判断出来るということが言えるでしょう。

純粋なモナドでは、アクション順序が決まっていないサンクの塊になるため、その評価順序は色々の様です。

おわりに

これで遅延評価の動作モデルの確認は終わりです。
モナドに関して面倒かと思ってましたが意外とわかりやすい結果が出てきて安心しました。

ようやくスペースリークの話に入れますね！！

  1. これは正しい言及でしょうか？ ↩

18
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
18
13