Re: [Haskell] Laziness and the IO Monad (randomness)
[redirecting to haskell-cafe]
On 3/1/07, Dave Tapley
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.
You didn't say which function you had narrowed down the stack overflow to, but I suspect it's here:
firstTen :: IO [Int] firstTen = do infiniteNums <- iterateM addRand randNum return (take 10 infiniteNums)
In order for IO to work the way you'd expect, you have to be able to specify which IO operations happen in what order, which is exactly what a do-block within the IO monad specifies. But specifying the order of operations also means specifying in what order evaluation happens. So, the code you've written means "evaluate infiniteNums fully (in order that we might do whatever IO operations it involves before the return statement), then return the first 10 elements of its result." Since you're forcing evaluation of an infinite list, the program loops infinitely. If you find this counter-intuitive, you wouldn't be the first, but there's no other sensible interpretation for the code you've written. Deferring evaluation of infiniteNums in this case would mean that IO would happen in a strange and unpredictable order (or if it actually wouldn't, then the compiler isn't smart enough to know that.) I would solve this problem by writing a version of iterateM that takes the length of the desired list as an argument (e.g., 10 in your example), which sadly breaks modularity, but as I explained above, working within the IO monad necessitates that. Someone more l33t than me may be able to suggest a more elegant solution, though. Cheers, Kirsten -- Kirsten Chevalier* chevalier@alum.wellesley.edu *Often in error, never in doubt "They killed, they maimed, and they called information for numbers they could easily look up in the book." -- Woody Allen
Dave Tapley wrote:
However this latter case gets stuck in an infinite loop, terminating on a stack overflow.
Kirsten Chevalier said:
You didn't say which function you had narrowed down the stack overflow to, but I suspect it's here:
firstTen :: IO [Int] firstTen = do infiniteNums <- iterateM addRand randNum return (take 10 infiniteNums)
In order for IO to work the way you'd expect, you have to be able to specify which IO operations happen in what order, which is exactly what a do-block within the IO monad specifies. But specifying the order of operations also means specifying in what order evaluation happens. So, the code you've written means "evaluate infiniteNums fully (in order that we might do whatever IO operations it involves before the return statement), then return the first 10 elements of its result." Since you're forcing evaluation of an infinite list, the program loops infinitely.
I don't think the IO monad is to blame in this case. There's no reason that an IO action can't return a lazily generated list. For a trivial example: infM f i = return (iterate f i) runFooM = do inf <- infM succ 0 print $ take 10 inf The strictness of the IO monad depends on the IO primitives used. In particular, return is not strict in its argument. The real culprit here is iterateM, since it has to run the (infinitely recursive) tail action before it can return the cons of head and tail. There is no way around this, since the function being iterated is a monadic action. The only way for iterateM to return anything at all is for the head action to fail at some iteration. By "fail", I just mean any case where (>>=) returns without calling its second argument. For example, in the Maybe monad: Prelude> iterateM return (Just 42) *** Exception: stack overflow Prelude> iterateM return Nothing Nothing Unfortunately, failure at any iteration will mean failure altogether, and that means no list is returned. I suspect this would be true in any monad, though I don't know how to prove it. An example in the Maybe monad: testMaybe x | x > 0 = Just (x-1) testMaybe _ = Nothing Prelude> iterateM testMaybe (Just 42) Nothing In the IO monad, iterateM must result in either a runtime error, or an infinite loop leading to inevitable resource exhaustion. But the main point is that iterateM cannot be expected to return a lazily-generated list in any monad. The possible solutions are as suggested by Kirsten and David. If you use randomRs based on the global generator, be sure to use split or newStdGen to avoid accidentally reusing pseudo-random subsequences, for example: randomSequence :: (Random a) => (a,a) -> IO [a] randomSequence range = do gen <- newStdGen return (randomRs range gen) If you've made it this far, you might also want to take a look at MonadRandom and friends: http://haskell.org/haskellwiki/New_monads/MonadRandom
participants (2)
-
Kirsten Chevalier -
Matthew Brecknell