状态 Monad、随机数序列和 Monad 代码
https://stackoverflow.com/questions/1956518
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在尝试掌握 State Monad，为此我想编写一个 Monadic 代码，该代码将使用线性同余生成器生成随机数序列（可能不好，但我的目的只是学习 State Monad，而不是建立一个好的RNG库）。
生成器就是这样（我想生成一系列 Bools 为简单起见）：
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 Monad 来避免这个样板：
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)
好的，这工作正常并给我一个 n 伪随机的列表 Bools 对于每个给定的种子。但...
我可以阅读我所做的事情（主要基于这个例子： http://www.haskell.org/pipermail/beginners/2008-September/000275.html ）并复制它来做其他事情。但我认为我无法理解 do 表示法和单子函数（如replicateM）背后到底发生了什么。
谁能帮我解决一些疑虑吗？
1 - 我尝试对 nextVal 函数进行脱糖以了解它的作用，但我做不到。我可以猜测它会提取当前状态，更新它，然后将状态传递到下一个计算，但这只是基于阅读这个 do-sugar，就好像它是英语一样。
我如何真正将此函数脱糖为原始 >>= 并逐步返回函数？
2 - 我无法理解到底是什么 put 和 get 函数做。我可以猜测他们“打包”和“解包”状态。但双糖背后的机制对我来说仍然难以捉摸。
好吧，非常欢迎有关此代码的任何其他一般性评论。有时我对 Haskell 感到很满意，因为我可以创建一个可以运行的代码，并执行我期望它执行的操作，但我不能像我习惯于使用命令式程序那样“遵循评估”。
解决方案
在国家单子看上去确实有种混乱起初;让我们做诺曼拉姆齐建议，并通过如何从头开始实行走。警告，这是相当漫长！
首先，状态有两种类型的参数：收纳状态的数据的类型和的计算的最终结果类型。我们将在这里分别用stateData和result类型变量他们。这是有道理的，如果你想想看;基于状态的计算的定义特征是其修饰的状态下，同时产生的输出。
不太明显的是，类型构造函数采用一个功能从一个状态到修改状态和结果，如下所示：
newtype State stateData result = State (stateData -> (result, stateData))
因此，尽管单子被称为“国家”，由单子包裹的实际值是的一个基于状态的计算，而不是载状态的实际值。
牢记这一点，我们不应该感到惊讶地发现，用在国家单子执行运算功能runState实际上无非是为包装的函数本身的访问更多，可能这样定义：
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。所以，你将如何去转换等功能于一体返回适合到一个国家包装的值？
可是，很明显，转换函数将需要采取的第二参数，表示所述状态值的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)
现在，棘手的问题 - 如果我们想串这些功能在一起呢？比方说，我们要使用lenState在一根绳子上，然后双击状态值，如果结果为假，然后再检查字符串，最后如果任一检查没有返回true。我们有我们需要为这个任务的所有部件，但是写这一切将是一个痛苦。我们可以做一个功能，可自动链两个函数，每个国家收益类功能整合在一起？当然可以！我们只需要确保它需要作为参数两件事情：第一函数返回的国家功能，而这需要事先功能的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'
所有这些都做的是将所述第一状态的功能于一些状态数据，则应用所述第二函数到结果和修改后的状态数据。简单，正确？
现在，有趣的部分：chainStates和convert之间，我们应该几乎能够把国家少功能任意组合成一个启用状态的功能！我们现在唯一需要的是useState返回状态数据作为其结果，使chainStates可以沿着那些不知道我们对他们拉的把戏什么的功能通过它的替代品。此外，我们将使用lambda表达式接受从以前的函数的结果，并给他们临时的名字。好吧，让我们做到这一点：
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)
请注意>> =几乎是相同的chainStates，但有使用chainStates来定义它没有好办法。因此，包装的东西，我们可以使用重写最后一个例子中的真正的状态：
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)
或者，所有蜜饯了等效做符号：
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存储在状态单子;只有种子的持久状态。其次，我认为你将有更好的运气，如果不是使用标准状态下单子，你重新实现所有国家单子及其运作自己，用自己的类型。我想你会这种方式了解更多信息。这里有一对夫妇的声明，以帮助您入门：
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符号是相当复杂的。
但是，脱糖是一个线，在一次一个机械过程。尽可能靠近我可以做出来，你的代码应该desugar像这样（要回你原来的类型和代码，这点我不同意）：
nextVal = get >>= \ Random seed val ->
let seed' = updateSeed seed
val' = even seed'
in put (Random seed' val') >>= \ _ -> return val'
为了使嵌套结构更清楚一点，我已经采取了重大自由与缩进。
您收到了一些很好的回复。我在使用 State monad 时所做的事情是在我的脑海中替换 State s a 和 s -> (s,a) （毕竟，事实就是如此）。
然后你会得到一个绑定类型，如下所示：
(>>=) :: (s -> (s,a)) ->
(a -> s -> (s,b)) ->
(s -> (s,b))
你会看到bind只是一种特殊的函数组合运算符，就像 (.)
我写了一篇关于状态单子的博客/教程 这里. 。它可能不是特别好，但是通过编写它帮助我更好地理解了事情。
