MyList - step 1

Build a tiny, immutable linked list from scratch. If you come from an object‑oriented background and are new to FP, this guide will walk you through the core ideas step by step.

What we are building (and why)

We will create a minimal version of Scala's standard List, called MyList. It will be:

Immutable: once created, it never changes.
Singly linked: each element points to the rest of the list.
Built from two building blocks (an Algebraic Data Type):
- Empty: represents “no elements.”
- Cons: represents “one element followed by the rest.”

Think of a list as either:

nothing (Empty), or
a box with a head value and an arrow pointing to the tail (the rest of the list).

- Cons(1, Cons(2, Cons(3, Empty)))
  1 -> 2 -> 3 ->
- Empty
  []
- Cons(1, Cons(2, Empty))
  [1] -> [2] -> []

Step 1: the common interface (a trait)

We start with a trait that describes what any MyList can do, regardless of whether it’s Empty or Cons. If you’re new to Scala:

trait is like an interface with possible default methods.
[A] means the list is generic (it can hold Int, String, etc.).

trait MyList[A]:
  def isEmpty: Boolean
  def head: A
  def tail: MyList[A]

Notes:

head returns the first element.
tail returns “the rest of the list.”
On an empty list, head and tail don’t make sense; we’ll address that below.

Exercise

Implement the trait with two cases (this is a standard FP pattern called an Algebraic Data Type):

Empty: the empty list.
Cons: a node that stores a head element and a tail (another MyList).

Start from these class skeletons and fill them in:

case class Empty[A]() extends MyList[A]
case class Cons[A]() extends MyList[A]

Hints:

Empty.isEmpty should be true.
Cons.isEmpty should be false.
Empty.head and Empty.tail should signal an error (e.g., throw NoSuchElementException), because there is no first element or remainder.
Cons should store its head and tail in the constructor.

Solution (expand if you’re stuck)

Empty

The empty list has no head or tail, so trying to access them is an error. We’ll use NoSuchElementException to indicate that.

case class Empty[A]() extends MyList[A]:
  override def isEmpty: Boolean = true
  override def head: A = throw new NoSuchElementException("head of empty list")
  override def tail: MyList[A] = throw new NoSuchElementException("tail of empty list")

A non‑empty list stores its first element (head) and a reference to the rest (tail). We pass both via the constructor. Because we are using case class, Scala will generate useful methods like toString, equals, and copy for free.

case class Cons[A](override val head: A, override val tail: MyList[A]) extends MyList[A]:
  override def isEmpty: Boolean = false

Try it out

@main
def main(): Unit =
  val myList: MyList[Int] = Cons(1, Cons(2, Cons(3, Empty())))
  println(myList)        // thanks to case classes, prints the structure
  println(myList.head)   // 1
  println(myList.tail)   // Cons(2,Cons(3,Empty()))

What you should see (format may vary):

- Cons(1,Cons(2,Cons(3,Empty())))
- 1
- Cons(2,Cons(3,Empty()))

## Key FP ideas you just practiced
- Immutability: we build new lists by composing nodes; we never mutate an existing node.
- Recursion by structure: a list is defined in terms of a smaller list (its tail). This is the foundation for many list operations you’ll implement next (map, filter, toString, etc.).
- Algebraic Data Types: modeling data with a small set of precise cases (Empty or Cons) leads to simple, predictable code.

In the next step, we’ll add behavior (like a nicer toString) and build more operations on top of this structure.

Keyboard shortcuts

Learning Scala