Using streams for purely functional random number generation in Scala

The generation of (pseudo-)random numbers is a perfect example for the differences between imperative (object-oriented) and purely functional programming. Scala’s support for both of these programming paradigms means that we can translate between them. In this post we start with the imperative random number generation from the Scala standard library and wrap it up in a purely functional random number generator. This exemplifies how mutable objects can be used even in functional code if the mutability is not observable from the outside. The key is a lazy data structure that queries a private mutable object on demand.

Imperative random number generation

The scala standard library provides a random number generator in a class Random, offering methods like nextInt:

val rng = new scala.util.Random(seed = 42)
println(rng.nextInt); // -1170105035 
println(rng.nextInt); // 234785527
println(rng.nextInt); // -1360544799

As you see, subsequent calls to nextInt on a Random object produce different results. Therefore, the expression rng.nextInt is neither deterministic nor referentially transparent - we could not replace all occurrences of that expression with a memoized value. This is because calling nextInt has side effects - it mutates the internal state of the object rng.

Whereas this is the idiomatic way to express random number generation in imperative programming, purely functional programming avoids side effects and mutation in favor of determinism and referential transparency. You may now wonder whether it is possible to use an imperative random number generator like scala.util.Random in a purely functional program at all. The answer is yes.

Purely functional random number generation

A purely functional random number generator can be expressed in Scala as follows:

trait RNG {
    def nextInt: (RNG, Int)
}
val rng: RNG = mkRNG(seed = 42) // initialize with seed = 42
println(rng.nextInt); // (RNG(seed = 13), -1170105035) 
println(rng.nextInt); // (RNG(seed = 13), -1170105035) 
println(rng.nextInt); // (RNG(seed = 13), -1170105035) 

Now RNG objects are immutable and generating a random number returns a changed RNG object instead of mutating r. The expression rng.nextInt is deterministic and referentially transparent. Next we look into an implementation of the RNG trait that wraps an imperative random number generator.

Wrapping an imperative random number generator in a purely functional random number generator

The fundamental idea of the RNG trait that it contains some immutable state that allows generating a deterministic random number stream. One way to do this is to use the last generated number as the state and some mathemagical formula to produce the next state. However, we can also make the stream of random numbers explicit:

def mkRNG(seed: Long): RNG = StreamRNG(stream(seed))

case class StreamRNG(stream: LazyList[Int]) extends RNG {
    def nextInt: (RNG, Int) = (StreamRNG(stream.tail), stream.head)
}

def stream(seed: Long): LazyList[Int] = {
    val random = new Random(seed)
    def mkStream: LazyList[Int] = random.nextInt #:: mkStream
    mkStream
}

The important part is the function stream with its recursive inner function mkStream. It produces a lazily evaluated, deterministic stream of random numbers with a private, mutable scala.util.Random object. Elements of this stream are memoized, therefore the expression random.nextInt is only evaluated once per stream element.

A StreamRNG object points to a specific element in the stream, and to get the next random number we just return the head of the stream and use the tail as the new state. Different StreamRNG objects can point to different elements in the stream, but the overall sequence of elements is shared between them. In addition, the head of the stream gets garbage-collected if it is no longer accessible by any StreamRNG object.

Bonus: Wrapping a purely functional random number generator in an imperative random number generator

The reverse direction is easier.

class MyRandom(seed: Int) {
    var rng: RNG = mkRNG(seed)
    def nextInt: Int = {
        val (rng2, r) = rng.nextInt
        rng = rng2
        r
    }
}

Saving the current state in a var allows overriding it, restoring mutability.