Algebraic data types

Object types and inheritance are complementary to algebraic types and matching. Object types and inheritance make it easy to extend the set of constructors for the type, so long as the set of operations is relatively fixed. Conversely, algebraic types and matching make it easy to add new operations over the type, so long as the set of constructors is relatively fixed. The former might be useful for building a prototype interpreter for a new programming language, where one often wants to add new language constructs, but the set of operations is small and fixed (evaluate, print). The latter might be useful for building an optimising compiler for a mature language, where one often wants to add new passes, but the set of language constructs is fixed.

Here is a simple example for a data type that represents linked lists, that also demonstrates polymorphism and higher-order functions. Note that the zip routine decomposes two lists in parallel, and is not very easy to write in the traditional object-oriented style, where one breaks a method into parts for each subclass.

Example 4.1 Polymorphism, higher-order functions, and algebraic types  

class Pair<A,B> {
  case Pair(A fst,B snd);
}

class List<A> {
  case Nil;
  case Cons(A head, List<A> tail);
  <B> List<B> map ((A)->B f) {
    switch (this) {
      case Nil:
        return Nil;
      case Cons(A x, List<A> xs):
        return Cons(f(x), xs.map(f));
    }
  }
  <B> List<Pair<A,B>> zip (List<B> ys) {
    switch (Pair(this,ys)) {
      case Pair(Nil,Nil):
        return Nil;
      case Pair(Cons(A x, List<A> xs),
                Cons(B y, List<B> ys)):
        return Cons(Pair(x,y), xs.zip(ys));
    }
  }
}