samedi 16 mars 2019

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

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?




Aucun commentaire:

Enregistrer un commentaire