# Randomness in purely functional programs

## Monads of randomness

In Haskell, the standard way to write programs with randomness, like other effects, is to use a monad. The `MonadRandom`

type class, from the package^{1} of the same name, is a monadic interface to access a source of randomness.

Here is a simplified version. It consists of a single method to get a random integer. More randomness can be obtained by just calling this multiple times.

A simple implementation wraps a pseudo-random number generator in a state monad. Let us first leave the PRNG abstract.

As a monad, it just threads the PRNG through the program.

```
instance Monad (StateGen g) where
return a = StateGen $ \g -> (g, a)
m >>= f = StateGen $ \g ->
let (g', a) = runStateGen m g in runStateGen (f a) g'
instance Functor (StateGen g) where fmap = liftM
instance Applicative (StateGen g) where pure = return ; (<*>) = ap
```

We assume that the PRNG provides a `next`

function, which outputs some random value and an updated state.

Then `genInt`

is trivially implemented by `next`

.

This implementation has one issue: when we compose two random computations, like with `(>>=)`

, we must run the first one to get the intermediate state `g'`

, before passing it to the second one, even if it didn’t depend on the former.

Surely, if I have two independent thunks `(<thunk>, <thunk>)`

, random or not, and I end up needing only the second one, then I shouldn’t need to pay for the first one. This is just laziness.

### Splittable PRNG

A `next`

-based sequential PRNG is definitely not compatible with laziness. What we need is a *splittable* PRNG^{2}. It consists of one method to *split* the state, and another to *extract* a random value from it.

Note that a SPRNG is also a sequential PRNG.

But a SPRNG can be encapsulated in a different way from `StateGen`

. We do not have to thread a PRNG state anymore. We are left with a simple function `g -> a`

, but the `SPRNG`

constraint now moves into the `Monad`

instance, to allow splitting the generator between two computations.

```
data SplitGen g a = SplitGen { runSplitGen :: g -> a }
instance SPRNG g => Monad (SplitGen g) where
return a = SplitGen $ \_ -> a
m >>= f = SplitGen $ \g ->
let (gm, gf) = split g in
runSplitGen (f (runSplitGen m gm)) gf
instance SPRNG g => Functor (SplitGen g) where fmap = liftM
instance SPRNG g => Applicative (SplitGen g) where pure = return ; (<*>) = ap
```

Getting a random value is still straightforward.

In QuickCheck^{3}, the `Gen`

monad is thus based on a splittable PRNG for efficient testing of non-strict properties.

## Beyond monads

In Haskell, we usually compose effectful computations *explicitly monadically*. In particular, the explicitness is sometimes nice, but it also gets in the way of clarity and simplicity. If I want to add the results of throwing two die, I would like to write `die + die`

. A very nice compromise seems reachable with *algebraic effects*^{4}: effects are still tracked in types, but effectful computations do not need special notation. Unfortunately I’m not sure that technique applies to the method using splittable PRNGs.

Anyway, let’s try to do things manually to see how they could be improved. We represent random values explicitly as functions `g -> a`

.

```
then_ :: SPRNG g => (g -> a) -> (a -> g -> b) -> g -> b
(m `then_` f) g = f (m gm) gf
where
(gm, gf) = split g
```

Doing this explicitly is risky: we may forget to split, passing `g`

to both functions (`f (m g) g`

); if we remember to split, we might still accidentally pass `gm`

or `gf`

twice, breaking independence (`f (m gm) gm`

). We could prevent this kind of mistake with a *linear type system* allowing us to express the constraint that a generator must be used at most once.

Even if it were properly checked, splitting and passing generators around explicitly becomes boring work quickly, and `SplitGen`

had precisely the advantage of making this implicit, but a monadic style adds some amount of overhead compared to simply applying pure functions. This is what an ideal imaginary alternative might look like:

It is similar to `ImplicitParams`

, but instead of simply passing the implicit parameter `?g`

when calling random functions in the body, `?g`

should be split with each component passed to each call requiring a generator.

The compiler would have to treat these constraints about generators specially. This certainly seems quite *ad hoc*. I have the idea that this may not need to be a special case. In Haskell, users can already define certain kinds of custom constraints and associated rules via type classes, and the resolution of these constraints according to those rules automatically generates code, so that the user doesn’t need to write it. Could this be generalized to obtain the aforementioned behavior for implicit splitting generators?

Roughly, I would like to define new sorts of rules on constraints in a richer language than Haskell’s Prolog-like type classes, in order to finely control the resolution process and the code generation derived from it (i.e., the desugaring to dictionary passing). At some level, this sounds very much like a static analogue of effect handlers: typechecking code generates various kinds of constraints, and one might write *handlers* to resolve them.

## Appendix: Examples of PRNG

### Pseudo-random number generator

I will not go into details about the formal requirements for such an object, but here is a simple example of PRNG. We assume a `hash`

function given as a primitive.

The state consists of the initial seed and a counter.

```
type Seed = Int
data G0 = G0 { seed0 :: Seed, counter0 :: Int }
newG0 :: Seed -> G0
newG0 seed = G0 seed 0
```

Then, `next`

hashes the pair, yielding a pseudo-random value, and increments the counter.

### Splittable PRNG

Rather than hashing the seed with a counter of how many times `next`

was called, we will hash it with the information of how a generator was obtained from `split`

. The seed can be associated with an infinite binary tree of random values. A generator state is a position in the tree, we start at the root.

Then `split`

outputs two positions one level deeper in the tree. A position in a binary tree is given by a list of booleans describing the path from the root to that position. We hash the seed and the path to obtain a pseudo-random value.

```
instance SPRNG G1 where
split (G1 seed path) = (G1 seed (False : path), G1 seed (True : path))
extract (G1 seed path) = hash (seed, path)
```

*Splittable Pseudorandom Random Number Generators using Cryptographic Hashing*, K. Claessen, M. Palka, Haskell Symposium 2013 (link).↩Here are three languages with algebraic effects:

- Eff: http://www.eff-lang.org/
- Frank: https://arxiv.org/abs/1611.09259
- Koka: https://github.com/koka-lang/koka

The latter two were presented at POPL2017.↩