状態モナド、乱数列とモナドコード
https://stackoverflow.com/questions/1956518
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は状態モナドを理解しようとしています。この目的で、線形合同生成器を使用して一連の乱数を生成するモナド コードを書きたかったのです (おそらく良くありませんが、私の目的は状態モナドを学習することだけであり、学習することではありません)優れた RNG ライブラリを構築します)。
ジェネレーターはこれだけです（ Bool簡単にするために s):
type Seed = Int
random :: Seed -> (Bool, Seed)
random seed = let (a, c, m) = (1664525, 1013904223, 2^32) -- some params for the LCG
seed' = (a*seed + c) `mod` m
in (even seed', seed') -- return True/False if seed' is even/odd
数値については心配しないでください。これは、（数値レシピに従って）次の疑似ランダム シーケンスを生成するシードの単なる更新ルールです。 Ints.さて、乱数を順番に生成したい場合は、次のようにします。
rand3Bools :: Seed -> ([Bool], Seed)
rand3Bools seed0 = let (b1, seed1) = random seed0
(b2, seed2) = random seed1
(b3, seed3) = random seed2
in ([b1,b2,b3], seed3)
さて、State モナドを使用することで、この定型文を回避できます。
import Control.Monad.State
data Random {seed :: Seed, value :: Bool}
nextVal = do
Random seed val <- get
let seed' = updateSeed seed
val' = even seed'
put (Random seed' val')
return val'
updateSeed seed = let (a,b,m) = (1664525, 1013904223, 2^32) in (a*seed + c) `mod` m
そして最後に：
getNRandSt n = replicateM n nextVal
getNRand :: Int -> Seed -> [Bool]
getNRand n seed = evalState (getNRandStates n) (Random seed True)
OK、これはうまく機能し、n 個の擬似乱数のリストが得られます。 Bool与えられたシードごとに s を指定します。しかし...
私が何をしたかを読むことができます（主に次の例に基づいています）。 http://www.haskell.org/pipermail/beginners/2008- September/000275.html ) 他のことを行うためにそれを複製します。しかし、do 記法やモナド関数 (replicateM など) の背後で実際に何が起こっているのか理解できないと思います。
誰かこの疑問について私を助けてくれませんか?
1 - nextVal 関数の機能を理解するために desugar しようとしましたが、できませんでした。現在の状態を抽出して更新し、その状態を次の計算に渡していると推測できますが、これは単にこの do-sugar を英語であるかのように読んだことに基づいています。
この関数を実際に元の >>= に脱糖し、段階的に関数を返すにはどうすればよいでしょうか?
2 - 正確に何が起こっているのか理解できませんでした put そして get 関数はそうします。状態を「梱包」したり「開梱」したりしているのだと推測できます。しかし、do-sugar の背後にある仕組みは私にはまだわかりません。
このコードに関するその他の一般的なコメントは大歓迎です。Haskell では、動作するコードを作成し、期待どおりの動作を実行できるが、命令型プログラムで慣れているように「評価に従う」ことができないと時々思いました。
解決
は最初に、状態は、2つのタイプのパラメータがあります。含まれる状態データのタイプと計算のの最終結果の種類。ここでは、それらの型の変数として、それぞれstateDataとresultを使用します。あなたはそれについて考える場合、これは理にかなっています。状態ベースの計算の定義特性は、出力を生成しながら、状態を変更することである。
明らか以下で型コンストラクタはそうのような状態から修飾状態及び結果を関数をとることです
newtype State stateData result = State (stateData -> (result, stateData))
だから、モナドは「国家」と呼ばれながら、で包まれた実際の値がモナドはの状態ベースの計算のではなく、含まれている状態の実際の値ます。
のことですは心の中で、我々は機能runStateはStateモナドで計算を実行するために使用されることを知って驚いべきではないことを保つことは、実際に包まれた関数自体のアクセッサ以外の何ものでもありませんし、このように定義することができます
runState (State f) = f
だから、それは何を意味するのでしょうか？のは一瞬のために国家がモナドで、ちょうど基本的な種類を見ているという事実を無視してみましょう。まず、（実際の状態で何もしない）、この関数を考えます：
len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)
stateDataを持っている必要がありますので、、、我々はここでIntタイプがresultであることを確認することができ、かつBoolタイプがInt -> (Bool, Int)です。さて、len2Stateのステートレスバージョンを想像して - 明らかに、それはタイプString -> Boolを持っているでしょう。それでは、どのようにその国に収まるラッパー？
まあ、明らかに、変換された関数は2番目のパラメータの状態値を表すIntを取る必要があります。また、状態値、別のIntを返す必要があります。経由でそのint型の権利を渡す - 私たちは実際にこの機能での状態で何もしていないので、ちょうど明白なことをやってみましょう。ここ州レスバージョンの用語で定義された状態状関数は、ですます：
len2 :: String -> Bool
len2 s = ((length s) == 2)
len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)
convert :: Bool -> (Int -> (Bool, Int))
convert r d = (r, d)
len2 s = ((length s) == 2)
len2State :: String -> (Int -> (Bool, Int))
len2State s = convert (len2 s)
私たちは状態を変更する関数をしたい場合は？我々は通過状態を渡すことを書いたので、明らかに私たちは、convertを持つものを構築することはできません。のは、単純な、それを維持し、新しい値で状態を上書きする関数を書いてみましょう。それは一種のタイプの何が必要でしょうか？それはどのような私たちの国家ラッパーのニーズだからそれは、新しい状態値のためIntが必要になります、そしてもちろん機能stateData -> (result, stateData)を返却する必要があります。ここで私たちの結果はちょうどresult、Haskellでは「無価値」を表していないゼロ要素のタプルになりますので、状態値を上書きすると、本当に、国家の計算外の賢明な()値を持っていません。
overwriteState :: Int -> (Int -> ((), Int))
overwriteState newState _ = ((), newState)
簡単でした！さて、実際にしてみましょう。の何かをするのその状態データを持ちます。上記から、より賢明なものにしましょう書き換えlen2State：。我々は現在の状態値に文字列の長さを比較します。
lenState :: String -> (Int -> (Bool, Int))
lenState s i = ((length s) == i, i)
私たちは、コンバータおよび国家レス機能にこれを一般化することはできますか？ないほど簡単に。私たちのlen関数は、引数として状態を取る必要がありますが、我々はそれが状態「について知る」必要はありません。確かに、ぎこちないです。しかし、私たちは私たちのために、ハンドルのすべてという迅速なヘルパー関数を書くことができます：我々はそれにそのニーズ機能をあげます状態値を使用するには、それが中に値を渡し、その後、賢明lenなしを残さない状態状の関数にすべてのバックアップをパッケージ化します。
useState :: (Int -> Bool) -> Int -> (Bool, Int)
useState f d = (f d, d)
len :: String -> Int -> Bool
len s i = (length s) == i
lenState :: String -> (Int -> (Bool, Int))
lenState s = useState (len s)
さて、トリッキーな部分 - 私たちは、これらの機能一緒に文字列にしたい場合は？我々は再び文字列をチェックし、最終的にどちらかのチェックはしなかった場合はtrueを返し、その後、結果がfalseの場合、状態値を倍増、その後、文字列にlenStateを使いたいとしましょう。私たちは、このタスクのために必要なすべての部品を持っていますが、それをすべて書き出すことは苦痛だろう。私たちは、それぞれの復帰状態のような機能に、一緒に自動的にチェーンの二つの機能の関数を作ることはできますか？確実なこと！最初の関数によって返された状態関数、および引数として前に関数のresultの型を取る機能：我々は、念のそれは引数として二つのことを取るようにする必要があります。レッツは、それが判明どのように参照してください。
chainStates :: (Int -> (result1, Int)) -> (result1 -> (Int -> (result2, Int))) -> (Int -> (result2, Int))
chainStates prev f d = let (r, d') = prev d
in f r d'
これはすべてその結果、変性状態データに第2の機能を適用し、いくつかの状態データに第1の状態関数を適用して行っています。シンプルな、右？
さて、興味深い部分：chainStatesとconvertの間に、我々はほとんど州立対応機能にステートレス機能の任意の組み合わせをオンにすることができるはず！私たちが今必要とする唯一のものは、その結果としての状態データは、そうchainStatesは、我々は彼らを引っ張っているのトリックについては何も知らない関数に沿って、それを渡すことができることを返すことuseStateを置き換えるものです。また、私たちは前の関数からの結果を受け入れ、それらを一時的に名前を付けるためにラムダを使用します。さて、これを実現してみましょう。
extractState :: Int -> (Int, Int)
extractState d = (d, d)
chained :: String -> (Int -> (Bool, Int))
chained str = chainStates extractState $ \state1 ->
let check1 = (len str state1) in
chainStates (overwriteState (
if check1
then state1
else state1 * 2)) $ \ _ ->
chainStates extractState $ \state2 ->
let check2 = (len str state2) in
convert (check1 || check2)
そして、それを試してみます：
> chained "abcd" 2
(True, 4)
> chained "abcd" 3
(False, 6)
> chained "abcd" 4
(True, 4)
> chained "abcdef" 5
(False, 10)
runState (State s) = s
return r = State (convert r)
(>>=) s f = State (\d -> let (r, d') = (runState s) d in
runState (f r) d')
get = State extractState
put d = State (overwriteState d)
注。
：だから、物事をラップするために、我々はの本当のの状態を使用して、最終的な例を書き換えることができますchained str = get >>= \state1 ->
let check1 = (len str state1) in
put (if check1
then state1 else state1 * 2) >>= \ _ ->
get >>= \state2 ->
let check2 = (len str state2) in
return (check1 || check2)
あるいは、全ての等価DO表記でアップ砂糖漬けます：
chained str = do
state1 <- get
let check1 = len str state1
_ <- put (if check1 then state1 else state1 * 2)
state2 <- get
let check2 = (len str state2)
return (check1 || check2)
他のヒント
それは状態モナドでvalを保存する必要がないため、まず第一に、あなたの例では、過度に複雑になっています。唯一のシードは、永続的な状態です。第二には、私の代わりに標準状態モナドを使って、あなたが自分のタイプで、Stateモナドとその操作を自分のすべてを再実装する場合は、より良い運を持っていると思います。私はあなたがより多くのこの方法を学ぶことになると思います。ここでは、始めるための宣言のカップルがあります：
data MyState s a = MyState (s -> (s, b))
get :: Mystate s s
put :: s -> Mystate s ()
次に、あなたがあなた自身の接続詞を書くことができます：
unit :: a -> Mystate s a
bind :: Mystate s a -> (a -> Mystate s b) -> Mystate s b
最後に
data Seed = Seed Int
nextVal :: Mystate Seed Bool
doはかなり洗練されています。
しかし、脱糖は、線順次機械的手順です。私が作ることができる限りで、あなたのコードは、（バックI体質に合わないオリジナルタイプとコード、に行く）このようdesugarする必要があります：
nextVal = get >>= \ Random seed val ->
let seed' = updateSeed seed
val' = even seed'
in put (Random seed' val') >>= \ _ -> return val'
の入れ子構造が少し明確にするために、私はインデントで大きな自由を撮影しました。
素晴らしい回答がいくつかありました。State モナドを扱うときに私がしていることは、頭の中で置き換えることです。 State s a と s -> (s,a) （結局のところ、それが本当のことなのです）。
次に、次のようなバインドのタイプを取得します。
(>>=) :: (s -> (s,a)) ->
(a -> s -> (s,b)) ->
(s -> (s,b))
そして、bind は、次のような特殊な種類の関数合成演算子にすぎないことがわかります。 (.)
状態モナドに関するブログ/チュートリアルを書きました ここ. 。おそらく特に良いものではありませんが、書くことで物事を少しよく理解するのに役立ちました。
