Haskellのランダムとリストを含むモナド

Question

私は私の試験のために学んでいるので、機能的プログラミング、私はまだ実際にしようとしています Monads。あなた自身を定義するよりも良い方法は何ですか？ 1に

newtype ST a = ST (State -> ([a], State)) 
type State = StdGen 

基本的にはリストモナドとモナドランダム：私はこれを定義しました。 このモナドでは、ランダムな関数とリストを扱うことができます。 return関数を定義することができたので今や問題が発生しますが、>>=ではそのようなことはあまりありません。

instance Monad ST where 
    return a = ST $ \g -> ([a], g) 
    -- M a -> (a -> M b) -> M b 
    st >>= f = ST $ \s -> 
       let (x,s') = st s 
       in (f x) s' 

コードがThis paper p.218

任意の説明からインスピレーションを得ていますか？

Answer 1

すべてのタイプを把握しておきましょう（私はトリッキーなコードを書くときにこれを自分で行います）。最初に、あなたのSTタイプ用のアクセサーを追加しましょう。これにより作業が楽になります。

newtype ST a = ST { runST :: State -> ([a], State) } 

今ではrunST :: ST a -> State -> ([a], State)です。モナドコードを定義するときは、すぐにrunSTの値をすべてSTの値に適用したいので、実際にどのタイプのものを使用しているのか知っています。

st >>= f = ST $ \s -> 
    -- runST st :: State -> ([a], State) 
    -- f   :: a -> ST b 
    -- runST . f :: a -> State -> ([b], State) 
    -- s   :: State 
    let (as, s') = runST st s in -- I renamed x to as for readability 
    -- as  :: [a] 
    -- s'  :: State 

ここでは([b], State)が必要です。 fを使用してbを取得できます。

-- map (\a -> runST (f a) s) as :: [([b], State)] 

は多分私達はこれで動作することができます：私たちは、それでは、マッピング

-- map (runST . f) as :: [State -> ([b], State)] 

うーんを試してみましょうsのaのリストを持って、それはとても有用ではないですが、我々はあまりにも、入ってくるしている状態を適用してみましょう。 bのリストとその他のものがあります。のは、（「結果」のために）このrsに名前を付けてみましょう：

let rs = map (\a -> runST (f a) s) as in 

今、私たちは、すべての結果のBSを連結してbのリストを取得することができます。

let bs = concat (map fst rs) in -- bs :: [b] 

おそらく、我々は返すようにしたいものをするように、 。今どのState私たちはそれと一緒に行きたいですか？私たちにはさまざまな選択肢がたくさんあるので問題があります。リスト内の最後のもの、または最初のものを選択しますか？リストが空の場合は、Stateが返ってくるかもしれません。これは任意の選択です。私の物理学者の教授は、「今、選択する必要があります。間違ったものを作る "。これは関数型プログラミングで非常に真実です。このような任意の選択をしなければならないときはいつも、あなたはうんざりしているでしょう。は、選択肢のリストを生成しますそれぞれの

我々はバックステップを取ると、直感的な意味を考える場合は、ST a計算は状態をとり、将来の計算に使用する新しい状態に選択肢のリストを返し、新しい状態。 concatを使用してすべてのリストを結合することはできますが、すべての状態をまとめて1つにまとめる方法はありません。ランダムなAPIを使用すると、これはありません（bitxorをすべての状態でまとめると想像できます）。

州を結合する方法なしでは、モナドバインドはデータの大部分を忘れる必要があります。それは法律に従わないというまともな兆候です（モナドでは複雑ですが複雑です法律を証明すること）。そして、私が知る限り、このタイプのモナドはありません。

ありこのタイプとモナドです：

newtype ST' a = ST' { runST' :: State -> [(a, State)] } 

そして、それはStateT State []と同等です。現在、計算の各枝はそれ自身のランダムな状態を持っているので、多くの状態を1つに結合する必要はありません。あなたは、このモナドを定義したことをよりうまくやっているかもしれません。あなたが知っているすべてのタイプを書き留めて、あなたがタイプ指向の方法で必要なものに到達しようとします。情報を "忘れない"ようにして、出力を構築する際に各入力を正確に1回使用するように努めます。

申し訳ありませんが、この投稿は少し漠然としていました。私はモナドを定義する際に直感的な原則をたくさん使用していますが、私はそれらを共有しようと考えていました。覚えておいても、タイプチェックの定義を得るには不十分です（ただし、そこには多くの方法があります）。法律をチェックしてください。そうしないと、doという表記法などを使用すると奇妙なことが起こります。

Answer 2

luqui's lead後、我々は（テストしていません）

st >>= f = ST (g . runST st) 
    -- runST st :: State -> ([a], State) 
    -- f   :: a -> ST b 
    -- runST . f :: a -> State -> ([b], State) 

    where 
     g (a:as,s) = let (bs, s2) = (runST . f) a s 
          (rs, sn) = g (as, s2) 
        in (bs ++ rs, sn) 
     g ([], s) = ([], s) 

を取得します。