如何在Haskell中无限期地在同一个State monad中连接一个状态？

Question

从Haskell开始,一直停留在State Monad ......

所以我试图在Haskell中掌握State Monad,并理解它,我正在编写一个代码来生成PRBS序列.对于感兴趣的人,它在论文'Pseudo Random Sequences and Arrays'中描述,其免费副本可以通过doi获得:10.1109/PROC.1976.10411.

必要的代表团很简单.你有一个移位寄存器和一个生成多项式.生成多项式告诉您移位寄存器的哪些位采用并求和(模2)以获得移位寄存器的MSB.在下一次迭代中,您采用此计算的MSB并在执行右移操作后将其粘贴到移位寄存器的MSB .

没有monad这样做的代码非常简单:

import Data.List

m = (4::Int)              -- This is the degree of the polynomial
p = tail $ [4, 1, 0]      -- This is a actual polynomial
s = 1 : replicate (m-1) 0 -- This is the initial state. Note that the head is the MSB

chSt poly s = msb poly s : init s -- changes the shift register 's'
    where
        msb poly s = let tot = sum $ map ( (reverse s) !! ) poly
                     in  tot `mod` 2

word p s = take n $ bits p s
    where
        bits p s = last s : bits p (chSt p s)
        n        = 2 ^ (length s) - 1

输出如下:

[ghci] word p s      --> [0,0,0,1,0,0,1,1,0,1,0,1,1,1,1]

这就是我想要的.

当然,由于移位寄存器可以被认为是我们修改的状态,我们可以使用状态monad来实现此目的.也许这是一个关于状态monad的问题太简单了,我似乎认为这可能是一个完美的例子,可以用状态monad实现.所以这就是我所做的:

getVal :: [Int] -> State [Int] Int
getVal poly = do
    curState <- get
    let lsb = last curState
    modify $ chSt poly
    return lsb

bitM :: State [Int] Int 
bitM = getVal p

这只是添加到代码的前一代码段,以及import Control.Monad.State程序的第一个代码段.当我将其导入GHCI并检查状态计算时,我能够获得如下所示的单个值:

[ghci] runState ( bitM  ) s                                   --> (0,[0,1,0,0])
[ghci] runState ( bitM >> bitM  ) s                           --> (0,[0,0,1,0])
[ghci] runState ( bitM >> bitM >> bitM ) s                    --> (0,[1,0,0,1])
[ghci] runState ( bitM >> bitM >> bitM >> bitM) s             --> (1,[1,1,0,0])
[ghci] runState ( bitM >> bitM >> bitM >> bitM >> bitM) s     --> (0,[0,1,1,0])
[ghci] 

因此,状态正在正确更新,并且返回的值也是正确的.现在我想创建一个类似于word前一个实现中的函数的函数,它将>>在bitMs n次上应用运算符,以便我们可以创建数组word p s.关于如何做到这一点,我完全不知道.请注意,我不想放入一组函数,如:

f1 = bitM
f2 = bitM >> bitM
f3 = bitM >> bitM >> bitM 
...

我想要一个函数,我将通过n它,它将bitM连续进行评估n,自动在连续计算中内部传递状态,收集结果值,并作为结果创建一个数组.我该怎么做呢？我无法弄清楚如何去做这件事.任何帮助将不胜感激!

Answer 1

如果你看起来很bitM >> bitM >> ... > bitM轻松,可以认为是行动清单,所以我们正在寻找Int -> m a -> [m a]或更简单Int -> a -> [a],这只是签名replicate.我们最终会得到类型的东西

[State [Int] Int]

现在我们正在寻找[State [Int] Int] -> State [Int] [Int]或更简单:[m a] -> m [a]恰好是sequence.因此,你正在寻找

sequence . replicate n $ bitM

碰巧是replicateM,有类型Int -> m a -> m [a].