How to preserve random numbers in Haskell iteration?

user_19145505 0
Viewed 143

I'm trying to calculate growing list with random number. The basic code is here:

import System.Random

randint :: IO Int
randint = randomRIO (0,1)

type Generation = [Int]

gnext :: Generation -> IO Generation
gnext g = flip (:) g <$> randint

gnext can be more complex.

Now following code behaved as expected:

test1 = do
  let b0 = []
  b1 <- gnext b0
  b2 <- gnext b1
  b3 <- gnext b2
  b4 <- gnext b3
  return [b0, b1, b2, b3, b4]

ghci> test1
[[],[0],[1,0],[1,1,0],[1,1,1,0]]

We can see the n-th list has the (n-1)-th list in its cdr part.

On the other hand, following code failed (because of lazy evaluation, I think).

test2 = sequence $ take 5 $ iterate (gnext =<<) (return [])

ghci> test2
[[],[0],[0,0],[1,0,1],[1,1,1,0]]

This result is completely random.

How can I rewrite test1 code by test2 style? Thank you.

haskell
2 Answers

What's the problem with sequence $ take 5 $ iterate (gnext =<<) (return [])?

Let's reduce iterate (gnext =<<) (return []):

iterate (gnext =<<) (return []) =>
[ return []
, gnext =<< return []
, gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< gnext =<< return []
, ...
]

Next reduce take 5 $ iterate (gnext =<<) (return []):

take 5 $ iterate (gnext =<<) (return []) =>
[ return []
, gnext =<< return []
, gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< return []
, gnext =<< gnext =<< gnext =<< gnext =<< return []
]

And finally, reduce sequence $ take 5 $ iterate (gnext =<<) (return []):

sequence $ take 5 $ iterate (gnext =<<) (return []) =>
sequence [ return []
         , gnext =<< return []
         , gnext =<< gnext =<< return []
         , gnext =<< gnext =<< gnext =<< return []
         , gnext =<< gnext =<< gnext =<< gnext =<< return []
         ]

which equivalent to:

do
    b0 <- return []
    b1 <- gnext =<< return []
    b2 <- gnext =<< gnext =<< return []
    b3 <- gnext =<< gnext =<< gnext =<< return []
    b4 <- gnext =<< gnext =<< gnext =<< gnext =<< return []
    return [b0, b1, b2, b3, b4]

As you can see, this is not what you want, and lazy evaluation has nothing to do with it.

You can solve this problem with the state monad:

gnextM :: StateT Generation IO Generation
gnextM = do
    g0 <- get
    g1 <- liftIO $ gnext g0
    put g1
    return g1

test2 = flip evalStateT [] $ sequence $ take 5 $ repeat gnextM

or:

gnextM :: StateT [Generation] IO ()                                         
gnextM = do                                                                 
    b0 <- gets head                                                         
    b1 <- liftIO $ gnext b0                                                 
    modify (b1:)                                                            

runGen :: StateT [Generation] IO a -> Generation -> IO [Generation]         
runGen gnext s = execStateT gnext [s]                                       
                                                                        
test2 = flip runGen [] $ replicateM 5 gnextM

depending on what you want.

user_71751170

following code failed (because of lazy evaluation, I think).

It’s not really due to lazy evaluation. In test1, you share the chain of results of all the actions, while in test2, you only share the actions themselves before sequencing them together, and their results are unrelated:

test2 = sequence (take 5 actions)
  where
    actions
      = (return [])
      : [(gnext =<< a) | a <- actions]

test2 = sequence
  [ return []
  , gnext =<< return []
  , gnext =<< gnext =<< return []
  , gnext =<< gnext =<< gnext =<< return []
  , gnext =<< gnext =<< gnext =<< gnext =<< return []
  ]

So the issue is that sequence (take 5 actions) doesn’t express the relationship you want, which is something more like fmap (take 5) (sequence actions). Unfortunately, that doesn’t produce a result at all, because sequence in IO is too strict: it tries to consume the infinite stream of actions before producing a result at all.

Instead, it’s typical to use patterns such as tails <$> replicateM 5 randint when you know the length ahead of time, or combinators like unfoldrM if not:

test = unfoldrM step (b0, 5)
  where
    b0 = []
    step (b, i)
      | i == 0 = pure Nothing
      | otherwise = do
        b' <- gnext b
        pure (Just (b', (b', i - 1)))

-- Available in ‘monad-loops’ or as below.
unfoldrM
  :: (Monad m)
  => (a -> m (Maybe (b, a))) -> a -> m [b]
unfoldrM f = go
  where
    go a = do
      m <- f a
      case m of
        Just (b, a') -> do
          bs <- go a'
          pure (b : bs)
        Nothing -> pure []
user_2468860
Related