State Monadを単純に使用すると、スタックオーバーフローが発生するのはなぜですか？

Question

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

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 

注 私は、コードのこの部分で問題を引き起こしているかを知りたいと思い、タスク自体は、それ自体重要ではありません。

Answer 1

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

遅延状態のモナドの（>> =）は（値、状態）のペアですべて見ないので、最後に達する前に何らかの評価を行う唯一の方法は、fにm >>= fペアを解体する。それはここでは起こらないので、あなたは巨大なサンクを得ます。これは、runStateが最終的に結果を望むときにスタックにとって大きすぎます。

さて、私は食べました、今私は精緻化することができます。怠惰なState sモナドの古い（mtl-1.x）定義を使用してみましょう。内側のモナドがなければ、少し見やすくなります。新しい（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 blobを検査する必要がある場合、またはk aがsnd blobを検査する必要がある場合のみ、評価が必要です。

replicateM r tickでは、計算は（>>）で連結されているため、（>> =）の定義内のkは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 

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

Control.Monad.State.Strictの（>> =）は、各バインドで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' = s+1の評価に結びついているseqにより、[（、）コンストラクタへ] ((), s')の評価が必要となり、すべてが完全に評価されますそれぞれが縛られ、サンクはなく、スタックされません。

ただし、まだ注意する必要があります。この場合、seq（resp。($!)）および関連するタイプの浅い構造により、評価は(>>)のアプリケーションで維持されました。一般に、より深い構造化タイプおよび/またはseqがない場合、C.M.S.Strictはスタックオーバーフローを招く大きなサンクを構築します。これらの状況では、サンクスはC.M.S.Lazyによって生成されたサンクよりも、少しシンプルでエンゲージメントが少ないです。他方、C.M.S.Lazyの怠惰はC.M.S.Strictでは不可能な他の計算を可能にする。例えば、C.M.S.Lazyは、非常に少数のモナドの1つを提供し、

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

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