Search code examples
scalafunctional-programmingmonadsstate-monadflatmap

Implementation of flatMap() for State transition

Exercise 6.8, Chiusano and Bjarnason, Functional Programming in Scala, p. 87 asks how one might implement flatMap() for the following trait:

trait RNG {
  def nextInt: (Int, RNG)
}

type Rand[+A] = RNG => (A, RNG)

The answer key gives the following solution:

def flatMap[A,B](f: Rand[A])(g: A => Rand[B]): Rand[B] =
rng => {
  val (a, r1) = f(rng)
  g(a)(r1) // We pass the new state along
}

Stackoverflow provides many answers to flatMap()/monad questions, but none which for me answered my questions regarding the next to last line of code.

I do not understand the syntax of the line

g(a)(r1)

(1) I do not understand how g(a)(r1) evaluates. What syntactic function is served by (r1)? The line does not exemplify currying, I do not believe, since g takes only one argument: A. (2) If g(a) will already return the type Rand[B], then why does not the line end here? (3) what is the relation between the Rand[B] returned by g(a) and the second set of parentheses: (r1)? (4) if the return type of this implementation of flatMap() is Rand[B], which is equal to RNG => (A, RNG), how are the enclosing parentheses to the right of the arrow generated? If I had to guess I would say they are generated by the evaluation, (r1), but I do not really understand this code given my questions 1 through 3.

Solution

  • Remember that we're calling f and g inside a new anonymous function, as indicated by the line 

    rng => { ... }

    g returns a Rand[B] when given an A, so g(a) evaluates to a function from RNG to (A, RNG).

    So g(a) returns a function expecting an RNG as its argument, we can then call this with our r1, which is of type RNG.

    The result of the call is (B, RNG). Now since the flatMap signature expects you to return a Rand[B] which is the same as RNG => (B, RNG) and we return (B, RNG) inside our function, it exactly matches the signature.