Hi all, I am having a problem with the implementation of a program (a genetic algorithm) which requires randomness in it. It all hinges on the ability to generate something (in the example below an Int), then provide a function to update it such that the prelude's iteratefunction (or an equivalent) may be used. In my program I require that both the generation and the updating function contain randomness. I have drafted a (simplified) example of my problem: This code show a trivial case where randomness (and hence the IO monad) is not used and the first 10 elements of the produced list are printed: aNum :: Int aNum = 2 addTwo :: Int -> Int addTwo = (+) 2 firstTen :: [Int] firstTen = take 10 (iterate addTwo aNum) main :: IO () main = do print firstTen As required the program terminates printing: [2,4,6,8,10,12,14,16,18,20] Now I present my 'conversion' of this trivial case where we both generate a random number, and add a random amount to it upon each iteration. Again we only wish to print the first 10: import System.Random -- Taken directly from function 'rollDice' in Haskell98 report randNum :: IO Int randNum = getStdRandom (randomR (1, 6)) addRand :: Int -> IO Int addRand x = do y <- randNum return (x + y) firstTen :: IO [Int] firstTen = do infiniteNums <- iterateM addRand randNum return (take 10 infiniteNums) main :: IO () main = do tenNums <- firstTen print tenNums -- Monadic interpretation of prelude iterate definition iterateM :: Monad m => (a -> m a) -> m a -> m [a] iterateM f xM = do x <- xM mcons xM (iterateM f (f x)) -- Taken from prelude definition of sequence mcons :: Monad m => m a -> m [a] -> m [a] mcons p q = p >>= \x -> q >>= \y -> return (x:y) However this latter case gets stuck in an infinite loop, terminating on a stack overflow. My question asks why this is the case, when laziness should ensure only the first 10 cases need to be computed. If anyone wishes to suggest another way entirely to approach this problem that would also be welcome! Many Thanks, Dave
Dave Tapley wrote:
This code show a trivial case where randomness (and hence the IO monad) is not used and the first 10 elements of the produced list are printed:
You don't need the IO monad to achieve pseudy-randomness. Why not use 'randoms' from System.Random (or 'randomRs' for a range). take 10 $ (randomRs (1,6) (mkStdGen 1)) :: [Int] You can use the IO monad to get a randomly seeded generator from the outside, but once seeded, just use the list. gen <- newStdGen take 10 $ (randomRs (1,6) gen) :: [Int] Dave
David Brown wrote:
Dave Tapley wrote:
This code show a trivial case where randomness (and hence the IO monad) is not used and the first 10 elements of the produced list are printed:
You don't need the IO monad to achieve pseudy-randomness. Why not use 'randoms' from System.Random (or 'randomRs' for a range).
take 10 $ (randomRs (1,6) (mkStdGen 1)) :: [Int]
The other possibility, which would work better in a non-toy problem, is to encapsulate the random numbers in a state monad. That way, rather than using the IO monad (with all its complexity) you can just have a monad of randomness (along with a Bag of Holding and a +2 sword). The trick is to use the split operation when you need to do something lazy. "split" forks the generator into two generators, so you can use one as the generator in your lazy stream and the other for the next step in your random computation. Or you could use "Gen" from Test.QuickCheck, which basically does this already. The Wikibook chapter on random numbers explains this. Paul.
On 3/1/07, Dave Tapley <dukedave@gmail.com> wrote:
My question asks why this is the case, when laziness should ensure only the first 10 cases need to be computed.
Basically, because the IO monad is strict, not lazy. If you want laziness, don't use the IO monad. -- Taral <taralx@gmail.com> "You can't prove anything." -- Gödel's Incompetence Theorem
On 01/03/07, Dave Tapley <dukedave@gmail.com> wrote:
My question asks why this is the case, when laziness should ensure only the first 10 cases need to be computed.
Just to clarify some of the other answers you've got. Saying the IO monad is strict isn't the whole picture, after all 'do {txt <- getContents; putStrLn $ transform txt}' doesn't read all the contents in before transforming it. The reason your program hangs is that you are trying to return an infinite list generated from an _infinite sequence of IO actions_. This example might help:
getList1, getList2, getList3 :: IO [Int] getList1 = return . repeat $ 0 getList2 = do {lst <- getList2; return $ 0 : lst} getList3 = sequence . repeat . return $ 0
main = do lst <- getList1 putStrLn . show . take 10 $ lst
getList1 will work in the lazy way that you expected. getList2 and getList3 are equivalent to each other and similar to your iterateM, they will loop forever. I hope this helps, - Joe
participants (5)
-
Dave Tapley -
David Brown -
Joe Thornber -
Paul Johnson -
Taral