How to make stateful API's pure

user_17883396 0
Viewed 98

I'm learning functional programming partially by reading the book Functional Programming in Scala a.k.a. The Red Book and I've run into my first real blocker. In Chapter 6, The book uses the example of a random number generator to illustrate how to change state by using side effects. Then the book goes on to demonstrate the patterns you would typically encounter as well as some of the tangents you might take in making a functional stateful api. My problem comes when trying to understand the following code:

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

def map[A, B](s: Rand[A])(f: A => B): Rand[B] =
  rng => {
      val (nxt, nxtrng) = s(rng)
      (f(nxt), nxtrng)
  }

def nonNegativeLessThan(n: Int): Rand[Int] =
  map(nonNegativeIntv2) { i =>
    val mod = i % n
    if (i + (n - 1) - mod >= 0) mod else nonNegativeLessThan(n)(???)
  }

I hope this is enough context to get an idea what the code does. This is coming directly from the book on page 86. How does the if statement for method nonNegativeLessThan filters out values of i that are greater than the largest multiple of n in a 32 bit integer? Doesn't the recursive call in the else clause return a value of type Rand[Int]? In general I'm confused about what's going on in the code that is bolded. This is a pretty good book so I'm happy with how things are going so far and I feel I've learned a lot about functional programming. My apologies if this question is ill formed and if there is an issue with the formatting. This is my first post on stack overflow! Thank you to those who take a look at this and I hope it helps someone who has the same problem.

scala functional-programming
2 Answers

Imagine that you have a new domain of a set of integers, for example 0 to 11. The Rand type represents an aleatory number in that domain, but this type can not be skewed. That means that there can not be numbers that have a greater probability of being generated that others.

If you want to generate a number that is positive and less than four, you can use the map function of the Rand type, that allows to transform the result of a state action. First, it generates a nonnegative number and transform the result, via the map, applying the anonymous function: _ % n to obtain a number less than n.

def nonNegativeLessThan(n: Int): Rand[Int] =
  map(nonNegativeInt) { _ % n }

It uses the modulo operation:

scala> 1 % 4
res0: Int = 1

scala> 2 % 4
res1: Int = 2

scala> 3 % 4
res2: Int = 3

scala> 4 % 4
res3: Int = 0

scala> 5 % 4
res4: Int = 1

scala> 6 % 4
res5: Int = 2

scala> 7 % 4
res6: Int = 3

scala> 8 % 4
res7: Int = 0

scala> 9 % 4
res8: Int = 1

scala> 10 % 4
res9: Int = 2

As you can see, the largest multiple of 4 in this domain is 8, so if the non-negative number that is generated is 9 or 10, we have a problem. The probability of having a 1 or 2 is greater than having a 3 or a 0. And for that reason, the other implementation detects that the number which is first generated as a result of the nonnegativeInt is not major than the largest multiple of n in a specific domain, the Int32 numbers domain in the book, to have a non- biased generator.

And yes, that book is amazing.

user_68021560

How does the if statement for method nonNegativeLessThan filters out values of i that are greater than the largest multiple of n in a 32 bit integer?

If i is greater than the largest multiple of n, then i + (n - 1) - mod will overflow and yield a negative number. The subsequent >= 0 is then false.

Doesn't the recursive call in the else clause return a value of type Rand[Int]?

Well, nonNegativeLessThan(n) is indeed of type Rand[Int]. However it says nonNegativeLessThan(n)(???), that is, it applies nonNegativeLessThan to n, and then it applies the resulting value (of type Rand[Int], which is a function type) to ???, and that yields an Int. Or rather it would do that if ??? ever yielded real value, which it doesn't.

The problem here is that you would have to pass the state of the RNG instead of ???, but the map function doesn't let you access that state. You'll need flatMap to solve this – presumably that's what the book is going to discuss next.

user_55820280
Related