Functional data structures

Two constructors

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

• Nil is the empty case.
• Cons(head, tail) is the nonempty case.
• sealed makes the set of cases closed to this file.
• Immutable tails can be shared by multiple list versions.

Pattern matching

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

Match the empty base case first, then expose the head and recurse over the tail.

Safe sharing

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 allocates one new node and reuses the old tail. Immutability means the shared suffix cannot be changed behind another reference.

Fold and map

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))
}

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

• Nil becomes zero.
• Each Cons becomes a call to f.
• map injects a transformation while rebuilding the list shape.

Design checklist

1. List every constructor case.
2. Choose the base result for the empty case.
3. Make the recursive call on a smaller structural value.
4. Return new nodes instead of mutating old ones.
5. Share immutable suffixes when that preserves the desired shape.

Rust translation

Think of Nil/Cons as the Scala equivalent of Empty/Cons enum variants. The ownership and allocation details differ, but the case analysis and recursive structure transfer directly.