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.

This looks pretty good to me. I'd suggest writing val randomDouble = ... instead of def randomDouble() = ..., though, to emphasize that these are pure values—just computations with no side effects. — Travis Brown
Thank you. If I follow this logic I should write val randomPoint = ... instead of def randomPoint(), etc. since all functions are pure. Is it correct ? — Michael
Two points: using () on the def suggests that the method has side effects (just convention, but it makes sense to follow it). More importantly, using def instead of val means calling randomDouble twice in randomPoint constructs two Random instances, while you only need one. — Travis Brown
Thanks. You are right: randomPoint constructs two instances of Random[Double]. Good point ! :) I should fix it. — Michael
I guess I don't understand the point here. You can pass in a RNG to use and have it internally update state and avoid the twenty-fold performance penalty that this method gave in benchmarking on your other question. Aside from inner satisfaction that it is possible to make explicit every state change as an explicit parameter pass (which is a nice exercise to do to convince yourself that you can), what is the problem here that you are trying to solve? — Rex Kerr

Nami Nami · Accepted Answer · 2015-02-15T22:41:23

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.