Monadic Fibonacciを理解する

Question

私はhaskellと学習用のモナドを学んでいます。私は、しかし、私は（Haskellのウィキから取られた）次のコードを理解することはできませんよ、見て、様々なチュートリアルを読んで、Stateモナドのためのいくつかの簡単な例をコード化されました：

import Control.Monad.State 
fib n = flip evalState (0,1) $ do 
    forM [0..(n-1)] $ \_ -> do 
    (a,b) <- get 
    put (b,a+b) 
    (a,b) <- get 
    return a 

私の質問は以下に集約します：

1. 内側のdoの最初の文の内部には何があるのですか。すなわち、(a,b)<-getの結果は何ですか？具体的な例として、aとbの値はどうなりますか。
2. なぜあなたはここで州のモナドを使いたいのですか？

Answer 1

この例では、状態は、シーケンスで生成された前の2つの数値を含むペアです。これは、(0, 1)が最初にevalStateに提供されています。

getのタイプは、内側doブロックにそうMonadState s m => m sある

(a, b) <- get 

状態ペアを取り出し、第1および第2の要素にaとbに結合します。状態は、次にputで更新されます。

状態は、したがって、次のようになります

(0, 1), (1, 1), (1, 2), (3, 2), (3, 5), ... 

外側

(a, b) <- get 
return a 

は最終状態値をアンパックし、最初の要素を返します。

Answer 2

まず、フィボナッチアルゴリズムが使用されていることを確認します。考え方はタプル(0, 1)で始まり、次は(1, 0 + 1)、次は(1, 1 + 1)、(2, 2 + 1)、(3, 3 + 2)などとなります。一般に、ステップは\(a, b) -> (b, a + b)です。これらのタプルにフィボナッチ数があることがわかります。内部の最初のステートメントの内側に起こっている

ない、すなわち何 は（a、b）は<はにつながる。-GETのでしょうか？

ハスケルにはステートメントがなく、式だけがあります。

y <- xは完全な表現ではありません。これはx >>= \y ->に似ています。

y <- x 
m 

完全表現はx >>= \y -> mと等価です。 y <- nの形式ではないnの行は、_ <- nと等価です（let行を除き、多分私は忘れています）。

これを使用して、私たちはdesugar do-notationを使用できます。

fib n = 
    flip evalState (0, 1) 
    (forM 
     [0..(n-1)] 
     (\_ -> get >>= (\(a, b) -> put (b, a + b))) 
    >>= (\_ -> get >>= (\(a, b) -> return a))) 
) 

は今、それはちょうどように理解>>=、return、get、put、およびについてです。

実際には、状態はタイプs -> (s, a)の単なる機能です。それらは初期状態をとり、次の状態に他の値を加えたものを生成する。

m >>= n a.k.a "bind"はタイプMonad m => m a -> (a -> m b) -> m bです。私たちのモナドがState sであればその後、これは同じです：

​​

mによって返さaはnに渡す必要があります。他に何があると思いますか？州も同様に進むと予想されますので、mで返された州はnにも渡されなければなりません。関数m >>= nは、nが返す状態と値を返す必要があります。私たちは、その後、バインドを実装する方法を知っている：そしてreturn :: a -> s -> (s, a)と同等です

m >>= n = uncurry (flip n) . m 

return :: Monad m => a -> m a：

return = flip (,) 

get :: State s sはget :: s -> (s, s)と同等です：

get = join (,) 

put :: s -> State s()かput :: s -> s -> (s,())：

put s _ = (s,()) 

evalState :: s -> State s a -> aまたはevalState :: s -> (s -> (s, a)) -> a：

evalState s f = snd (f s) 

あなたはすべての定義を拡大し、一例で起こっている正確に何を見ることができます。しかし、直感だけで十分です。

forM 
    [0..(n-1)] 
    (\_ -> get >>= (\(a, b) -> put (b, a + b))) 

我々は最初の引数がドロップされるのでn - 1に番号0を持つ気にしないでください。 getが現在の状態を取得すると、putは新しい状態を書き込みます。我々はこれを行うn回。

累積値（単位）は気にしないので、最初のパラメータは削除されます。次に、現在の状態を取得し、ペアの最初の要素だけを投影します。これが私たちが探している最終的な答えです。

flip evalState (0, 1) … 

最後に、最初の状態(0, 1)から実行します。

この実装にはいくつかのクリーンアップがあります。まず、我々は範囲[0..(n-1)]に気にしない、我々はちょうどアクションn回を繰り返す気にする。これを行うために、より直接的な方法は以下の通りです：

replicateM n (get >>= \(a, b) -> put (b, a + b)) 

結果は未使用である単位のリストであるので、より効率的なバージョンは次のとおりです。

replicateM_ n (get >>= \(a, b) -> put (b, a + b)) 

のための機能がすでにありますgetの後にputのmodifyと命名された共通パターン、これは\f -> get >>= put . fと定義される。したがって：

replicateM_ n (modify (\(a, b) -> (b, a + b))) 

が続いて部分がある：

>>= (\_ -> get >>= (\(a, b) -> return a))) 

我々は>>を使用することができ、以前の結果を気にしないでくださいいつでも。

>> get >>= (\(a, b) -> return a)) 

これは、次のとおりです。

>> get >>= return . fst 

m >>= return . fが簡素化fmap f mへ：今

>> fmap fst get 

我々持ち、合計：

fib n = 
    evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> fmap fst get 
) 
    (0, 1) 

我々はまた、比較のために、使用する場合があります：

私は愚かだから、その後

fib n = 
    fst 
    (evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> get 
    ) 
    (0, 1) 
) 

そして：

fib = 
    fst 
    . flip evalState (0, 1) 
    . (>> get) 
    . flip replicateM_ (modify (snd &&& uncurry (+))) 

あなたはこっち状態モナドを使用したいと思うのはなぜ？

あなたはそうではありません。状態値のみを使用するため、これは明らかです。他の値は常に単位であり、破棄されます。換言すれば、冒頭にn（すなわち、どのフィボナッチ数を見つけるか）が必要なだけで、累積タプルのみが必要となる。

時々、h . g . fのような文字列があると思うかもしれませんが、ただ1つではなく2つの引数を送信したいと思うことがあります。つまり、Stateが適用可能な場合があります。

一部の関数を読み込んでいくつかの状態（2番目の引数）を書き込むか、またはその両方を行う場合、Stateが請求書に適合します。読者だけがいる場合はReaderを使用し、ライターのみがある場合はWriterを使用してください。

この例を変更して、State Monadをより使いやすくすることができます。私はタプルを消滅させるでしょう！だから、

fib = 
    flip evalState 0 
    . foldr (=<<) (return 1) 
    . flip replicate (\x -> get >>= \y -> put x $> x + y) 

Answer 3

ドキュメントの状態：get :: m s -- Return the state from the internals of the monad（hereを参照してください）。

しかし、私は国家モナドの周りに頭を抱えようとしたとき、これは私を大きく助けなかったことをよく覚えています。

ghciで:iと:tを試してみて、別のサブ式を試してみることをおすすめします。ちょうどそれのための感じを得るために。このようなビット：

import Control.Monad.State.Lazy 

runState (get) 0 
runState (get >>= \x -> put (x+1)) 0 
:t return 1 :: State Int Int 
runState (return 1) 0 
runState (return 1 >>= \x -> (get >>= \y -> return (x+y))) 0 

-- Keeping a pair of (predecessor/current) in the state: 
let f = (get >>= (\(a,b) -> put (b,a+b))) :: State (Int, Int)() 
runState (f >> f >> f >> f >> f >> f) (0,1) 

-- only keeping the predecessor in the state: 
let f x = (get >>= (\y -> put x >> return (x+y))) :: State Int Int 
runState (return 1 >>= f >>= f >>= f >>= f >>= f >>= f) 0 

はまたmodify、runState、evalState、execStateで遊びます。