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.

Koumis

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. – Nikolaus

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 ? – Koumis

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. – Nikolaus

Thanks. You are right: randomPoint constructs two instances of Random[Double]. Good point ! :) I should fix it. – Koumis

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? – Ahmed

@RexKerr The point is to learn about RNG rather than just calculate Pi with Monte-Carlo. Does it make sense ? Do you think the RNG approach ("random" monad) is useful ? – Koumis

@RexKerr Your comment made me wonder when PRG (or another approach based on a random monad) is useful and practical. It is probably not practical to calculate Pi. So what is the minimal example, where is PRG is useful more than the obvious straightforward side-effecting approach ? I will probably ask it as a separate question on SO. – Koumis

@Koumis - As someone who has used RNGs extensively for decades, I can think of precisely zero cases where anything would have been aided by having a monad aside from some extra bookkeeping that I don't want to do explicitly (and that's assuming it were no slower!). I grant that there could be some cases where the exact weaving of the random number stream through the code becomes exquisitely important, but in practice I've never found one (including in a stochastic reaction-diffusion simulator where reproducibility given a certain seed or set thereof was essential). – Ahmed

@RexKerr Thank your comments. I will think about it. – Koumis

@Koumis - While thinking, note that I tend to do a lot of computation-heavy usage of RNGs. That may color my perspective a bit. – Ahmed

@RexKerr the monad structure makes it very easy to test (it's kind of enforced "dependency injection") and enforces that the exact weaving is deterministic, meaning reproducibility based on a particular seed is enforced by the compiler. It also makes it very clear which of your higher-level methods use random input and which are deterministic, because whether a particular method uses randomness is right there in the method type. – Anthology

@Anthology - Why would I want it in the method type instead of the method signature, or the identity of the class? (Also, dependency injection is good at hiding what things depend on, not making all your types reflect what things depend on.) – Ahmed

@RexKerr why as a type rather than the method or class name? The same reasons for using type safety anywhere. Why a monadic return type rather than a method parameter? for/yield composition, and all the libraries that operate on generic Monads. ((DI is fundamentally about saying a class' dependencies should be injected into that class from outside, not constructed or located by the class itself)) – Anthology

@Anthology - This isn't the place for an extended discussion, so I will just state that I haven't found any of those things needed or helpful in this particular context. I think code examples would be needed to have any hope of making progress. – Ahmed

@RexKerr Interestingly one of the examples in the Functional Programming in Scala book is monadic random generators (chapter 6). One of the use cases were to generate (reproducible) test cases, though probably without them those could also be easily implemented. – Halpin

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.

Furtive