1

从 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]

这就是我想要的。

当然，既然移位寄存器可以被认为是我们修改的状态，我们可以为此目的使用状态单子。也许学习状态单子太简单了，我似乎只是认为这可能是一个可以使用状态单子实现的完美示例。所以这就是我所做的：

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之前实现中的函数的函数，它将在s次上应用>>运算符，以便我们可以创建数组。我完全不知道如何去做这件事。请注意，我不想放入一组函数，例如：bitMnword p s

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

我想要一个我将传递给它的函数，它将n连续多次进行bitM评估n，在连续计算中自动在内部传递状态，收集结果值，并创建一个数组作为结果。我该怎么做呢？我不知道该怎么做。任何帮助将不胜感激！

4

1 回答 1

7

如果您稍微看一下，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，它有 type Int -> m a -> m [a]。

于 2014-02-26T09:23:25.973 回答