I remember a developer I mentored a few years back who was tasked with implementing a custom undo-history mechanism for a graphics editor. He spent three days wrestling with a mutable linked list, manually updating next and prev pointers. He ended up with a bug where a specific sequence of "undo" and "redo" actions would create a circular reference, causing the application to freeze in an infinite loop. When we sat down to debug it, he was exhausted. I showed him how to model the same history using an immutable linked list and a simple recursive function. He looked at the code—which was about a tenth of the length of his original implementation—and asked why anyone would ever use pointers. The answer is that we're often taught to think in terms of changing memory, rather than transforming data.

Modeling the List as an Algebraic Data Type

In Scala, we don't build linked lists by creating a class with a mutable pointer to the next node. Instead, we treat the list as an Algebraic Data Type (ADT). Essentially, a list is either empty, or it is a head element followed by another list. This is a recursive definition that maps perfectly to Scala's sealed trait and case class structure.

sealed trait MyList[+A]
case object MyNil extends MyList[Nothing]
case class MyCons[A](head: A, tail: MyList[A]) extends MyList[A]

Notice the +A. That's covariance. It allows us to treat MyNil (which is a MyList[Nothing]) as a valid MyList[String] or MyList[Int]. If you omit that, the compiler will complain every time you try to return an empty list from a function expecting a specific type. I've seen many devs fight the compiler for an hour before realizing they forgot the plus sign.

Processing Lists with Pattern Matching

Once you have this structure, you stop thinking about while loops and start thinking about pattern matching. To do anything with a functional list, you ask two questions: "What do I do if the list is empty?" and "What do I do with the first element if it isn't?"

Take a map function, for example. You don't iterate; you decompose. You take the head, apply the function, and then recursively call map on the tail. It's a clean, mathematical way of describing the transformation.

def map[A, B](list: MyList[A], f: A => B): MyList[B] = list match {
  case MyNil => MyNil
  case MyCons(h, t) => MyCons(f(h), map(t, f))
}

This looks elegant, but there's a catch. Each recursive call adds a frame to the call stack. If you try to map a list with a million elements, you'll hit a StackOverflowError. This is where the "revisited" part of our implementation comes in: we need to optimize for the JVM.

The Power of Tail Recursion and Accumulators

To avoid crashing the stack, we use tail recursion. A function is tail-recursive if the very last action it performs is calling itself. The JVM can then optimize this into a loop under the hood, giving us the performance of a while loop with the safety of functional programming.

The trick is usually an "accumulator." Instead of building the result as the recursion unwinds (which is what happens in the map example above), you pass the current state of the result into the next call. Let's look at how to implement a reverse function this way. I always recommend using the @tailrec annotation; it tells the compiler to throw an error if the function isn't actually tail-recursive, saving you from finding out about a stack overflow in production.

import scala.annotation.tailrec

def reverse[A](list: MyList[A]): MyList[A] = {
  @tailrec
  def loop(remaining: MyList[A], acc: MyList[A]): MyList[A] = remaining match {
    case MyNil => acc
    case MyCons(h, t) => loop(t, MyCons(h, acc))
  }
  
  loop(list, MyNil)
}

In this version, we peel the head off the original list and prepending it to the accumulator. By the time we hit MyNil, the accumulator contains the entire list in reverse order. It's efficient, it's safe, and most importantly, it's immutable. No pointers to lose, no circular references to worry about.

📋 Practical Task

Implementing a Tail-Recursive List Filter

Your task is to extend the MyList implementation. Write a function called filter that takes a MyList[A] and a predicate function (A => Boolean), returning a new MyList[A] containing only the elements that satisfy the predicate.

Requirements:

• The implementation must be tail-recursive (use the @tailrec annotation).
• Because a tail-recursive filter naturally reverses the list (due to the accumulator), you must ensure the final result is in the original relative order. (Hint: You can use the reverse function we discussed in the lesson).
• Test your function with a list of integers and a predicate that only keeps even numbers.