SIMPLE random number generation

Question

I'm writing this after a good while of frustrating research, and I'm hoping someone here can enlighten me about the topic.

I want to generate a simple random number in a haskell function, but alas, this seems impossible to do without all sorts of non-trivial elements, such as Monads, asignation in "do", creating generators, etc.

Ideally I was looking for an equivalent of C's "rand()". But after much searching I'm pretty convinced there is no such thing, because of how the language is designed. (If there is, please someone enlighten me). As that doesn't seem feasible, I'd like to find a way to get a random number for my particular problem, and a general explanation on how it works to get a random number.

prefixGenerator :: (Ord a, Arbitrary a) => Gen ([a],[a])
prefixGenerator = frequency [ 
    (1, return ([],[])),
    (2, do {
            xs1 <- orderedListEj13 ;
            xs2 <- orderedListEj13 ;
            return (xs1,xs2)
       }),
    (2, do {                
            xs2 <- orderedListEj13 ;
            return ((take RANDOMNUMBERHERE xs2),xs2)
       })
    ]

I'm trying to get to grips with QuickCheck but my inability to use random numbers is making it hard. I've tried something like this (by putting an drawInt 0 (length xs2) instead of RANDOMNUMBERHERE)but I get stuck with the fact that take requires an Int and that method leaves me with a IO Int, which seems impossible to transform to an Int according to this.

Agnosia

Recall that Haskell is a language free of side effects. In simplified terms, this means that there cannot be a function such as C's rand that gives a pseudorandom number every time it's called. If rand is a pure Haskell function giving an Int, then it gives the same Int every time. What you can do, though, is make pure functions that take the state of the random number generator as input, and returns the next pseudorandom number and the new state of the generator. See System.Random – Lauzon

Followup: The IO monad, as you mention, only enters into use in the System.Random module when you want to manage a global random state, or for example initialize your generator with system entropy (this obviously requires interaction with the outside world). – Lauzon

Answer 1

As haskell is a pure functional programming language, functions are referentially transparent which means essentially that only a function's arguments determine its result. If you were able to pull a random number out of the air, you can imagine how that would cause problems.

I suppose you need something like this:

prefixGenerator :: (Ord a, Arbitrary a) => Gen ([a],[a])
prefixGenerator = do
  randn <- choose (1,999) -- number in range 1-999
  frequency [ 
    (1, return ([],[])),
    (2, do {
            xs1 <- orderedListEj13 ;
            xs2 <- orderedListEj13 ;
            return (xs1,xs2)
       }),
    (2, do {                
            xs2 <- orderedListEj13 ;
            return ((take randn xs2),xs2)
       })
    ]

In general in haskell you approach random number generation by either pulling some randomness from the IO monad, or by maintaining a PRNG that is initialized with some integer seed hard-coded, or pulled from IO (gspr's comment is excellent).

Reading about how pseudo random number generators work might help you understand System.Random, and this might help as well (scroll down to section on randomness).

Profligate

Note that Gen is a monad that (among other thing) store a random generator state so that you can get random number anywhere in a Gen action. So there is no real problems with randomness in quickcheck instances. Generally, beginners have difficulties in other contexts, where they have to put the necessary framework to use randomness in their algorithms (and often return to IO when they fail to use one of the better solutions). – Contorted

@Contorted : thanks, I didn't explain what was going on in my answer very well – Profligate

Answer 2

You're right in that nondeterministic random (by which I mean "pseudo-random") number generation is impossible without trickery. Functions in Haskell are pure which means that the same input will always produce the same output.

The good news is that you don't seem to need a nondeterministic PRNG. In fact, it would be better if your QuickCheck test used the same sequence of "random" numbers each time, to make your tests fully reproducible.

You can do this with the mkStdGen function from System.Random. Adapted from the Haskell wiki:

import System.Random
import Data.List

randomInts :: Int -> [Int]
randomInts n = take n $ unfoldr (Just . random) (mkStdGen 4)

Here, 4 is the seed that you may want to choose by a fair dice roll.

Bipack

Answer 3

The standard library provides a monad for random-number generation. The monadic stuff is not that hard to learn, but if you want to avoid it, find a pseudo-random function next that takes an Int to an Int in a pseudorandom way, and then just create and pass an infinite list of random numbers:

next :: Int -> Int
randoms :: [Int]
randoms = iterate next 73

You can then pass this list of random numbers wherever you need it.

Here's a linear congruential next from Wikipedia:

next n = (1103515245 * n + 12345) `mod` 1073741824

And here are the first 20 pseudorandom numbers following 73:

Prelude> take 20 $ iterate next 73
[73,25988430,339353199,182384508,910120965,1051209818,737424011,14815080,325218177,1034483750,267480167,394050068,4555453,647786674,916350979,980771712,491556281,584902142,110461279,160249772]

Cartography

Unfortunately, the standard library does not actually provide a monad for random number generation. The MonadRandom library does, though. – Nazarius

@Nazarius - unless things have changed recently System.Random comes with GHC so that makes it "standard" by most measures. – Alwitt

@stephentetley: System.Random does not define any monads. Indeed, the only occurrence of "monad" in its documentation is in the phrase "the IO monad". – Nazarius

@Nazarius - ah, indeed, System.Random equips the IO monad for random number generation. – Alwitt