This library deals with the common task of pseudo-random number generation.

This module provides type classes and instances for the following concepts:

Monadic pseudo-random number generators

StatefulGen is an interface to monadic pseudo-random number generators.

Monadic adapters

StateGenM, AtomicGenM, IOGenM, STGenM and TGenM turn a RandomGen instance into a StatefulGen instance.

Drawing from a range

UniformRange is used to generate a value of a type uniformly within a range.

This library provides instances of UniformRange for many common numeric types.

Drawing from the entire domain of a type

Uniform is used to generate a value of a type uniformly over all possible values of that type.

This library provides instances of Uniform for many common bounded numeric types.

In monadic code, use the relevant Uniform and UniformRange instances to generate pseudo-random values via uniformM and uniformRM, respectively.

As an example, rollsM generates n pseudo-random values of Word in the range [1, 6] in a StatefulGen context; given a monadic pseudo-random number generator, you can run this probabilistic computation as follows:

>>> :{
let rollsM :: StatefulGen g m => Int -> g -> m [Word]
    rollsM n = replicateM n . uniformRM (1, 6)
in do
    monadicGen <- MWC.create
    rollsM 10 monadicGen :: IO [Word]
:}
[3,4,3,1,4,6,1,6,1,4]

Given a pure pseudo-random number generator, you can run the monadic pseudo-random number computation rollsM in an IO or ST context by applying a monadic adapter like AtomicGenM, IOGenM or STGenM (see monadic-adapters) to the pure pseudo-random number generator.

>>> :{
let rollsM :: StatefulGen g m => Int -> g -> m [Word]
    rollsM n = replicateM n . uniformRM (1, 6)
    pureGen = mkStdGen 42
in
    newIOGenM pureGen >>= rollsM 10 :: IO [Word]
:}
[1,1,3,2,4,5,3,4,6,2]

Pseudo-random number generators come in two flavours: pure and monadic.

RandomGen: pure pseudo-random number generators

See System.Random module.

StatefulGen: monadic pseudo-random number generators

These generators mutate their own state as they produce pseudo-random values. They generally live in ST or IO or some transformer that implements PrimMonad.

Pure pseudo-random number generators can be used in monadic code via the adapters StateGenM, AtomicGenM, IOGenM, STGenM and TGenM

• StateGenM can be used in any state monad. With strict StateT there is no performance overhead compared to using the RandomGen instance directly. StateGenM is not safe to use in the presence of exceptions and concurrency.
• AtomicGenM is safe in the presence of exceptions and concurrency since it performs all actions atomically.
• IOGenM is a wrapper around an IORef that holds a pure generator. IOGenM is safe in the presence of exceptions, but not concurrency.
• STGenM is a wrapper around an STRef that holds a pure generator. STGenM is safe in the presence of exceptions, but not concurrency.
• TGenM is a wrapper around a TVar that holds a pure generator. TGenM can be used in a software transactional memory monad STM. It is not as performant as AtomicGenM, but it can provide stronger guarantees in a concurrent setting.

This library provides two type classes to generate pseudo-random values:

• UniformRange is used to generate a value of a type uniformly within a range.
• Uniform is used to generate a value of a type uniformly over all possible values of that type.

Types may have instances for both or just one of UniformRange and Uniform. A few examples illustrate this:

• Int, Word16 and Bool are instances of both UniformRange and Uniform.
• Integer, Float and Double each have an instance for UniformRange but no Uniform instance.
• A hypothetical type Radian representing angles by taking values in the range [0, 2π) has a trivial Uniform instance, but no UniformRange instance: the problem is that two given Radian values always span two ranges, one clockwise and one anti-clockwise.
• It is trivial to construct a Uniform (a, b) instance given Uniform a and Uniform b (and this library provides this tuple instance).
• On the other hand, there is no correct way to construct a UniformRange (a, b) instance based on just UniformRange a and UniformRange b.

Typically, a monadic pseudo-random number generator has facilities to save and restore its internal state in addition to generating pseudo-random numbers.

Here is an example instance for the monadic pseudo-random number generator from the mwc-random package:

instance (s ~ PrimState m, PrimMonad m) => StatefulGen (MWC.Gen s) m where
  uniformWord8 = MWC.uniform
  uniformWord16 = MWC.uniform
  uniformWord32 = MWC.uniform
  uniformWord64 = MWC.uniform
  uniformShortByteString n g = unsafeSTToPrim (genShortByteStringST n (MWC.uniform g))

instance PrimMonad m => FrozenGen MWC.Seed m where
  type MutableGen MWC.Seed m = MWC.Gen (PrimState m)
  thawGen = MWC.restore
  freezeGen = MWC.save

FrozenGen

FrozenGen gives us ability to use any stateful pseudo-random number generator in its immutable form, if one exists that is. This concept is commonly known as a seed, which allows us to save and restore the actual mutable state of a pseudo-random number generator. The biggest benefit that can be drawn from a polymorphic access to a stateful pseudo-random number generator in a frozen form is the ability to serialize, deserialize and possibly even use the stateful generator in a pure setting without knowing the actual type of a generator ahead of time. For example we can write a function that accepts a frozen state of some pseudo-random number generator and produces a short list with random even integers.

>>> import Data.Int (Int8)
>>> :{
myCustomRandomList :: FrozenGen f m => f -> m [Int8]
myCustomRandomList f =
  withMutableGen_ f $ \gen -> do
    len <- uniformRM (5, 10) gen
    replicateM len $ do
      x <- uniformM gen
      pure $ if even x then x else x + 1
:}

and later we can apply it to a frozen version of a stateful generator, such as STGen:

>>> print $ runST $ myCustomRandomList (STGen (mkStdGen 217))
[-50,-2,4,-8,-58,-40,24,-32,-110,24]

or a Seed from mwc-random:

>>> import Data.Vector.Primitive as P
>>> print $ runST $ myCustomRandomList (MWC.toSeed (P.fromList [1,2,3]))
[24,40,10,40,-8,48,-78,70,-12]

Alternatively, instead of discarding the final state of the generator, as it happens above, we could have used withMutableGen, which together with the result would give us back its frozen form. This would allow us to store the end state of our generator somewhere for the later reuse.

The UniformRange instances for Float and Double use the following procedure to generate a random value in a range for uniformRM (a, b) g:

If \(a = b\), return \(a\). Otherwise:

1. Generate \(x\) uniformly such that \(0 \leq x \leq 1\).

   The method by which \(x\) is sampled does not cover all representable floating point numbers in the unit interval. The method never generates denormal floating point numbers, for example.

2. Return \(x \cdot a + (1 - x) \cdot b\).

   Due to rounding errors, floating point operations are neither associative nor distributive the way the corresponding operations on real numbers are. Additionally, floating point numbers admit special values NaN as well as negative and positive infinity.

For pathological values, step 2 can yield surprising results.

• The result may be greater than max a b.

  >>> :{
  let (a, b, x) = (-2.13238e-29, -2.1323799e-29, 0.27736077)
      result = x * a + (1 - x) * b :: Float
  in (result, result > max a b)
  :}
  (-2.1323797e-29,True)
  

• The result may be smaller than min a b.

  >>> :{
  let (a, b, x) = (-1.9087862, -1.908786, 0.4228573)
      result = x * a + (1 - x) * b :: Float
  in (result, result < min a b)
  :}
  (-1.9087863,True)
  

What happens when NaN or Infinity are given to uniformRM? We first define them as constants:

>>> nan = read "NaN" :: Float
>>> inf = read "Infinity" :: Float

• If at least one of \(a\) or \(b\) is NaN, the result is NaN.

  >>> let (a, b, x) = (nan, 1, 0.5) in x * a + (1 - x) * b
  NaN
  >>> let (a, b, x) = (-1, nan, 0.5) in x * a + (1 - x) * b
  NaN
  

• If \(a\) is -Infinity and \(b\) is Infinity, the result is NaN.

  >>> let (a, b, x) = (-inf, inf, 0.5) in x * a + (1 - x) * b
  NaN
  

• Otherwise, if \(a\) is Infinity or -Infinity, the result is \(a\).

  >>> let (a, b, x) = (inf, 1, 0.5) in x * a + (1 - x) * b
  Infinity
  >>> let (a, b, x) = (-inf, 1, 0.5) in x * a + (1 - x) * b
  -Infinity
  

• Otherwise, if \(b\) is Infinity or -Infinity, the result is \(b\).

  >>> let (a, b, x) = (1, inf, 0.5) in x * a + (1 - x) * b
  Infinity
  >>> let (a, b, x) = (1, -inf, 0.5) in x * a + (1 - x) * b
  -Infinity
  

Note that the GCC 10.1.0 C++ standard library, the Java 10 standard library and CPython 3.8 use the same procedure to generate floating point values in a range.

1. Guy L. Steele, Jr., Doug Lea, and Christine H. Flood. 2014. Fast splittable pseudorandom number generators. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications (OOPSLA '14). ACM, New York, NY, USA, 453-472. DOI: https://doi.org/10.1145/2660193.2660195