Functional Programming in Scala, chapter by chapter

Functional programming (FP) is programming with pure functions: functions whose only job is to compute a result from their inputs. No printing, no database writes, no mutating variables outside themselves — those are side effects.

The book opens with a coffee shop. An impure buyCoffee charges a credit card as a side effect, which makes it painful to test (you'd bill a real card!) and impossible to reuse (buying 10 coffees charges the card 10 times when you wanted one combined charge). The fix: return the charge as data instead of performing it.

// Impure: charging happens inside the function (invisible side effect)
def buyCoffee(cc: CreditCard): Coffee = {
  val cup = new Coffee()
  cc.charge(cup.price)   // side effect!
  cup
}

// Pure: return the charge as a value, let the caller decide what to do
def buyCoffee(cc: CreditCard): (Coffee, Charge) = {
  val cup = new Coffee()
  (cup, Charge(cc, cup.price))
}

Without mutable loop counters, how do you loop? Recursion. Scala turns tail-recursive functions (where the recursive call is the very last thing that happens) into loops under the hood, so they never blow the stack. The @annotation.tailrec annotation makes the compiler verify this for you.

The chapter also introduces higher-order functions (functions that take or return other functions) and polymorphic functions that work for any type. When a signature is generic enough — like def compose[A,B,C](f: B => C, g: A => B): A => C — there's often only one reasonable implementation. The types guide you; the book calls this "following the types."

def factorial(n: Int): Int = {
  @annotation.tailrec
  def go(n: Int, acc: Int): Int =
    if (n <= 0) acc
    else go(n - 1, n * acc)   // tail call: nothing left to do after
  go(n, 1)
}

Functional data structures are immutable — "modifying" a list means building a new one. That sounds wasteful, but immutability enables data sharing: prepending to a list reuses the entire old list as the tail. Nothing needs to be copied, and nothing can break, because nobody can mutate the shared part.

The chapter builds a singly linked List from scratch as an algebraic data type (ADT) — it's either Nil or Cons(head, tail) — and takes it apart with pattern matching. Then comes the workhorse of the whole book: fold. Almost every list operation (sum, length, map, filter, even append) is just a fold with a different combining function.

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = as match {
  case Nil => z
  case Cons(h, t) => f(h, foldRight(t, z)(f))
}
// sum = foldRight(xs, 0)(_ + _)   length = foldRight(xs, 0)((_, n) => n + 1)

Exceptions break referential transparency — a function that throws doesn't really return what its signature promises, and the error escapes the type system entirely. The functional answer: represent failure as an ordinary value.

Option[A] is either Some(a) or None — "there might not be an answer." Either[E, A] is Right(a) or Left(e) — same idea, but the failure carries information. The magic is that you don't have to null-check at every step: map and flatMap let you write the happy path, and any None short-circuits the rest automatically.

def parseAge(s: String): Option[Int] =
  s.toIntOption                       // None if not a number

def validAge(n: Int): Option[Int] =
  if (n >= 0 && n <= 120) Some(n) else None

def category(s: String): Option[String] =
  parseAge(s)
    .flatMap(validAge)
    .map(n => if (n < 18) "minor" else "adult")

Scala normally evaluates arguments strictly (before the function runs). A non-strict (lazy) argument — written => A — is only evaluated if and when it's actually used, and lazy val caches the result so it's evaluated at most once.

Laziness unlocks Stream (today's LazyList): a list whose tail is a thunk that isn't computed until you ask. Now map, filter and take don't each walk the whole list — they fuse into one pass that does the minimum work needed. You can even describe infinite streams like ones or all the Fibonacci numbers, then take(10) from them safely. The chapter frames this as separating the description of a computation from its evaluation.

val fibs: LazyList[Int] = {
  def go(a: Int, b: Int): LazyList[Int] =
    a #:: go(b, a + b)          // #:: is lazy cons — tail not computed yet
  go(0, 1)
}
fibs.take(8).toList   // List(0, 1, 1, 2, 3, 5, 8, 13) — only 8 evaluations

How can a pure function generate random numbers, when calling it twice must return the same thing? Answer: make the generator's state explicit. Instead of mutating hidden state, a functional RNG takes a state in and returns the next value together with the next state: RNG => (A, RNG).

Threading that state by hand gets tedious fast, so the chapter abstracts the pattern into State[S, A] — "a program that, given a state, produces a value and a new state" — with map and flatMap to sequence steps without ever mentioning the state explicitly. This is the same shape you'll meet again in Chapter 11 as a monad.

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

case class SimpleRNG(seed: Long) extends RNG {
  def nextInt: (Int, RNG) = {
    val newSeed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
    val n = (newSeed >>> 16).toInt
    (n, SimpleRNG(newSeed))     // value AND the next generator
  }
}

The chapter designs a parallelism library from scratch. The core data type is Par[A]: a description of a parallel computation that will eventually yield an A. Crucially, building a Par runs nothing — you compose descriptions with combinators like map2 (combine two parallel results) and fork (mark something for its own thread), and only run actually touches a thread pool.

This is the book's big design lesson: separate the what from the how. Because Par values are just data, they obey algebraic laws (like map(unit(x))(f) == unit(f(x))) that you can reason about — and the whole API stays pure even though execution involves very impure threads.

def sum(ints: IndexedSeq[Int]): Par[Int] =
  if (ints.size <= 1) Par.unit(ints.headOption.getOrElse(0))
  else {
    val (l, r) = ints.splitAt(ints.size / 2)
    Par.map2(Par.fork(sum(l)), Par.fork(sum(r)))(_ + _)
  }
// Nothing runs yet. Par.run(pool)(sum(xs)) executes the tree.

Instead of hand-writing example tests ("reverse of [1,2,3] is [3,2,1]"), property-based testing states a law that must hold for all inputs ("reversing twice gives back the original list") and lets the library hammer it with hundreds of random cases. When a case fails, good libraries shrink it to a minimal counterexample.

The chapter builds the two halves: Gen[A], a generator of random test values (built on Chapter 6's State/RNG!), and Prop, a property that can be checked, with combinators like && and forAll. It's both a testing tool and a third case study in algebra-first library design.

val intList = Gen.listOf(Gen.choose(0, 100))

val reverseProp = forAll(intList) { xs =>
  xs.reverse.reverse == xs               // must hold for EVERY list
}
val badProp = forAll(intList) { xs =>
  xs.reverse == xs                       // only true for palindromes!
}

A parser combinator library builds big parsers out of tiny ones: char('a') parses one character, or tries alternatives, many repeats, map transforms results, product sequences two parsers. A JSON parser is just these pieces stacked up.

The chapter's real subject is method: it designs the algebra (the combinator signatures and the laws relating them) before writing any implementation at all — the purest demonstration of "algebraic design" in the book. Error reporting (labels, nesting, committed vs. uncommitted branches) is designed the same way.

// The algebra — signatures first, implementation later
def char(c: Char): Parser[Char]
def or[A](p1: Parser[A], p2: Parser[A]): Parser[A]
def many[A](p: Parser[A]): Parser[List[A]]
// law: run(char(c))(c.toString) == Right(c)

A monoid is the simplest useful abstraction in the book: a type with a binary combine operation that is associative — (a·b)·c == a·(b·c) — plus an identity element that does nothing. Integers with + and 0. Strings with concatenation and "". Lists with append and Nil. Booleans with && and true.

Why care? Associativity means grouping doesn't matter — so a fold over a monoid can be split into chunks, computed in parallel, and combined in any order, with the identity as a safe starting value. Monoids also compose: if A and B are monoids, so is (A, B), which lets you compute several aggregates (say, sum and count, for a mean) in a single pass.

trait Monoid[A] {
  def combine(a1: A, a2: A): A   // must be associative
  def empty: A                     // combine(a, empty) == a
}
val intAddition = new Monoid[Int] {
  def combine(a: Int, b: Int) = a + b
  def empty = 0
}

Option, List, Par, Gen, Parser, State — you implemented flatMap and unit for every one of them. A monad is just the name for that shared interface: unit(a) wraps a plain value, and flatMap sequences a computation with a function that produces the next computation. Once a type is a monad, you get a pile of functions for free — map, map2, sequence, traverse — written once, working for all of them.

The laws (associativity and identity, cousins of the monoid laws) guarantee that chaining behaves sensibly no matter how you group the steps. Don't look for a metaphor — the book's stance is that a monad is defined by its operations and laws, nothing more mystical. Each instance just decides what "and then" means: for Option it's "if it succeeded so far", for List "for each result", for State "threading the state through."

trait Monad[F[_]] {
  def unit[A](a: => A): F[A]
  def flatMap[A,B](fa: F[A])(f: A => F[B]): F[B]

  // free for every monad:
  def map[A,B](fa: F[A])(f: A => B): F[B] =
    flatMap(fa)(a => unit(f(a)))
}

An applicative functor sits between plain functors and monads: its core operation map2 combines two independent effects. Monads are strictly more powerful — flatMap lets the second computation depend on the first's result — but that power costs you: monadic effects must run in sequence, while applicative effects have a fixed, statically-known structure you can analyse, parallelise, or run all at once.

The practical star is validation: with Either, chained flatMaps stop at the first error. An applicative Validation type combines independent checks and accumulates every error — exactly what you want for a web form. The chapter also introduces Traverse: traverse walks a structure, applies an effectful function to each element, and flips the result inside-out (e.g. List[Option[A]] => Option[List[A]]).

// Monadic Either: stops at the first Left
// Applicative Validation: gathers ALL the Lefts
def validateForm(name: String, age: String, email: String) =
  map3(checkName(name), checkAge(age), checkEmail(email))(User(_, _, _))

The trick: an IO[A] value doesn't do anything — it's a description of an effectful program that will produce an A when someone finally runs it. Since IO is a monad, you compose whole programs with map and flatMap while staying pure; the single impure moment is one unsafeRun call at the very edge of your app (the "end of the world").

A naive IO overflows the stack on long programs, so the chapter rebuilds it as a data structure of instructions (trampolining with Return / Suspend / FlatMap), generalising to the Free monad. The deep idea: your program becomes data describing effects, and you write interpreters for that data — a test interpreter, a production interpreter, whatever you need.

def greet: IO[Unit] = for {
  _    <- printLine("What's your name?")
  name <- readLine
  _    <- printLine(s"Hello, $name!")
} yield ()
// greet is just a value. Nothing happens until: unsafeRun(greet)

A surprising refinement: purity is about what's observable from outside. A function that allocates a mutable array, scribbles all over it, and returns an immutable result is still pure — no caller can ever tell. In-place quicksort inside, referential transparency outside.

The chapter builds the ST monad ("state thread") to make this compiler-enforced: mutable references (STRef) are tagged with a type parameter that can't escape their scope, thanks to a clever use of Scala's type system (rank-2-style polymorphism via RunnableST). Try to leak a mutable ref out, and the code simply doesn't compile.

def quicksort(xs: List[Int]): List[Int] = {
  // copies to an Array, sorts in place, returns a new List
  // mutation is real — but sealed inside; the function is pure
  ...
}

Monolithic IO code for "read a huge file, count lines, check if > 40,000" mixes concerns and reads everything eagerly. The chapter's answer is Process[I, O]: a stream transducer — a state machine that repeatedly awaits an input, emits outputs, or halts. Transducers compose with |> (pipe) into pipelines like filter(nonEmpty) |> count |> exists(_ > 40000).

Each stage pulls only what it needs, so processing is incremental and constant-memory — a gigabyte log file streams through without ever being fully in memory, and the pipeline stops as soon as the answer is known. Generalised to carry effects, this design is the ancestor of modern streaming libraries like FS2.

val pipeline =
  filter[String](_.nonEmpty) |> lift(_.toUpperCase) |> take(3)
// pulls at most 3 lines from the source, no matter how huge it is