Lesson 03 · Functional Programming in Scala

Let data shape code

Immutable lists and pattern matching: make each case explicit, then recurse without mutation.

Tangible win

You will model a small immutable list with Nil and Cons, then implement sum, dropWhile, and map by matching its shape. The browser lab traces which constructor case your function visits.

Retrieve before reading

If xs is a nonempty immutable list, what can removing its first element return without changing xs?

Reveal a strong answer

It can return the existing tail. Because the list is immutable, the original list remains available and the result can safely share the untouched suffix.

A list is two cases

A singly linked list does not need a hidden mutable cursor. Its shape is explicit: an empty list, or a head value followed by another list.

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

sealed keeps the set of cases closed in this file. Nil represents empty; Cons represents one value plus the rest. The +A says the list is covariant, so the same shape can hold Int, String, or another type.

For example, List(2, 5, 9) is shorthand for Cons(2, Cons(5, Cons(9, Nil))). Every list is one of those two shapes.

Pattern matching follows shape

A function over this data type should account for both cases. The empty case supplies the base result; the nonempty case binds the head and recursively processes the tail.

def sum(xs: List[Int]): Int = xs match {
  case Nil => 0
  case Cons(head, tail) => head + sum(tail)
}

case Nil stops recursion and returns the identity value for addition.
case Cons(head, tail) exposes the current value and the smaller problem.
The recursive call eventually reaches Nil, then the results combine on the way back.

Pattern vocabulary

The value being inspected is the scrutinee. A pattern such as Cons(head, tail) both checks the constructor and binds names to its fields. A wildcard _ means “this field exists, but I do not need its value.”

Immutability makes sharing safe

“Remove” does not have to mean “erase something in place.” A total helper can return the tail for a nonempty list and the empty list for an empty one:

def tailOrEmpty[A](xs: List[A]): List[A] = xs match {
  case Nil => Nil
  case Cons(_, tail) => tail
}

def setHead[A](xs: List[A], value: A): List[A] = xs match {
  case Nil => Cons(value, Nil)
  case Cons(_, tail) => Cons(value, tail)
}

setHead creates one new Cons node, then reuses the old tail. No caller can mutate that shared tail, so defensive copying is unnecessary. This is persistent data: old versions remain valid after a transformation.

The same idea explains append(first, second): copy the spine of first until it reaches Nil, then point the new spine at second. The second list is shared rather than copied.

Generalize the recursion

sum and product have the same traversal. A right fold replaces the list constructors with a starting value and a combining function:

def foldRight[A, B](xs: List[A], zero: B)(f: (A, B) => B): B = xs match {
  case Nil => zero
  case Cons(head, tail) => f(head, foldRight(tail, zero)(f))
}

val total = foldRight(List(2, 5, 9), 0)(_ + _)

Read it as a structural substitution: Nil becomes zero; every Cons becomes f. The result type B does not have to equal the element type A.

Once the traversal is reusable, map changes each value while rebuilding the same shape:

def map[A, B](xs: List[A])(f: A => B): List[B] =
  foldRight(xs, Nil: List[B])((head, tail) => Cons(f(head), tail))

This is the Lesson 02 idea applied to data: keep the recursive structure stable and inject the behavior that changes.

Rust bridge

The shape is close to a Rust enum such as enum FList<T> { Empty, Cons(T, Box<FList<T>>) }. Scala's sealed trait plus case constructors and Rust's enum plus pattern matching make the same cases visible. Ownership and allocation differ; the structural reasoning is the bridge.

Interactive coding checkpoint

Choose a pure operation over an immutable numeric list. The lab shows the constructor-shaped input, the result, and a short trace of the cases visited.

Browser lab / constructors and recursion

Run a list function

Operation

Values, comma-separated Threshold

Result 19

Input: Cons(2, Cons(5, Cons(9, Cons(3, Nil))))

Cons → Cons → Cons → Cons → Nil

The sum reaches Nil, then combines values on the way back.

Try this sequence:

Run sum on 2, 5, 9, 3. Find the Nil base case in the trace.
Switch to map. The values change, but the Cons/Nil shape stays the same.
Switch to dropWhile, set the threshold to 6, and notice that the result is the untouched suffix 9, 3.
Clear the values and run again. Every operation still has an explicit Nil case.

Quick checks

Which pattern handles an empty list?

What happens when setHead builds Cons(new, tail)?

Spaced review

Before the next lesson, answer these from memory:

What are the two constructors of the small list type?
Why does a recursive list function need a base case?
Why can tail share the original suffix safely?
In foldRight, what replaces Nil and what replaces Cons?
How does Lesson 02's injected behavior appear inside map?

Keep the compact version nearby: Functional data structures reference.

Primary source: Chiusano and Bjarnason, Functional Programming in Scala, Chapter 3. The official first-edition exercise repository provides the chapter stubs and answers. This page is an original, self-contained lesson; the book PDF is not required to run the checkpoint.

Ask me a follow-up question whenever a pattern or recursive step feels unclear. We can trace one constructor at a time.