[Haskell-beginners] Randomness, lists, and unfoldr

[Cook, James A CTR USA USMA]

Daniel Fischer wrote:
> What you want would be something like
> 
> iterateM :: (Monad m) => (a -> m a) -> a -> m [a]
> iterateM act start = do
>     next <- act start
>     rest <- iterateM act next
>     return (start : rest)
> 
> but that would only work if the bind is sufficiently lazy, otherwise you'd
> have to iterate a given number of times.

Daniel's explanation is exactly right - unfoldr doesn't work "in the monad", and you need a function like this iterateM that does.  Unfortunately (as he hints) this exact function won't work because it tries to compute an infinite list, which RVar can't do in finite time.  Intstead, I would recommend starting with a function such as iterateM and modifying it to accept a "number of steps" parameter - effectively fusing the "take" step into the "unfoldr" step from your original example - or to use some other knowledge of your algorithm to limit the size of the list generated. For example, truncating the output when the cell changes to False.  That would be a bit silly in this example since then your output would just be a variable-length list of "True"s, but I imagine this is just a simplification of what you're really trying to accomplish anyway.

I'm pretty sure it would not be possible to make the bind lazy (even when the remaining computation uses no entropy), because if nothing else the bind operation would have to search the remaining (infinite) computation to make sure it isn't going to require any more random sampling.  Lazily sampling the random variables wouldn't be an option either - that would effectively require a generalized unsafeInterleaveIO which is somehow able to work in any monad, since RVars can be run in all kinds of monads - State, IO, "ContT (FooT BarM)", etc. - anything that has a 'RandomSource' or 'MonadRandom' instance.

Incidentally, the type of "unfoldr (\x -> Just (x, x >>= updateCell))" gives a valuable clue about the behavior you can expect from it.  Its type is [RVar Bool], which is a list of random variables.  Every RVar is (by design) independent from all others, so that type just can't describe the operation you want.  "iterateM updateCell True" has the type you need, which is "RVar [Bool]".

-- James