Random list where each element differs by at most 1 from the previous element

Question

I'm attempting to write a function which will generate a list, where the first element is specified as an argument to the function, and every element after that has a difference of at most 1 from the previous element. Here's what I have tried:

import Data.List
import System.Random

step :: Int -> IO Int
step n = (+n) <$> randomRIO (-1, 1)

steps :: Int -> Int -> IO [Int]
steps n = sequence . take n . iterate' (>>= step) . return

(I also tried with the non-strict iterate function, which gave me the same result).

The step function takes an integer and, at random, adds either -1, 0, or 1 to it. The steps function takes an amount of iterations to perform and a starting integer, and applies step the correct amount of times.

The problem is that steps gives me things like [0,1,-1,0,1,1,1,3], which is wrong. It looks like each element is generated from scratch each time, whereas I want each element to depend on the previous one. This is the reason I decided to use iterate' instead of iterate, which says it reduces each iteration to WHNF before continuing, but even still it doesn't work.

Then I realised that the problem might arise from the fact that it will actually generate a list which looks something like:

[ n,
  n >>= step,
  n >>= step >>= step
  ... ]

And then it seems clear why it happens. So my question is, can I prevent this? Can I force Haskell to evaluate each element as it goes along? Is there a strict version of the >>= operator?

(Edit: I thought it might be useful to give an example of the kind of list I'm looking for, instead of just describing one. [0, 1, 2, 1, 2, 1, 0, -1], for example)

Answer 1

You don't need a strict version of the >>=. You need a monadic variant for iterate. After all, you already identified your problem, you're building an infinite number of computations:

[ return x , return x >>= step, return x >>= step >>= step, ... ]

You would need a monadic variant of iterate:

-- This function does not work, but shows the principle we would
-- want from such a function.
iterateM :: Monad m => (a -> m a) -> a -> m [a]
iterateM f x = do
     y  <- f x
     ys <- iterateM f y -- << this never terminates
     return (y:ys)

However, that variant does not exist*, as it will not terminate, for the same reasons that forM [1..] return does not terminate. We can, however, fix this, if change the algorithm to first generate the differences with replicateM and then sum those differences with scanl:

import Control.Monad (replicateM)
import System.Random (randomRIO)

step :: IO Int
step = randomRIO (-1, 1)

steps :: Int -> Int -> IO [Int]
steps n x = scanl (+) x <$> replicateM n step

In this case, we have a limited number of steps in IO and use the usual scanl to generate your desired list.

^{* There are some variants in streaming libraries where the consumer can decide whether a computation can run. iterateM can be implemented there, for example in ConduitM.}