On Thu, 8 Jul 2004, John Kozak wrote:
The root problem is that random number generation is inherently stateful, and so the familiar imperative idioms don't translate directly into a pure functional language. In a C-like language, each invocation of "rand()" mutates a secret piece of state lurking off-stage; pure functional code doesn't have the option of doing this.
Another way of thinking about/implementing it is to thread through the relevant state, eg: rand :: RandState -> (Int, RandState) where RandState is the state from which numbers are generated. Then, you must be careful to avoid reusing any particular RandState if you don't want to have repetitions. You can do pure I/O in this way too, where the threaded state is "the state of the world". Mercury does this; Hello World looks something like this: :- pred main(io:state, io:state). :- mode main(di, uo) is det. main(S1, S2) :- io:write_string("Hello, World!\n", S1, S2). Here io:state is the type of "the state of the world". It's really important that you don't reuse an old "state of the world" because it would rip holes in timespace. That's the point of the "mode" declaration... the "di" is short for "destructive input" and the "uo" for "unique output". They are "linear modes", which basically means the compiler won't let you reuse an io:state. If you have multiple I/O actions you have to thread the states correctly, viz: main(S1, S3) :- io:write_string("Hello, ", S1, S2). io:write_string("World!\n", S2, S3). If you write this: main(S1, S2) :- io:write_string("Hello, ", S1, S2). io:write_string("World!\n", S1, S2). the compiler will scream at you for trying to rip timespace by reusing S1. It's conceptually straightforward, but a bit fiddly, so Mercury has a couple of bits of syntactic sugar to make it nicer, which means you can write: main --> :- io:write_string("Hello, "). io:write_string("World!\n"). or main(!S) :- io:write_string("Hello, ", !S), io:write_string("World\n", !S). and the threading gets done automatically. And of course, the compiled code doesn't really thread any states-of-the-world around, it all disappears inside the compiler once the modes have been checked. I think Clean does a similar thing for I/O with its linear types. So it's similar to Haskell's IO monad, in that you end up with an "I/O shell" with side-effects around a pure program. It's different in that monads are a bit more powerful in general, and a zillion times harder to understand. Perhaps it's helpful to think about the IO monad as just a way of doing this state threading, or perhaps it just confuses things further. N ps: I might have got the module separator ':' wrong above -- "__" is a (horrible) alternative, '.' might be accepted now.