17

私はStateモナドで遊んでいましたが、この単純なコードでスタックオーバーフローの原因がわかりません。

import Control.Monad.State.Lazy

tick :: State Int Int
tick = do n <- get
         put $! (n+1)
         return n

million :: Int
million = snd $ runState (mapM_ (const tick) [1..1000000]) 0

main = print million

この コードで問題の原因を知りたいだけです。タスク自体は重要ではありません。

4

1 に答える 1

41

問題は、Control.Monad.State.Lazy（>> =）が非常に怠惰であるため、（$！）でさえ役に立たないことです。
Control.Monad.State.Strictを試してください。これは、（$！）に到達するはずです。

怠惰な状態のモナドの（>> =）は、（値、状態）のペアをまったく調べないため、最後に到達する前に評価を行う唯一の方法は、ペアfをm >>= f分解することです。これはここでは発生しないため、runStateが最終的に結果を求めている場合、スタックには大きすぎる巨大なサンクが発生します。

さて、私は食べました、今私は詳しく説明することができます。怠惰なモナドの古い（mtl-1.x）定義を使用State sさせてください。内側のモナドがないと、そこが少し見やすくなります。新しい（mtl-2.x）定義type State s = StateT s Identityは同じように動作し、書き込みと読み取りが増えます。（>> =）の定義は

m >>= k  = State $ \s -> let
    (a, s') = runState m s
    in runState (k a) s'

さて、letバインディングは怠惰なので、これは

m >>= k = State $ \s -> let
    blob = runState m s
    in runState (k $ fst blob) (snd blob)

より読みやすいだけです。したがって、（>> =）を使用すると、ブロブは完全に未評価になります。評価は、続行する方法を決定するkために検査する必要がある場合、または検査する必要がある場合にのみ必要です。fst blobk asnd blob

ではreplicateM r tick、計算は（>>）で連鎖されているため、kin（>> =）の定義はconst tickです。定数関数として、それは間違いなくその引数を検査する必要はありません。だからtick >> tick_

State $ \s -> 
    let blob1 = (\n -> let n' = n+1 in seq n' ((),n')) s
        blob2 = (\m -> let m' = m+1 in seq m' ((),m')) (snd blob1)
    in blob2

評価が必要になるseqまで触れられませんblobN。しかし、それを最も外側のコンストラクター（ペアコンストラクター）で評価する必要があると(,)、seqをトリガーするのに十分であり、それがここでの完全な評価につながります。さて、では、に達した後のmillion決勝まで、何も評価を必要としません。その時までに、百万層のサンクが作られました。そのサンクを評価するには、初期状態に達するまでスタックに多くをプッシュする必要があり、スタックがそれらを保持するのに十分な大きさである場合、それらはポップされて適用されます。つまり、3つのトラバーサル、1。サンクの構築、2。サンクからのレイヤーの剥離とスタックへのプッシュ、3。スタックの消費になります。sndrunStatelet m' = m+1 in seq m' ((),m')

Control.Monad.State.Strictの（>> =）は、各バインドでsを強制するのに十分厳密であるためseq、トラバーサルは1つだけで、（重要な）サンクは作成されず、計算は一定のスペースで実行されます。定義は

m >>= k = State $ \s ->
    case runState m s of
      (a, s') -> runState (k a) s'

重要な違いは、式のパターンマッチングcaseが厳密であるということです。ここでは、blobのパターンと照合するために、最も外側のコンストラクターに対して評価する必要がありcaseます。本質的な部分
でm = tick = State (\m -> let m' = m+1 in seq m' ((),m'))

case let s' = s+1 in seq s' ((),s') of
    (a, s'') -> runState (k a) s''

パターンマッチでは、((), s')[（、）コンストラクターへの]の評価が必要です。seqこれは、の評価に関連付けられているためs' = s+1、すべてがバインドごとに完全に評価され、サンクやスタックはありません。

ただし、それでも注意する必要があります。この場合、seq（($!)または）が含まれるタイプの構造が浅いため、評価は。の適用に追いつきました(>>)。一般に、より深い構造化タイプを使用する場合、および/またはseqsを使用しない場合、CMSStrictはスタックオーバーフローにつながる可能性のある大きなサンクも作成します。サンクは、そのような状況でCMSLazyによって生成されたものよりも少し単純で、絡み合いが少なくなっています。

一方、CMSLazyの怠惰により、CMSStrictでは不可能な他の計算が可能になります。たとえば、CMSLazyは、数少ないモナドの1つを提供します。

take 100 <$> mapM_ something [1 .. ]

終了します。[ただし、その状態は使用できなくなることに注意してください。使用する前に、無限のリスト全体を移動する必要があります。したがって、そのようなことを行う場合は、状態に依存する計算を再開する前にput、新しい状態にする必要があります。]

于 2011-11-03T17:01:58.750 に答える