Recursively defining a list of monadic random numbers: most idiomatic Haskell and analogous to pure code

Question

I am trying to recursively make a list of random numbers that uses the previous value to get the next (so recursion is required instead of map or fold, and also I prefer to make it explicit unless map/foldr makes it ridiculously simple in comparison).

Using a pure PRNG this is very straightforward and idiomatic, in my opinion (puregaussian uses System.Random to generate a normal variate and has type puregaussian :: System.Random.RandomGen t => t -> Double -> Double -> (Double, t)).

purecurse :: System.Random.RandomGen t => t -> Double -> [Double] -> [Double]
purecurse gen current [] = []
purecurse gen current (x:xs) = let (rand, gen2) = puregaussian gen 0 1
                                   next = current + rand
                               in current:purecurse gen2 next xs

Unfortunately, pure PRNGs don't seem do be as well developed in Haskell as the monadic ones, so I want to do the same thing using a library like random-fu or mwc-probability, and the solutions I found to work are either unidiomatic, not as concise, or both.

Here's a solution using do notation that works, and why I'm not satisfied with it:

import Control.Monad.Primitive
import System.Random.MWC.Probability

recurse :: PrimMonad m => Gen (PrimState m) -> [Double] -> [Double] -> m [Double]
recurse gen history@(current:_) [] = return history
recurse gen history@(current:_) (x:xs) = do
                                         rand <- (sample (normal 0 1) gen)
                                         let next = current + rand
                                         recurse gen (next:history) xs

First of all I would rather use >>= than do notation, but I couldn't find a way of binding the rand variable that has type m Double and then lifting it to get m [Double] at the end case. There doesn't seem to be a lot of documentation (that I could find) or examples on how to do something like that. I thought maybe it would be necessary to nest the (>>=) operators, but that could make the function extremely complicated or unreadable. If that is the tradeoff, maybe do notation is just cleaner, but I didn't manage to make even that work and would like to know how to.

Second, the function requires the entire list to be passed on at each call, and gives the list back in reverse (and just switching next and history breaks it).

So. I would like to be able to pass the initial state and a list to recurse over that returns a monadic list of values.

The main question I would like help with is: is there a Haskell idiomatic way of writing such a recursion of monadic values resulting in a monadic list that is similar to the structure of a pure function?

Answer 1

The main question I would like help with is: is there a Haskell idiomatic way of writing such a recursion of monadic values resulting in a monadic list that is similar to the structure of a pure function?

You can do it in two steps. Have your recursive function return a list of "monadic actions", then compose / sequence those actions.

Lets consider a simpler but analogous function to yours, for ease of presentation. Instead of randomness lets consider input. The list you recourse over is there for size only (content is ignored) so lets just use an integer.

rc ::  Int -> [Double] -> IO [Double]
rc 0 h        = return h
rc n h@(cr:_) = do rand <- readLn :: IO Double
                   let nx = cr + rand
                   rc (n-1)(nx:h) 

Here is a similar alternative that works the way you wants

rc' ::  Int -> Double -> IO [Double]
rc' 0 cr = return []
rc' n cr = do rand <- readLn :: IO Double
              let nx = cr + rand
              xs   <- rc' (n-1) nx
              return (nx : xs)

And here without do notation

rc'' ::  Int -> Double -> IO [Double]
rc'' 0 cr = return []
rc'' n cr = (readLn :: IO Double) >>= (\rand -> 
              let nx = cr + rand 
              in (rc'' (n-1) nx) >>= (\xs ->
                 return (nx : xs))) 

In any case, another thing you can do is abstract away pieces of code, rather than have a monolithic presentation.

In each step you require the current value to generate a new one. So a step is a function of type Double -> IO Double. And this is a pretty neat type, fundamental in the world of monads. You can bind values to a step via x >>= step or compose two steps with step1 >=> step2. So lets go with it.

step :: Double -> IO Double
step cr = do rand <- readLn :: IO Double
             return (cr + rand)

It's very easy to understand. You 'generate' a number, add the current one and return the result. And you want to do n such steps, so make a list of steps.

steps :: Int -> [Double -> IO Double]
steps n = replicate n step 

Now you can choose how to combine them. For instance it would be very natural to fold a list of steps with >=>. You would get this,

runSteps :: Int -> Double -> IO Double 
runSteps n = foldr (>=>) return (steps n)

It's close to what you want but only returns the final result, rather than accumulate the generated values at each step. Below is a (restricted) type of (>=>) and the type of the operator (*=>) we want.

(>=>) :: Monad m => (a -> m a) -> (b -> m  a)  -> a -> m  a
(*=>) :: Monad m => (a -> m a) -> (a -> m [a]) -> a -> m [a]

The definition is,

(*=>) :: Monad m => (a -> m a) -> (a -> m [a]) -> a -> m [a]
(*=>) ac uc c = do x  <- ac c
                   xs <- uc x
                   return (x:xs) 

I actually think this encapsulates the bit you didn't particularly like. Now we abstracted it away to this isolated piece of code. Even away from the recursive calls. And finally we just fold to execute the steps.

execSteps :: Int -> Double -> IO [Double] 
execSteps n = foldr (*=>) (\x -> return []) (steps n) 

This function differs from the original one in the initial input being a Double rather than a [Double]. But this is the type that makes sense. You'd just be passing a single wrapped double in the original function. And it accumulates the elements in the 'right' order as you requested.

Answer 2

is there a Haskell idiomatic way of writing such a recursion of monadic values resulting in a monadic list that is similar to the structure of a pure function

Usually, when need apply a monadic values to a pure function, Applicative operator, such as <$>, <*> may be helpful.

In particular, for list construction, it is often apply operator (:) in recursive way to build a list, like

f [] = []
f (x:xs) = x : f xs

in prefix way:

(:) x (f xs)

However, (:) is pure function, not accept monadic value by default, but the good new is, every data type which is instance of Monad, it also be an instance of Applicative. with help of Applicative operator mentioned above, monadic value can be applied to pure function without any change. For example,

(:) <$> (pure x) <*> (pure .f) xs

will return a monadic List instead of pure list.

Return to your question, personally, I think your solution in question is already almost a idiomatic way to do that (since it is simple and readable) except always append next random value at the head of history.

As you said, the list back in reverse and worse, when the history list has old random value already, it is inconvenient to find out which is new add to it.

To solve it, it can be modified slightly as:

recurse :: PrimMonad m => Gen (PrimState m) -> [Double] -> [Double] -> m [Double]
recurse gen history [] = return history
recurse gen history (x:xs) = do rand <- (sample (normal 0 1) gen)
                                let next = (last history) + rand
                                recurse gen (history ++ [next]) xs

It make sense, if the last element of history is the newest random value.

However, the different between (:) and (++) is: (:) is O(1), but (++) is O(N), where the N is the length of history list. (and last history is also O(N) instead of O(1)).

To archive an efficient solution, a helper function may need to introduce, say, newHistory, to construct a new list of random value as:

newHistory::PrimMonad m=>Gen(PrimState m)->m Double->[Double]->m [Double]
newHistory _ _ []             = return []
newHistory gen current (x:xs) = let next = (+) <$> current <*> sample (normal 0 1) gen
                                in  (:) <$> next <*> newHistory gen next xs

As said before, with help of Applicative operator, the syntax look like pure function, except apply function in prefix way and use Applicative operator.

And then append back to the original history list as:

(++) <$> pure history <*> newHistory gen (pure $ last history) xs

And the Applicative version of recurse function look like:

recurse2::PrimMonad m=>Gen(PrimState m)->[Double]->[Double]->m [Double]
recurse2 gen history xs = 
    (++) <$> pure history <*> newHistory gen (pure $ last history) xs

    where newHistory::PrimMonad m=>Gen(PrimState m)->m Double->[Double]->m [Double]
          newHistory _ _ []         = return []
          newHistory gen current (x:xs) = 
            let next = (+) <$> current <*> sample (normal 0 1) gen
            in  (:) <$> next <*> newHistory gen next xs

Answer 3

Your issue seems to lie with do-notation and monads. You're assuming there's much more magic going on than there actually is: learning how the desugaring works will help you out here.

Anyway, let's try and convert the non-monadic version into the monadic one step-by-step. First, the type signature:

recurse :: PrimMonad m => Gen (PrimState m) -> Double -> [Double] -> m [Double]

I'm not sure why you had [Double] as the second parameter in your version: we want to change as little as possible from the original. The first clause, then:

purecurse gen current [] = []
-- Goes to:
recurse gen current [] = return []

Again, we're changing as little as possible: no effects were happening in this clause in your pure code, so no effects should be happening here, either. You got the next two lines right:

purecurse gen current (x:xs) = let (rand, gen2) = puregaussian gen 0 1
                                   next = current + rand
-- Goes to:
recurse gen current (x:xs) = do rand <- (sample (normal 0 1) gen)
                                let next = current + rand

But the last one tripped you up. Ideally, we would write:

in current:purecurse gen2 next xs
-- Goes to:
current:recurse gen next xs

But it doesn't work! What's more, you get a confusing error:

• Couldn't match type ‘Double’ with ‘[Double]’
  Expected type: m [Double]
    Actual type: [Double]

This is probably what led you down the wrong path. The issue has nothing to do with the lists: it's to do with the m (the encapsulating monad). When you write current : xs, xs has to be a list: in this example, it's actually a m [Double], or a list wrapped in the monad. There's two ways to solve the problem (which are both equivalent). We could unwrap the list, using do notation again:

rest <- recurse gen next xs
return (current : rest)

Or we could lift the function current : to work inside the monad:

fmap (current:) (recurse gen next xs)

Answer 4

In situations like this, I usually jump straight to using a streaming library with a suitably list-like interface, like streaming. They allow a more natural translation from pure code to monadic, and have the added benefit that you aren't required to construct/consume all of the results at once, but instead incrementally, just as with pure lists.

I'm not sure what purecurse is doing, but it could be written as

import           Streaming
import qualified Streaming.Prelude as S

recurse :: PrimMonad m 
        => Gen (PrimState m) 
        -> Double 
        -> [Double] 
        -> Stream (Of Double) m ()
recurse gen current [] = 
    return ()
recurse gen current (x:xs) =
    S.yield current *> -- (*>) and (>>) work like concatenation for pure lists
    lift (sample (normal 0 1) gen) >>= \rand -> 
    recurse gen (current + rand) xs

Or, more naturally using do-notation, as:

recurse :: PrimMonad m 
        => Gen (PrimState m) 
        -> Double 
        -> [Double] 
        -> Stream (Of Double) m ()
recurse gen current [] = 
    return ()
recurse gen current (x:xs) = 
    do S.yield current -- (*>) and (>>) work like concatenation for pure lists
       rand <- lift $ sample (normal 0 1) gen
       recurse gen (current + rand) xs

Now you can use function like S.take to generate/extract only parts of the result. If you want to get the whole list, you can use S.toList_.