A data constructor names one possible form of an algebraic data type (ADT) and creates values in that form. It may take no arguments, as with `Nil`, or carry fields, as with `Cons(head, tail)`. An ADT is the union of its constructors: each constructor is a product of its arguments. section 3.1 section 3.4
For a singly linked list, there are exactly two forms. `Nil` constructs the empty list. `Cons` constructs a nonempty list from an element and another list. Because the tail is itself a `List`, repeated `Cons` calls build a recursive structure. 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*))
The `case` declarations introduce `Nil` and `Cons`; the companion `apply` function then turns a sequence of arguments into nested constructor calls. section 3.1
Constructing list values
`List.Nil` is an empty `List[Double]`. `List.Cons(1, List.Nil)` is a one-element `List[Int]`. `List.Cons("a", List.Cons("b", List.Nil))` builds a two-element string list. The same polymorphic definition works for each element type. section 3.1
Constructors also provide the shapes used to take values apart. A pattern such as `Cons(x, xs)` recognizes a nonempty list and binds its head and tail. Recursive functions commonly assign a base case to `Nil` and recursive cases to `Cons`; the first matching pattern supplies the result. section 3.2
The pattern generalizes beyond lists:
- A tree can use `Leaf(value)` for a terminal node and `Branch(left, right)` for an internal node. section 3.4
- Matching `Leaf(_)` and `Branch(l, r)` lets `size` count every tree node recursively. section 3.4
- Scala can express ADTs with enumerations or sealed trait hierarchies; constructors may have zero or more arguments. section 3.6
Choosing constructors makes the valid forms of a structure explicit. Pattern matching can then inspect the fields that originally constructed a value, and exhaustive matches ensure that every constructor form is considered. This supports recursive, pure operations over immutable data structures. section 3.6
