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.
