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

Question

我正在努力掌握State Monad并且为了这个目的,我想编写一个使用线性同余生成器生成一系列随机数的monadic代码(可能不好,但我的目的只是学习State Monad,而不是建立一个好的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 

不要担心数字,这只是种子的更新规则(根据Numerical Recipes)应该生成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)

好的,这很好用,给我一个Bool每个给定种子的n个伪随机s 列表.但...

我可以阅读我所做的事情(主要基于这个例子:http://www.haskell.org/pipermail/beginners/2008-September/000275.html)并复制它以做其他事情.但是我认为我不能理解do-notation和monadic函数背后的真实情况(比如replicateM).

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

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

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

2 - 我无法理解这些put和get功能究竟是做什么的.我猜他们会"打包"并"打开"状态.但是糖的背后的机制对我来说仍然是难以捉摸的.

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

Answer 1

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

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

不太明显的是,类型构造函数从状态到修改状态和结果采用函数,如下所示:

newtype State stateData result = State (stateData -> (result, stateData))

因此,当monad被称为"状态"时,monad 包含的实际值是基于状态的计算,而不是包含状态的实际值.

牢记这一点,我们不应该惊讶地发现runState用于在State monad中执行计算的函数实际上只不过是包装函数本身的访问器,并且可以像这样定义:

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.因为我们实际上并没有对这个函数中的状态做任何事情,所以让我们做一件明显的事情 - 直接传递那个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),因为这是我们的State包装器所需要的.覆盖状态值result在State计算之外并没有真正的合理值,所以我们的结果就是(),在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在字符串上使用,如果结果为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就可以将它传递给那些我们不了解它们的技巧的函数.此外,我们将使用lambdas接受先前函数的结果并为它们提供临时名称.好的,让我们做到这一点:

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)

Answer 2

首先,你的例子过于复杂,因为它不需要存储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'

为了使嵌套结构更清晰一些,我对缩进采取了重大的自由.

Answer 3

您收到了几个很好的答复。在我看来，与State monad一起工作时所做的事情被替换State s a为s -> (s,a)（毕竟，这确实是事实）。

然后，您将获得绑定类型，如下所示：

(>>=) :: (s -> (s,a)) ->
         (a -> s -> (s,b)) ->
         (s -> (s,b))

您会发现bind只是一种特殊的函数组合运算符，例如 (.)

我在这里写了一篇关于monad州的博客/教程。它可能不是特别好，但是通过编写它帮助我更好地完成了工作。