Nil is the zero-argument data constructor for the empty case of a polymorphic singly linked List. A List has exactly two forms: Nil, containing no elements, or Cons(head, tail), containing one element followed by another List. Because the tail may itself be Nil, every finite list eventually ends at Nil. section 3.1 section 3.6
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*))
The List definition makes the distinction concrete: Nil needs no arguments, while Cons stores a head and a remaining List. The companion apply function reaches Nil when no input elements remain. section 3.1
Nil is an immutable value. It represents absence of list elements rather than a list that can later be filled in. List operations therefore produce values without changing their inputs: concatenation yields a new list, and the original lists remain available. This persistence permits structural sharing where an operation can reuse existing structure rather than copy it unnecessarily. section 3.1 section 3.6
Constructing empty and nonempty lists
An empty list can be written as List.Nil. A one-element list is Cons(1, Nil), and a three-element list is Cons("a", Cons("b", Nil)). Nil is thus both the complete value of an empty list and the terminating tail inside every nonempty list. section 3.1
Pattern matching distinguishes the two possible list shapes. The pattern Nil matches only the Nil value; it does not match a Cons. Recursive list functions use Nil as their base case and Cons as the case that exposes a head and tail. A match that provides only case Nil for a nonempty list has no matching case and throws MatchError. section 3.2 section 3.6
Nil determines several common boundary behaviors:
- sum returns 0 and product returns 1.0 when the input is Nil, supplying the base result for recursive traversal. section 3.2
- drop returns Nil when it runs out of elements before completing further drops. section 3.6
- tail, setHead, and init report an error for Nil, preserving the fact that these operations require a nonempty list. section 3.6
- foldLeft returns its accumulator at Nil; reverse, map, filter, flatMap, and concat use Nil as an initial empty result of the appropriate element type. section 3.6
- zipWith stops with Nil when either input list is Nil, while startsWith treats an empty prefix as present. section 3.6
The appropriate Nil behavior is a design decision tied to an operation's meaning. Returning Nil from tail of an empty list is possible, but signaling an error can be preferable because it keeps a mistaken nonempty assumption close to where it occurred. In contrast, returning Nil from drop after exhaustion naturally expresses that no elements remain. section 3.6
Nil also supplies the empty structural case used by higher-order list operations. For example, map begins with Nil: List[B] and builds Cons values around transformed elements; filter can return Nil for elements that fail its predicate; flatMap can use Nil to represent an element contributing no results. These definitions follow the same structure: a base case for Nil and recursive construction for Cons. section 3.6 section 3.6
