State Monad，随机数序列和monadic代码-Java 学习之路

我正在努力掌握State Monad并且为了这个目的，我想编写一个使用线性同余生成器生成一系列随机数的monadic代码（可能不好，但我的目的只是学习State Monad，而不是 Build 一个好的RNG库） .

生成器就是这样（为了简单起见，我想生成一个 Bool 序列）：

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

不要担心数字，这只是种子的更新规则（根据Numerical Recipes）应该生成 Int 的伪随机序列 . 现在，如果我想按顺序生成随机数，我会这样做：

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个伪随机 Bool 的列表 . 但...

我可以阅读我所做的事情（主要基于这个例子：http://www.haskell.org/pipermail/beginners/2008-September/000275.html）并复制它做其他事情 . 但是我并没有真正发生在do-notation和monadic函数背后（比如replicateM） .

有人可以帮我解决一些疑惑吗？

1 - 我试图去掉nextVal函数来理解它的作用，但我不能 . 我可以猜测它会提取当前状态，更新它然后将状态提前传递到下一个计算，但这只是基于读取这个do-sugar，就像它是英语一样 .

我如何真正地将这个函数去掉原始的>> =并逐步返回函数？

2 - 我无法理解 put 和 get 函数究竟是做什么的 . 我猜他们是"pack"和"unpack"这个州 . 但是糖的背后的机制对我来说仍然是难以捉摸的 .

好吧，关于这段代码的任何其他一般性评论都是非常受欢迎的 . 我有时会遇到Haskell，我可以创建一个有效的代码并按照我的期望去做，但我不能“按照评估”，因为我习惯于使用命令式程序 .

3 回答

30
国家monad一开始看起来确实令人困惑;让我们按照Norman Ramsey的建议去做，并从头开始实现如何实施 . 警告，这很长！

首先，State有两个类型参数：包含的状态数据的类型和计算的最终结果的类型 . 我们将在这里分别使用 stateData 和 result 作为它们的类型变量 . 如果你考虑一下，这是有道理的;基于状态的计算的定义特征是它在产生输出时修改状态 .

不太明显的是，类型构造函数从状态到修改状态和结果采用函数，如下所示：
```
newtype State stateData result = State (stateData -> (result, stateData))
```
因此，当monad被称为"State"时，monad包装的实际值是基于状态的计算，而不是包含状态的实际值 .

记住这一点，我们不应该惊讶地发现用于在State monad中执行计算的函数 runState 实际上只不过是包装函数本身的一个访问器，并且可以像这样定义：
```
runState (State f) = f
```
那么当你定义一个返回State值的函数时它意味着什么呢？让我们暂时忽略State是monad的事实，只看一下底层类型 . 首先，考虑一下这个函数（它实际上并没有对状态做任何事情）：
```
len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)
```
如果查看State的定义，我们可以看到 stateData 类型为 Int ， result 类型为 Bool ，因此数据构造函数包装的函数必须具有 Int -> (Bool, Int) 类型 . 现在，想象一下 len2State 的无状态版本 - 显然，它的类型为 String -> Bool . 那么你将如何将这样一个函数转换成一个返回一个适合State包装器的值？

很明显，转换后的函数需要采用第二个参数，即表示状态值的 Int . 它还需要返回一个状态值，另一个是 Int . 因为我们're not actually doing anything with the state in this function, let'只是做了明显的事情 - 直接传递那个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 构建一个，因为我们写了这个来传递状态 . 设's keep it simple, and write a function to overwrite the state with a new value. What kind of type would it need? It' ll需要 Int 作为新的状态值，并且当然必须返回一个函数 stateData -> (result, stateData) ，因为's what our State wrapper needs. Overwriting the state value doesn't在状态计算之外确实有一个合理的 result 值，所以我们的结果只是 () ，这是在Haskell中表示"no value"的零元素元组 .
```
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 ，然后在结果为false时将状态值加倍，然后再次检查字符串，如果检查到，则最后返回true . 我们拥有完成这项任务所需的所有部分，但将其全部写出来会很痛苦 . 我们可以创建一个自动将两个函数链接在一起的函数，每个函数返回类似状态的函数吗当然可以！我们只需要确保它将两个方面作为参数：第一个函数返回的State函数，以及将previous函数的 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就可以将它传递给不需要拉动它们的函数 . 此外，我们'll use lambdas to accept the result from the previous functions and give them temporary names. Okay, let' s实现了这一点：
```
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)
```
当然，我们不能忘记，国家实际上是一个包含类似国家的功能并使我们远离它们的单子，因此我们所建造的任何漂亮的功能都不会帮助我们处理真实的事物 . 或者他们会吗？令人震惊的是，事实证明，真正的国家monad以不同的名字提供了所有相同的功能：
```
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)
```
回复于 2024-04-26T22:33:56+08:00
4
首先，您的示例过于复杂，因为它不需要将 val 存储在状态monad中;只有种子才是持久状态 . 其次，我认为如果不使用标准状态monad，你将获得更好的运气，你可以用它们的类型重新实现所有状态monad及其操作 . 我想你会通过这种方式学到更多东西 . 以下是一些让您入门的声明：
```
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 符号非常复杂 . 但是desugaring是一种一次性的机械程序 . 尽可能接近，你的代码应该像这样desugar（回到你原来的类型和代码，我不同意）：
```
nextVal = get >>= \ Random seed val ->
                      let seed' = updateSeed seed
                          val'  = even seed'
                      in  put (Random seed' val') >>= \ _ -> return val'
```
为了使嵌套结构更清晰一些，我对缩进采取了重大的自由 .
回复于 2024-04-26T22:33:56+08:00
7
你有几个很好的回应 . 在使用状态monad时我所做的就是在我的脑海中用 s -> (s,a) 替换 State s a （毕竟，这就是它的本质） .

然后，您将获得一个类似于bind的类型：
```
(>>=) :: (s -> (s,a)) ->
         (a -> s -> (s,b)) ->
         (s -> (s,b))
```
你看到bind只是一种特殊的函数组合运算符，如 (.)

我写了关于州monad here的博客/教程 . 它可能不是特别好，但通过编写它帮助我改善了一些事情 .
回复于 2024-04-26T22:33:56+08:00

State Monad，随机数序列和monadic代码

3 回答

相关问题