# 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.