Scala Functional Design & Programming - Chapter 6 (6)
I bought "Scala Functional Design & Programming - A Comprehensive Guide to Functional Programming by Scalaz Contributors".
I'll read it bit by bit and summarize each chapter's content.
This time, it's Chapter 6. This chapter discusses how to handle state in functional programming.
The question that comes to mind is, "How can we handle state in a purely functional way?"
The answer is to pass the state as an argument and return it, just like we did with lists.
6 Chapter
This chapter explains how to handle state.
The first exercise is to create a function that generates a non-negative integer using nextInt.
Create a function that returns a non-negative integer using
nextInt. Note that ifnextIntreturnsInt.MinValue, we need to handle it as a special case.
We can handle negative numbers by adding 1 to them, making all numbers in the range [0, Int.MaxValue] appear twice.
def nonNegativeInt(rng: RNG): (Int, RNG) = {
val (i, next) = rng.nextInt
if(i < 0)
(-(i + 1), next)
else
(i, next)
}
Create a function that returns a
Doublevalue in the range [0, 1).
def double(rng: RNG): (Double, RNG) = {
val (i, next) = nonNegativeInt(rng)
(i.toDouble / (Int.MaxValue.toDouble +1), next)
}
Create a function that returns a tuple with various types.
def intDouble(rng: RNG): ((Int,Double), RNG) = {
val (i1, r1) = rng.nextInt
val (d2, r2) = double(r1)
((i1, d2), r2)
}
def doubleInt(rng: RNG): ((Double,Int), RNG) = {
val ((i1, d1), next) = intDouble(rng)
((d1, i1), next)
}
def double3(rng: RNG): ((Double,Double,Double), RNG) = {
val (d1, r1) = double(rng)
val (d2, r2) = double(r1)
val (d3, r3) = double(r2)
((d1, d2, d3), r3)
}
When I thought it was getting tedious to write so much code, the next exercise appeared.
Create a function that generates a list of random integers.
def ints(count: Int)(rng: RNG): (List[Int], RNG) = {
@tailrec
def loop(n: Int, acc: List[Int], r: RNG): (List[Int], RNG) = {
n match {
case 0 => (acc, r)
case _ =>
val (i, nr) = r.nextInt
loop(n-1, i :: acc, nr)
}
}
loop(count, List.empty[Int], rng)
}
Here, the Rand[+A] type is introduced, which takes an RNG and returns a value and the next RNG.
This type is convenient for handling random number generation.
Implement
mapusingRand.
// before
def double(rng: RNG): (Double, RNG) = {
val (i, next) = nonNegativeInt(rng)
(i.toDouble / (Int.MaxValue.toDouble +1), next)
}
// after
def mapDouble: Rand[Double] =
map(nonNegativeInt)(_.toDouble / (Int.MaxValue.toDouble +1))
It's much simpler now.
Next, we're told to implement map2, which combines two Rand actions.
Implement
map2.
def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
rng => {
val (a, rng2) = ra(rng)
val (b, rng3) = rb(rng2)
(f(a, b), rng3)
}
The implementation is simple.
[Difficult] Implement
sequenceto combine a list of state transitions into one.
I was stuck on this problem, but the answer was simple.
We can use Rand to implement sequence.
def _sequence[A](fs: List[Rand[A]]): Rand[List[A]] = {
rng => {
fs.foldRight((List.empty[A], rng))((x, acc) => {
val (a, r2) = x(acc._2)
(a :: acc._1, r2)
})
}
}
def sequence[A](fs: List[Rand[A]]): Rand[List[A]] =
fs.foldRight(unit(List[A]()))((x, acc) => map2(x, acc)(_ :: _))
def intsSeq(count: Int): Rand[List[Int]] =
sequence(List.fill(count)(int))
The RNG is being hidden more and more.
Next, we're told to implement flatMap and use it to implement nonNegativeLessThan.
Implement
flatMapand use it to implementnonNegativeLessThan.
def flatMap[A,B](f: Rand[A])(g: A => Rand[B]): Rand[B] = {
rng => {
val (a, r) = f(rng)
g(a)(r)
}
}
def nonNegativeLessThan(n: Int): Rand[Int] = {
flatMap(nonNegativeInt)(i => {
val mod = i % n
if(i + (n-1) - mod >= 0)
unit(mod)
else
nonNegativeLessThan(n)
})
}
The state transitions are being automated.
In the next problem, we're told to reimplement map and map2 using flatMap.
Reimplement
mapandmap2usingflatMap.
def map[A,B](s: Rand[A])(f: A => B): Rand[B] =
flatMap(s)(i => unit(f(i)))
def map2[A,B,C](ra: Rand[A], rb: Rand[B])(f: (A, B) => C): Rand[C] =
flatMap(ra)(a => map(rb)(b => f(a, b)))
It's much simpler now.
Next, the State type is introduced to generalize state transitions.
Generalize
unit,map,map2,flatMap, andsequenceusingState.
I had to peek at the answer because it was difficult.
case class State[S,+A](run: S => (A, S)) {
def map[B](f: A => B): State[S, B] =
flatMap(a => State.unit(f(a)))
def map2[B,C](sb: State[S, B])(f: (A, B) => C): State[S, C] =
flatMap(a => sb.map(b => f(a,b)))
def flatMap[B](f: A => State[S, B]): State[S, B] =
State(s => {
val (a, s2) = run(s)
f(a).run(s2)
}
)
}
object State {
type Rand[A] = State[RNG, A]
def unit[S,A](a: A): State[S, A] = State(s => (a, s))
def sequence[S,A](fs: List[State[S, A]]): State[S, List[A]] =
fs.foldRight(unit[S, List[A]](List()))((x, acc) => x.map2(acc)(_ :: _))
}
This part was difficult to understand, so I'll come back to it later.
Finally, we're given a difficult problem.
[Difficult] Implement a vending machine.
I looked at the answer because it was difficult.
The solution uses sequence and is quite abstract.
object Candy {
def update = (i: Input) => (s: Machine) =>
(i, s) match {
case (_, Machine(_, 0, _)) => s
case (Coin, Machine(false, _, _)) => s
case (Turn, Machine(true, _, _)) => s
case (Coin, Machine(true, candy, coin)) =>
Machine(false, candy, coin + 1)
case (Turn, Machine(false, candy, coin)) =>
Machine(true, candy - 1, coin)
}
def simulateMachine(inputs: List[Input]): State[Machine, (Int, Int)] = for {
_ <- sequence(inputs.map((i: Input) => modify[Machine](s => update(i)(s))))
s <- get
} yield (s.coins, s.candies)
}
Thoughts
I've been writing stateless code for a while, but now I can finally handle state.
If I can master this, I can write stateful code in a stateless way, which is extremely powerful.
I feel like I'm getting closer to the essence of functional programming.
However, this book is only about 1/3 done, and I still have a lot to learn.
I'll keep going and come back to this chapter later.
