Cons is the nonempty case of a singly linked List. It stores exactly two things: a first element, called the head, and another List, called the tail. The tail may be Nil, so Cons(1, Nil) is a one-element list; or it may itself be another Cons, forming a chain. This small recursive shape represents lists of any finite length without requiring a separate constructor for each size. section 3.1
Listing 3.1 Singly linked lists
package fpinscala.datastructures
enum List[+A]: #1
case Nil #2
case Cons(head: A, tail: List[A]) #3
object List: #4
def apply[A](as: A*): List[A] = #5
if as.isEmpty then Nil
else Cons(as.head, apply(as.tail*))
Read Cons(head, tail) as the repeating link in a list: each link holds one value and points to the remaining List. section 3.1
A List has only two possible forms: Nil for an empty list and Cons for a nonempty one. Since List is polymorphic, the same Cons shape can hold Int, Double, String, or another element type. Constructing Cons values directly makes the recursive structure visible: Cons("a", Cons("b", Nil)) places "a" at the front and leaves a one-element list as its tail. section 3.1
Taking apart a nonempty list
Pattern matching reveals the values used to construct Cons. In case Cons(x, xs) => x + sum(xs), x is bound to the head and xs to the tail. The function can then combine the first value with a recursive computation on what remains. A separate Nil case supplies the base case, because there is no head or tail to inspect in an empty list. section 3.2 section 3.6
Cons supports common list operations by either reusing or rebuilding links:
- tail matches Cons(_, tl) and returns tl, discarding the head without constructing a replacement list. section 3.6
- setHead matches Cons(_, tl) and builds Cons(hd, tl), keeping the original tail while supplying a new head. section 3.6
- drop repeatedly matches Cons(_, tl), discarding one head at a time and recurring on the tail. section 3.6
- init preserves earlier elements by rebuilding Cons(hd, init(tl)) until it reaches the final element. section 3.6
This distinction matters for immutable lists. Prepending creates a new Cons whose tail can be an existing list, avoiding a copy of that tail. By contrast, operations that change the far end of a singly linked list, such as appending, may need to copy the structure leading to that end. Cons therefore makes both reuse and necessary rebuilding explicit. section 3.6
Cons also appears as the building block for higher-level list transformations. foldRight can reconstruct a list with Cons, map can apply a function to each head while retaining the list shape, and filter can choose whether to emit a Cons for each element. These functions differ in purpose, but each decides what to do at a Cons and continues with its tail. section 3.6 section 3.6
