State Monad，随机数字和一元代码的序列 [英] State Monad, sequences of random numbers and monadic code

问题描述

我试图掌握State Monad，为此我想编写一个monadic代码，用一个线性同余发生器产生一个随机数序列（可能不太好，但我的意图是学习状态Monad，不建立一个好的RNG库）。

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

  type Seed = Int 
 
 random :: Seed  - > （Bool，Seed）
 random seed = let（a，c，m）=（1664525,1013904223,2 ^ 32） -  LCG 
种子的某些参数=（a * seed + c ）`mod` m 
 in（even seed'，seed'） - 如果seed是偶数/奇数，返回True / False 
  

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

  rand3Bools :: Seed  - > （bool，seed）
 rand3Bools seed0 = let（b1，seed1）= random seed0 
（b2，seed2）= random seed1 
（b3，seed3）= random seed2 
在（[b1，b2，b3]，seed3）
  

好的，我可以避开这个样板通过使用State Monad：

  import Control.Monad.State 
 
 data Random {seed :: Seed，value :: Bool} 
 
 nextVal = do 
随机种子val<  -  get 
 let seed'= updateSeed seed 
 val'= even seed'$ （a，b，m）=（1664525,1013904223,2 ^ 32）b（b，b）表示随机种子'val'）
返回值'b 
 $ b updateSeed seed = * seed + c）`mod` m 
  

最后：

  getNRandSt n = replicateM n nextVal 
 
 getNRand :: Int  - >种子 - > [bool] 
 getNRand n seed = evalState（getNRandStates n）（Random seed True）
  

好吧，这工作正常，给我一个n伪随机列表 Bool s为每个给定的种子。但是...

我可以阅读我所做的（主要基于此示例： http://www.haskell.org/pipermail/beginners/2008-September/000275.html ）并复制它以完成其他事情。但我不认为我能理解do not notation和monadic函数背后发生的事情（如replicateM）。

任何人都可以帮助我解决这些疑惑吗？

1 - 我试图去解析nextVal函数来理解它的功能，但是我不能。我猜可以提取当前状态，更新它，然后将状态传递给下一个计算，但这只是基于阅读这个do-sugar，就好像它是英文一样。

我如何真正将这个函数解析为原始的>> =并且一步一步地返回函数？

2 - 我无法掌握放入和 get 函数。我可以猜测他们打包和解压缩状态。但是do-do背后的机制仍然难以捉摸。

那么，对于这个代码的其他一般评论是非常受欢迎的。我有时会跟Haskell一起合作，我可以创建一个可以工作的代码，并做我期望的代码，但由于习惯于使用命令式程序，我不能按照评估操作。

解决方案

国家monad起初看起来很混乱，让我们按诺曼拉姆齐的建议做，并从头开始实施。首先，State有两个类型参数：包含的状态数据的类型以及 的类型 em>计算的最终结果。这里我们分别使用 stateData 和 result 作为类型变量。如果你仔细想想，这是有道理的。基于状态的计算的定义特征是它在产生输出时修改状态。

不太明显的是类型构造函数使用函数

从状态到状态和结果，如下所示：

  newtype State state data result = State（stateData  - > （result，stateData））
  

所以当monad被称为State时， monad是基于状态的计算，而不是包含状态的实际值。

记住这一点，我们不应该发现用于在State monad中执行计算的函数 runState 实际上不过是封装函数本身的访问器，并且可以像这：

  runState（State f）= f 
  

那么当你定义一个返回一个状态值的函数时，这意味着什么？让我们暂时忽略一个事实，即国家是一个单子，只看基本类型。首先，考虑这个函数（它实际上并没有对状态做任何事情）：

  len2State :: String  - > State Int Bool 
 len2State s = return（（length s）== 2）
  

如果你看看State的定义，我们可以看到这里的 stateData 类型是 Int ，并且 result type是 Bool ，所以数据构造函数包装的函数必须具有类型 Int - > （Bool，Int）。现在，设想一个无状态版本的 len2State - 显然，它会有类型 String - >布尔。那么，如何将这样一个函数转换为一个返回适合State包装的值？

显然，转换后的函数需要花费一秒参数，表示状态值的 Int 。它还需要返回一个状态值，另一个 Int 。由于我们在这个函数中并没有对状态做任何事情，所以让我们做一些明显的事情 - 把这个int传递给它。这是一个状态函数，按照无状态版本定义：

  len2 :: String  - > Bool 
 len2 s =（（length s）== 2）
 
 len2State :: String  - > （Int  - >（Bool，Int））
 len2State si =（len2's，i）
  

但那是愚蠢和多余的。让我们概括一下转换，以便我们可以传递结果值，并将任何东西变成类似状态的函数。

  convert :: Bool  - > （Int  - >（Bool，Int））
 convert rd =（r，d）
 
 len2 s =（（length s）== 2）
 
 len2State :: String  - > （int  - >（Bool，Int））
 len2State s = convert（len2 s）
  

如果我们想要一个改变状态的函数呢？显然，我们不能用 convert 来构建一个，因为我们写了这个来传递状态。让我们保持简单，写一个函数来用新值覆盖状态。它需要什么类型的？它需要一个 Int 作为新的状态值，当然必须返回一个函数 stateData - > （result，stateData），因为这是我们的状态包装器所需要的。覆盖状态值在状态计算之外并没有真正的 result 值，所以我们的结果只会是（），在Haskell中表示无值的零元素元​​组。 （（），（Int，>（），Int））
overwriteState newState _ =（（），newState）

那很简单！现在，让我们用这些状态数据来做一些事情。让我们从上面将 len2State 重写成更明智的东西：我们将比较字符串长度和当前状态值。

  lenState :: String  - > （Int  - >（Bool，Int））
 lenState si =（（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。我们拥有完成这项任务所需的所有部分，但全部写出来将是一件痛苦的事情。我们可以创建一个函数来自动链接两个函数，每个函数返回类似状态的函数吗？当然可以！我们只需要确定它需要两个参数：第一个函数返回的状态函数和一个函数，它将前一个函数的 result 类型作为参数。让我们看看结果如何：

  chainStates ::（Int  - >（result1，Int）） - > （result1  - >（Int→>（result2，Int））） - > （int  - >（result2，Int））
 chainStates prev fd = let（r，d'）= prev d 
 in fr d'
  pre> 
 
 
所有这些都是将第一个状态函数应用于某些状态数据，然后将第二个函数应用于结果和修改的状态数据。简单的吧？
 
 
现在，有趣的部分： chainStates 和 convert  code>，我们几乎应该能够将任何无状态函数的组合转换为启用状态的函数！我们现在唯一需要的是替换返回状态数据的 useState ，以便chainStates可以将它传递给不知道任何事情的函数我们正在拉他们的诀窍。另外，我们将使用lambdas接受前面函数的结果并给它们临时名称。好的，让我们来做这件事：
  extractState :: Int  - > （Int，Int）
 extractState d =（d，d）
 
 chained :: String  - > （Int  - >（Bool，Int））
 chained str = chainStates extractState $ \state1  - > 
让check1 =（len str state1）in 
 chainStates（overwriteState（
 if check1 
 then state1 
 else state1 * 2））$ \ _  - > 
 chainStates extractState $ \state2  - > 
让
中的check2 =（len str state2）convert（check1 || check2）
  
然后尝试一下： 
 
 
 >链接abcd2 
（True，4）
>链接abcd3 
（假，6）
>链接abcd4 
（True，4）
> chainedabcdef5 
（False，10）
  
当然，我们不能忘记国家实际上是一个包装类似国家职能的monad，并使我们远离它们，所以我们所建立的漂亮功能都不会帮助我们实现真正的事情。或者他们会？在一个令人震惊的转折中，事实证明，真实的国家monad以不同的名字提供了所有相同的功能： 
 
 
  runState（State s）= s 
 return r = State（convert r）
（>> =）sf = State（\d-> let（r，d'）=（runState s）d in 
 runState（fr）d'）
 get = State extractState 
 put d = State（overwriteState d）
  
请注意>> =与chainStates几乎相同，但没有好的方法可以使用chainStates来定义它。因此，为了包装，我们可以使用 real 状态重写最后一个例子： 
 
 
  chained str = get>> = \state1  - > 
让check1 =（len str state1）in 
 put（if check1 
 then state1 else state1 * 2）>> = \ _  - > 
 get>> = \state2  - > 
让check2 =（len str state2）in 
 return（check1 || check2）
  
 
 
  
 
 
  chained str = do 
 state1 < - > 
得到
让check1 = len str state1 
 _<  -  put（如果check1 then state1 else state1 * 2）
 state2 < -  get 
 let check2 =（len str state2 ）
 return（check1 || check2）
  
 
I'm trying to grasp the State Monad and with this purpose I wanted to write a monadic code that would generate a sequence of random numbers using a Linear Congruential Generator (probably not good, but my intention is just to learn the State Monad, not build a good RNG library). 


The generator is just this (I want to generate a sequence of Bools for simplicity):
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 
Don't worry about the numbers, this is just an update rule for the seed that (according to Numerical Recipes) should generate a pseudo-random sequence of Ints. Now, if I want to generate random numbers sequentially I'd do:
rand3Bools :: Seed -> ([Bool], Seed)
rand3Bools seed0  = let (b1, seed1) = random seed0
                        (b2, seed2) = random seed1
                        (b3, seed3) = random seed2
                    in  ([b1,b2,b3], seed3)
Ok, so I could avoid this boilerplate by using a 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
And finally:
getNRandSt n = replicateM n nextVal 

getNRand :: Int -> Seed -> [Bool]
getNRand   n seed = evalState (getNRandStates n) (Random seed True)
Ok, this works fine and give me a list of n pseudo-random Bools for each given seed. But...

I can read what I've done (mainly based on this example: http://www.haskell.org/pipermail/beginners/2008-September/000275.html ) and replicate it to do other things. But I don't think I can understand what's really happening behind the do-notation and monadic functions (like replicateM).

Can anyone help me with some of this doubts?

1 - I've tried to desugar the nextVal function to understand what it does, but I couldn't. I can guess it extracts the current state, updates it and then pass the state ahead to the next computation, but this is just based on reading this do-sugar as if it was english. 

How do I really desugar this function to the original >>= and return functions step-by-step? 

2 - I couldn't grasp what exactly the put and get functions do. I can guess that they "pack" and "unpack" the state. But the mechanics behind the do-sugar is still elusive to me.

Well, any other general remarks about this code are very welcome. I sometimes fell with Haskell that I can create a code that works and do what I expect it to do, but I can't "follow the evaluation" as I'm accustomed to do with imperative programs.
解决方案
The State monad does look kind of confusing at first; let's do as Norman Ramsey suggested, and walk through how to implement from scratch. Warning, this is pretty lengthy!

First, State has two type parameters: the type of the contained state data and the type of the final result of the computation. We'll use stateData and result respectively as type variables for them here. This makes sense if you think about it; the defining characteristic of a State-based computation is that it modifies a state while producing an output.

Less obvious is that the type constructor takes a function from a state to a modified state and result, like so:
newtype State stateData result = State (stateData -> (result, stateData))
So while the monad is called "State", the actual value wrapped by the the monad is that of a State-based computation, not the actual value of the contained state.

Keeping that in mind, we shouldn't be surprised to find that the function runState used to execute a computation in the State monad is actually nothing more than an accessor for the wrapped function itself, and could be defined like this:
runState (State f) = f
So what does it mean when you define a function that returns a State value? Let's ignore for a moment the fact that State is a monad, and just look at the underlying types. First, consider this function (which doesn't actually do anything with the state):
len2State :: String -> State Int Bool
len2State s = return ((length s) == 2)
If you look at the definition of State, we can see that here the stateData type is Int, and the result type is Bool, so the function wrapped by the data constructor must have the type Int -> (Bool, Int). Now, imagine a State-less version of len2State--obviously, it would have type String -> Bool. So how would you go about converting such a function into one returning a value that fits into a State wrapper?

Well, obviously, the converted function will need to take a second parameter, an Int representing the state value. It also needs to return a state value, another Int. Since we're not actually doing anything with the state in this function, let's just do the obvious thing--pass that int right on through. Here's a State-shaped function, defined in terms of the State-less version:
len2 :: String -> Bool
len2 s = ((length s) == 2)

len2State :: String -> (Int -> (Bool, Int))
len2State s i = (len2' s, i)
But that's kind of silly and redundant. Let's generalize the conversion so that we can pass in the result value, and turn anything into a State-like function. 
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)
What if we want a function that changes the state? Obviously we can't build one with convert, since we wrote that to pass the state through. Let'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 need an Int for the new state value, and of course will have to return a function stateData -> (result, stateData), because that's what our State wrapper needs. Overwriting the state value doesn't really have a sensible result value outside the State computation, so our result here will just be (), the zero-element tuple that represents "no value" in Haskell.
overwriteState :: Int -> (Int -> ((), Int))
overwriteState newState _ = ((), newState)
That was easy! Now, let's actually do something with that state data. Let's rewrite len2State from above into something more sensible: we'll compare the string length to the current state value.
lenState :: String -> (Int -> (Bool, Int))
lenState s i = ((length s) == i, i)
Can we generalize this into a converter and a State-less function, like we did before? Not quite as easily. Our len function will need to take the state as an argument, but we don't want it to "know about" state. Awkward, indeed. However, we can write a quick helper function that handles everything for us: we'll give it a function that needs to use the state value, and it'll pass the value in and then package everything back up into a State-shaped function leaving len none the wiser.
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)
Now, the tricky part--what if we want to string these functions together? Let's say we want to use lenState on a string, then double the state value if the result is false, then check the string again, and finally return true if either check did. We have all the parts we need for this task, but writing it all out would be a pain. Can we make a function that automatically chains together two functions that each return State-like functions? Sure thing! We just need to make sure it takes as arguments two things: the State function returned by the first function, and a function that takes the prior function's result type as an argument. Let's see how it turns out:
chainStates :: (Int -> (result1, Int)) -> (result1 -> (Int -> (result2, Int))) -> (Int -> (result2, Int))
chainStates prev f d = let (r, d') = prev d
                       in f r d'
All this is doing is applying the first state function to some state data, then applying the second function to the result and the modified state data. Simple, right?

Now, the interesting part: Between chainStates and convert, we should almost be able to turn any combination of State-less functions into a State-enabled function! The only thing we need now is a replacement for useState that returns the state data as its result, so that chainStates can pass it along to the functions that don't know anything about the trick we're pulling on them. Also, we'll use lambdas to accept the result from the previous functions and give them temporary names. Okay, let's make this happen:
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)
And try it out:
> chained "abcd" 2
(True, 4)
> chained "abcd" 3
(False, 6)
> chained "abcd" 4
(True, 4)
> chained "abcdef" 5
(False, 10)
Of course, we can't forget that State is actually a monad that wraps the State-like functions and keeps us away from them, so none of our nifty functions that we've built will help us with the real thing. Or will they? In a shocking twist, it turns out that the real State monad provides all the same functions, under different names:
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)
Note that >>= is almost identical to chainStates, but there was no good way to define it using chainStates. So, to wrap things up, we can rewrite the final example using the real State:
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)
Or, all candied up with the equivalent do notation:
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)


                        
这篇关于State Monad，随机数字和一元代码的序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！