How do I generate a random number using functional state?

Question

I'm struggling to figure out how to merge a functional representation of State with Scala's Random class to generate random integers. I'm studying from the book Functional Programming in Scala, and so most of the code is taken from there.

Here's what the State class looks like, directly from the book:

case class State[S, +A](run: S => (A, S))

And here's what I want to do:

object State {
  type Rand[A] = State[A, Random] // the Random from scala.util.Random

  def nextIntInRange(from: Int, to: Int): Rand[Int] =
  ??? _.nextInt(from - to) + from ??? // unsure about much of this

  def get(a: Rand[A]): A = ??? // also unsure; should modify state

  def getAndPreserveState(a: Rand[A]): A = ??? // ditto; should not modify state

  def diceRolls(n: Int) = {
    val roll = nextIntInRange(1, 6) 
    go(n: Int, acc: List[Int]): List[Int] = {
      if (n >= 0) go(n-1, get(roll) :: acc) else acc
    }
    go(n, List())
  }

I've spent hours trying to figure out how to work with State's constructor, and have yet to achieve what I want, hence the near-total lack of understanding on how to implement those first three methods.

My goal is to be able to use diceRolls with any sized integer and for any given starting seed and generate a list of integers that does not ever change. In other words, diceRolls(3) might be List(3,3,2), and if so, rewriting it as diceRolls(7).take(3) must result again in List(3,3,2), and so on.

Answer 1

We want to generate random numbers and keep the random number generator (as of now RNG) (of type scala.util.Random) as state in your State class.

We can define the type Rand[A] as :

type Rand[A] = State[Random, A]

We want to be able to get a random integer in a range. If we have a RNG, this can easily be done using :

def randomInRange(rng: Random, start: Int, end: Int) = 
  rng.nextInt(end - start + 1) + start

randomInRange(new Random(1L), 10, 20) // Int = 14

But we want to use the RNG from a previous state, so we define a State with the same code in the run function :

def nextIntInRange(from: Int, to: Int): Rand[Int] = 
  State((r: Random) => (r.nextInt(to - from + 1) + from, r))

Our nextIntInRange function returns a random number and the RNG. Lets define roll to test it :

val roll = nextIntInRange(1, 6)

val rng = new Random(1L)
val (one, rng2) = roll.run(rng)
// (Int, scala.util.Random) = (4,scala.util.Random@5fb84db9)
val (two, rng3) = roll.run(rng2)
// (Int, scala.util.Random) = (5,scala.util.Random@5fb84db9)

So far so good we might think, but if we use rng two times we would like to receive the same random number:

val rng = new Random(1L)
val (one, _) = roll.run(rng) // 4
val (two, _) = roll.run(rng) // 5

We got two different numbers, that's not what we want when we use State. We would like that a roll using the same RNG returns the same result. The problem is that Random mutates its internal state, so we can't put the subsequent state changes in State.

In Functional Programming in Scala this problem is solved by defining a new random number generator, which also returns it state on nextInt.

Although using Random defeats the purpose of using State, we can try to implement the rest of the functions as an educational exercise.

Lets take a look at get and getAndPreserveState:

def get(a: Rand[A]): A = ??? // also unsure; should modify state

def getAndPreserveState(a: Rand[A]): A = ??? // ditto; should not modify state

If we look at the type signatures, we need to pass a Rand[A] like our roll function and return the result of this function. These function are strange because of a couple of reasons :

• Our roll function needs a Random instance to get a result, but we have no parameter of type Random.
• The return type is A, so if we had a Random instance we could return only the random number after calling a.run(ourRng), but what should we do with our state. We want to keep our state explicitly around.

Lets leave these function who are trying to loose our precious state behind and implement the final function diceRolls, in which we want to roll a dice a couple of times and return a list of the random numbers. The type of this function would thus be Rand[List[Int]].

We already have a function roll, now we need to use it multiple times, which we could do with List.fill :

List.fill(10)(roll) // List[Rand[Int]] 

However the resulting type is List[Rand[Int]] and not Rand[List[Int]]. Converting from F[G[_]] to G[F[_]] is an operation generaly called sequence, lets implement it directly for State :

object State {

  def sequence[A, S](xs: List[State[S, A]]): State[S, List[A]] = {
    def go[S, A](list: List[State[S, A]], accState: State[S, List[A]]): State[S, List[A]] = 
      list match { 
        // we have combined all States, lets reverse the accumulated list
        case Nil => 
          State((inputState: S) => {
            val (accList, state) = accState.run(inputState)
            (accList.reverse, state)
          })
        case stateTransf :: tail => 
          go(
            tail,
            State((inputState: S) => {
              // map2
              val (accList, oldState) = accState.run(inputState) 
              val (a, nextState) = stateTransf.run(oldState)
              (a :: accList, nextState) 
            })
          )
      }
    // unit
    go(xs, State((s: S) => (List.empty[A], s)))
  }

}

Some explanation for our case with Rand[Int] :

// use the RNG in to create the previous random numbers
val (accList, oldState) = accState.run(inputState)
// generate a new random number 
val (a, nextState) = stateTransf.run(oldState)
// add the randomly generated number to the already generated random numbers
// and return the new state of the RNG
(a :: accList, nextState) 

My implementation of State.sequence can be cleaned up considerably by defining a unit and a map2 function like they have done in the fpinscala answers on github.

Now we can define our diceRolls function as :

def diceRolls(n: Int) = State.sequence(List.fill(n)(roll))

Which we can use as :

diceRolls(5).run(new Random(1L))
// (List[Int], scala.util.Random) = (List(4, 5, 2, 4, 3),scala.util.Random@59b194af)