How to thread a state in the same State monad indefinitely in Haskell?

Question

Beginning with Haskell and stuck at the State Monad ...

So I am trying to come to grips with the State Monad in Haskell, and to understand it, I am writing a code to generate PRBS sequences. For people interested, it is described in the paper 'Pseudo Random Sequences and Arrays', a free copy of which can be obtained by the doi: 10.1109/PROC.1976.10411.

The essential coputation is very simple. You have a shift register and a generator polynomial. The generator polynomial tells you which bits of the shift register to take and sum (modulo 2) to get the MSB of the shift register. In the next iteration, you take this computed MSB and stick it to the MSB of the shift register after doing a right shift operation.

The code for doing this without monads is really simple:

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

The output is as follows:

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

which is what I want.

Now of course, since the shift register can be considered to be a state which we modify, we can use the state monad for this purpose. Maybe it is too simple a problem to learb about the state monad, bit I just seem to think that this might be the perfect example which one may implement using the state monad. So here is what I did:

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

This is just adding on to the previous code segment of code, along with the import Control.Monad.State in the first like of the program. When I import this into GHCI and check the state computations, I am able to get individual values as shown below:

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

So both the state is being updated correctly and the value being returned is also correct. Now I want to create a function like the function word in the previous implementation that will apply the >> operator on the bitMs n times so that we can create the array word p s. I am totally clueless about how to even go about doing this. Note, that I dont want to put in a set of functions like:

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

I want one function to which I will pass n and it will do the bitM evaluations successively n times, passing on the state internally in successive computations automatically, collect the resultant values, and create an array as a result. How do I go about doing that? I cant figure out how to go about doing this. Any help will be greatly appreciated!

Zeta Zeta · Accepted Answer · 2014-02-26T09:23:25

If you look a litte bit at it, bitM >> bitM >> ... > bitM can be thought as a list of actions, so we're looking for Int -> m a -> [m a] or simpler Int -> a -> [a], which is just the signature of replicate. We'll end up with something of type

[State [Int] Int]

Now we're looking for [State [Int] Int] -> State [Int] [Int], or simpler: [m a] -> m [a], which happens to be sequence. Therefore, you're looking for

sequence . replicate n $ bitM

which happens to be replicateM, which has type Int -> m a -> m [a].

How to thread a state in the same State monad indefinitely in Haskell?

1 Answers