title: State Monad, sequences of random numbers and monadic code
body: <p>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). </p>
  
  <p>The generator is just this (I want to generate a sequence of <code>Bool</code>s for simplicity):</p>
  
  <pre><code>type Seed = Int
  
  random :: Seed -&gt; (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 
  </code></pre>
  
  <p>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 <code>Int</code>s. Now, if I want to generate random numbers sequentially I'd do:</p>
  
  <pre><code>rand3Bools :: Seed -&gt; ([Bool], Seed)
  rand3Bools seed0  = let (b1, seed1) = random seed0
                          (b2, seed2) = random seed1
                          (b3, seed3) = random seed2
                      in  ([b1,b2,b3], seed3)
  </code></pre>
  
  <p>Ok, so I could avoid this boilerplate by using a State Monad:</p>
  
  <pre><code>import Control.Monad.State
  
  data Random {seed :: Seed, value :: Bool}
  
  nextVal = do 
     Random seed val &lt;- 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
  </code></pre>
  
  <p>And finally:</p>
  
  <pre><code>getNRandSt n = replicateM n nextVal 
  
  getNRand :: Int -&gt; Seed -&gt; [Bool]
  getNRand   n seed = evalState (getNRandStates n) (Random seed True)
  </code></pre>
  
  <p>Ok, this works fine and give me a list of n pseudo-random <code>Bool</code>s for each given seed. But...</p>
  
  <p>I can read what I've done (mainly based on this example: <a href="http://www.haskell.org/pipermail/beginners/2008-September/000275.html" rel="noreferrer">http://www.haskell.org/pipermail/beginners/2008-September/000275.html</a> ) 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).</p>
  
  <p>Can anyone help me with some of this doubts?</p>
  
  <p>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. </p>
  
  <p>How do I really desugar this function to the original >>= and return functions step-by-step? </p>
  
  <p>2 - I couldn't grasp what exactly the <code>put</code> and <code>get</code> functions do. I can guess that they "pack" and "unpack" the state. But the mechanics behind the do-sugar is still elusive to me.</p>
  
  <p>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.</p>