Random Number Generator

Let's crack open a pseudo-random number generator to see how it works. Random number generators in imperative languages usually produce a repeatable sequence with this computation:

prime old_number with seed

function random
  new_number = (multiplier * old_number + offset) % max
  remember new_number as old_number for next call

The next random new_number is generated by applying some arithmetic to the previously generated old_number. The first time the random function is called, there is no previous number, and the generator's seed is used instead. This method of computing random numbers is called linear congruence. It's linear because there's a linear function, and it's a congruence because the modulus operation reduces different numbers to the same remainder.

Linear congruence produces a predictable and repeatable sequence of random numbers. To generate the same random sequence at a later time, we merely supply the same seed, multiplier, offset, and maximum.

Linear congruence requires a memory of the most recent number. Remembering that number seems like a good job for a variable that persists between calls—perhaps a global, static, or instance variable. We could implement our own random number generator with this Ruby code that uses a global hash:

$state = {previous: seed}

def random
  number = (multiplier * $state[:previous] + offset) % max
  $state[:previous] = number
  return number
end

Can we write this in Haskell? No, because we wouldn't be able to read from and assign to the global $state in a pure function. However, we have another option. We could move the state from an implicit global to an explicit parameter and return value, as is done in this modified Ruby implementation:

def random(state)
  number = (multiplier * state[:previous] + offset) % max
  newState = {previous: number}.freeze
  return [number, newState]
end

The function reads the old number from the state hash. Then it records the new number in a new state hash that it returns for future calls. The random function is now pure. This is how we would generate the first three random numbers in the sequence:

state0 = {previous: seed}.freeze
a, state1 = random(state0)
b, state2 = random(state1)
c, state3 = random(state2)
...

The caller receives both the random number and the new state. The new state is passed along to the next call. Thus we have a pure random number generator. Instead of mutating a single state variable, it creates a new version of the state for each function call.

Moving state from globals to parameters is the magic that allows for stateful code when we only have pure functions. But do we really want to use this technique if we have to actively receive and pass along the state? The Haskell designers didn't think we would, so they added a feature called do notation that automatically threads the state along for us. This main function is assigned a do block that behaves like the pure Ruby program:

main = do
  a <- random
  b <- random
  c <- random

It looks like a conventional imperative program. Under the hood, though, the Haskell compiler turns the statements into a chain of function calls. The state implicitly returned from one call is implicitly passed along as a parameter to the next call. But we don't see this state parameter mentioned anywhere in the code like we did in the equivalent Ruby program.

The function random is technically pure because its behavior only relies on the parameters it is given. However, Haskell developers still affix the label impure to functions if they rely on the implicit state that the do syntax passes around.