An algebraic data type (ADT) defines a type through one or more data constructors. The type is a sum of constructor alternatives, while each constructor is a product of its arguments. section 3.4
In Scala, ADTs can use enumerations or sealed trait hierarchies. Constructors may take zero or more arguments, and pattern matching inspects the values used to construct them. section 3.6
A binary tree
A tree has two constructors: Leaf(value) stores a value, while Branch(left, right) combines two trees. A recursive size operation matches Leaf as the base case and Branch as the recursive case, computing 1 + size(left) + size(right). The same operation can be expressed as a method or a standalone function.
ADTs support several recurring functional-programming techniques:
- Model lists with Cons(head, tail) and Nil, making the empty and nonempty cases explicit. section 3.6
- Use exhaustive pattern matching to ensure that every constructor is handled; non-exhaustive matches may produce MatchError. section 3.6
- Recurse over constructors to implement operations, then generalize repeated traversals with higher-order functions such as map, filter, flatMap, foldRight, and foldLeft. section 3.6
- Represent success and failure as values with ADTs such as Option, Either, Try, and Validated instead of throwing exceptions. section 4.6
