A singly linked list represents a sequence as immutable nodes. Nil denotes an empty list; Cons stores a head element and a tail containing the remaining list. The polymorphic structure supports lists of different element types and can be processed with pure functions. 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 definition makes the recursive shape explicit: each Cons points to another List, while the companion apply method constructs lists from sequences of arguments. section 3.1
Use the structure to reason about functional data and its costs:
- Treat lists as immutable values: concatenation creates a new result without modifying either input. section 3.1
- Reuse unchanged tails through persistence, avoiding unnecessary copying when operations can share structure. section 3.3.1 section 3.6
- Prepending can avoid copying, whereas appending or replacing a tail requires copying preceding Cons nodes. section 3.3.1 section 3.6
- Define recursive algorithms by matching Nil as the base case and Cons as the recursive case; foldRight, foldLeft, map, filter, and flatMap generalize common traversals. section 3.6
Constructing and challenging a list
Examples include List.Nil, List.Cons(1, List.Nil), and List.Cons("a", List.Cons("b", List.Nil)). A useful implementation challenge is init: given List(1,2,3,4), return List(1,2,3). Unlike tail, init cannot run in constant time because reaching the result requires rebuilding the preceding Cons nodes. section 3.1 section 3.3.1
