Understanding Random monad in Scala

Question

This a follow-up to my previous question

Travis Brown pointed out that java.util.Random is side-effecting and suggested a random monad Rng library to make the code purely functional. Now I am trying to build a simplified random monad by myself to understand how it works.

Does it make sense ? How would you fix/improve the explanation below ?

Random Generator

First we plagiarize a random generating function from java.util.Random

 // do some bit magic to generate a new random "seed" from the given "seed" 
 // and return both the new "seed" and a random value based on it

 def next(seed: Long, bits: Int): (Long, Int) = ...

Note that next returns both the new seed and the value rather than just the value. We need it to pass the new seed to another function invocation.

Random Point

Now let's write a function to generate a random point in a unit square.

Suppose we have a function to generate a random double in range [0, 1]

 def randomDouble(seed: Long): (Long, Double) = ... // some bit magic

Now we can write a function to generate a random point.

def randomPoint(seed: Long): (Long, (Double, Double)) = {
   val (seed1, x) = randomDouble(seed)
   val (seed2, y) = randomDouble(seed1)
   (seed2, (x, y)) 
}

So far, so good and both randomDouble and randomPoint are pure. The only problem is that we compose randomDouble to build randomPoint ad hoc. We don't have a generic tool to compose functions yielding random values.

Monad Random

Now we will define a generic tool to compose functions yielding random values. First, we generalize the type of randomDouble:

type Random[A] = Long => (Long, A) // generate a random value of type A

and then build a wrapper class around it.

class Random[A](run: Long => (Long, A))

We need the wrapper to define methods flatMap (as bind in Haskell) and map used by for-comprehension.

class Random[A](run: Long => (Long, A)) {
  def apply(seed: Long) = run(seed)  

  def flatMap[B](f: A => Random[B]): Random[B] =
    new Random({seed: Long => val (seed1, a) = run(seed); f(a)(seed1)})

  def map[B](f: A => B): Random[B] =
    new Random({seed: Long = val (seed1, a) = run(seed); (seed1, f(a))})
}  

Now we add a factory-function to create a trivial Random[A] (which is absolutely deterministic rather than "random", by the way) This is a return function (as return in Haskell).

def certain[A](a: A) = new Random({seed: Long => (seed, a)})

Random[A] is a computation yielding random value of type A. The methods flatMap , map, and function unit serves for composing simple computations to build more complex ones. For example, we will compose two Random[Double] to build Random[(Double, Double)].

Monadic Random Point

Now when we have a monad we are ready to revisit randomPoint and randomDouble. Now we define them differently as functions yielding Random[Double] and Random[(Double, Double)]

def randomDouble(): Random[Double] = new Random({seed: Long => ... })
def randomPoint(): Random[(Double, Double)] =
  randomDouble().flatMap(x => randomDouble().flatMap(y => certain(x, y))

This implementation is better than the previous one since it uses a generic tool (flatMap and certain) to compose two calls of Random[Double] and build Random[(Double, Double)].

Now can re-use this tool to build more functions generating random values.

Monte-Carlo calculation of Pi

Now we can use map to test if a random point is in the circle:

def randomCircleTest(): Random[Boolean] = 
  randomPoint().map {case (x, y) => x * x + y * y <= 1} 

We can also define a Monte-Carlo simulation in terms of Random[A]

def monteCarlo(test: Random[Boolean], trials: Int): Random[Double] = ...

and finally the function to calculate PI

def pi(trials: Int): Random[Double] = ....

All those functions are pure. Side-effects occur only when we finally apply the pi function to get the value of pi.

Answer 1

Your approach is quite nice although it is a little bit complicated. I also suggested you to take a look at Chapter 6 of Functional Programming in Scala By Paul Chiusano and Runar Bjarnason. The chapter is called Purely Functional State and it shows how to create purely functional random generator and define its data type algebra on top of that to have full function composition support.