ADTs (algebraic data types) are an essential feature of any programming language, and though they've been around for decades, new languages still manage to omit them (Go), or half-ass them (Kotlin). So I just want to talk about why they're useful and important for hypothetical language, and also touch on a few design considerations that arise in their implementation.

Why

ADTs are a great tool for modeling the data in your program, and operating on it. That's a pretty broad statement, but that's because they're a very general purpose tool. In a language like Haskell or OCaml, they are the primary tool for modeling data (along with standard collection types like lists, sets and maps) and just about everything you write in those languages will use them.

If you look at a random Haskell TODO MVC example I dug up on the web, the first thing is an ADT defining the basic model for the program:

data Task
   = Task { taskDescription :: String
          , taskCompleted :: Bool
          }
   deriving (Show, Eq)

In this case, they're not using the algebraic aspect of ADTs, they're just using it like a simple struct, but the value here is that ADTs provide a syntactically lightweight mechanism to declare a record which can be easily created and which is usually "value-like".

In the case of Haskell, you request this explicitly with deriving (Show, Eq). Show makes show task print what you'd expect (something like Task("Blah blah blah", false)) and Eq makes taskA == taskB do what you'd expect (compare the two field by field for equality).

Bringing this idea into OOP-land, that is the difference between writing:

case class Task (taskDescription :String, taskCompleted :Boolean)

and

public class Task {
  private final String taskDescription;
  private final boolean taskCompleted;

  public Task (String taskDescription, boolean taskCompleted) {
    this.taskDescription = taskDescription;
    this.taskCompleted = taskCompleted;
  }

  public String getTaskDescription () {
    return taskDescription;
  }
  public boolean getTaskCompleted () {
    return taskCompleted;
  }

  @Override public boolean equals (Object other) {
    if (other instanceof TaskDescription) {
      TaskDescription otask = (TaskDescription)other;
      return taskDescription.equals(otask.taskDescription) &&
        taskCompleted == other.taskCompleted;
    } else {
      return false;
    }
  }
  @Override public int hashCode () {
    return taskDescription.hashCode() ^ Boolean.hashCode(taskCompleted);
  }
  @Override public String toString () {
    return "Task(" + taskDescription + ", " + taskCompleted + ")";
  }
}

Aside from the myriad ways you could screw up in hammering out that Java boilerplate, it imparts a substantial reluctance on the part of a well-meaning programmer to do things the "properly". If I have two or three values that really ought to be wrapped up together in some sensibly named type, I am almost certainly going to do it in Haskell or Scala because it's trivial and I just write down exactly what I need.

In Java, I'm going to look around pretty frantically for any cheap hack I can bring to bear to avoid having to type out all that tedious boilerplate. Or I'll only type some of it, and then some programmer down the line gets to suffer when they spend two hours debugging because I opted not to implement either or both of equals or hashCode, or they get to see Task@37ddb69a show up in the logs because I was too lazy to write toString.

So that's important.

But back to the algebraic part of ADTs. We only have to go down another ten lines or so in our Haskell TODO MVC example to see those get used:

data Filter
   = All -- ^ All tasks
   | Active -- ^ Uncompleted tasks
   | Completed -- ^ Completed tasks
   deriving (Show, Eq)

Here we see ADTs used as an enum, which is another thing they're super useful for. This is a simplified incarnation of their more general purpose use which could be described as "enums with data", but we'd have to find a slightly more complex program to see that in action. Here's an expression evaluator pulled out of a Stack Overflow post on OCaml (where some clever student asked the Internet to do his homework for him):

type expression =
| Term of int
| Addition of expression * expression
| Multiplication of expression * expression
| Subtraction  of expression * expression
| Factorial of expression;;

An expression can be one of Term, Addition, Multiplication, etc. and each one of those cases carries some data with it. Term has an int associated with it, the binary expression types have two more expressions bundled in. All of this is still syntactically very concise. Imagine writing a class hierarchy to model expression in Java. Ugh.

ADTs go hand in hand with pattern matching. That's the main way you discriminate which type you have and destructure it to get at the data stored inside. The same Stack Overflow post contains a function that pattern matches on the expression ADT to evaluate it:

let rec eval expression =
  match expression with
  | Term m -> m
  | Addition(m,n) -> eval(m) + eval(n)
  | Subtraction(m,n) -> eval(m) - eval(n)
  | Multiplication(m,n) -> eval(m) * eval(n)
  | Factorial(m) -> factorial(eval(m));;

You can see that we not only "figure out" what particular ADT case we're looking at, but we also bind the associated data for that case to names so that we can use them in the code executed when we've matched that case.

ADTs also turn out to be useful for a lot of basic programming building blocks:

data Maybe a = Nothing | Just a
data Either a b = Left a | Right b
data List a = Cons a (List a) | Nil
data Tree a = Leaf a | Branch (Tree a) (Tree a)

Maybe models a situation where you have some result or nothing, Either models a situation where you have one type of result or another. List builds up a list from a head and tail (in the Lisp tradition). Tree is a binary tree with data only in the leaves.

These are generic data structures which usually come with a host of functions that operate on them to do generally useful stuff, but they naturally fit into the ADT paradigm just as nicely as all of the "end user" stuff that we might come up with in our day to day programming.

ADTs and OOP

In traditional functional languages (Haskell, SML, etc.), ADTs are just tagged containers for data. Any "behavior" has to come in the form of functions that take the ADT as a parameter and use pattern matching to operate on the different cases. But Java (with enums) and Scala (with sealed traits and case classes) have shown that it can be fruitful to mix and match ADTs with OOP.

Take the case of Scala's Option, which is like Haskell's Maybe shown above. Sometimes we just want to know if we have something, but we don't care what it is. In traditional functional style, we might write:

sealed trait Option[T]
case class Some[T] (value :T) extends Option[T]
case object None extends Option[Nothing]

def isDefined (opt :Option[_]) :Boolean = opt match {
  case None    => false
  case Some(_) => true
}

But in an object-oriented langauge, we model Option as an interface and None and Some as concrete implementations of it, so we can add methods to Option and implement them in Some and None:

sealed trait Option[T] {
  def isDefined :Boolean
}
case class Some[T] (value :T) extends Option[T] {
  override def isDefined = true
}
case object None extends Option[Nothing] {
  override def isDefined = false
}

You can still pattern match on Option in cases where that makes sense, but you can also call methods on an Option directly, because sometimes that's more natural.

This becomes even more apparent when an ADT implements an existing interface. For example, an Option can be viewed as a collection of zero or one elements, and there are many situations where it's natural to operate on it as such. So we might want our Option to implement Collection and support folds and maps and all the things you can do with collections.

This allows something like this to work "for free":

trait Traversable[T] {
  def foreach (op :T => Unit) :Unit
}

case class Some[T] (value :T) extends Traversable[T] {
  def foreach (op :Nothing => Unit) {} // noop!
}
case object None extends Option[Nothing] {
  def foreach (op :T => Unit) = op(value)
}

def flatten[A] (css :Traversable[Traversable[A]]) :Traversable[A] = {
  let flat = List.builder[A]()
  css.foreach { $1.foreach { flat += $1 }}
  flat.build()
}

I can pass List(Some("a"), None, None, Some("b"), None) and get back List("a", "b") without any special code to handle Option. I can also pass Some(List("foo", "bar")) and get back List("foo", "bar") and None and get back List(). Note that I'm glossing over the complex and fiddly problem of how to return the "right" concrete collection type for generic operations on collections, that's not germaine to this discussion.

So there are useful situations where we want our ADTs to implement interfaces, and be treated as simple class heirarchies.

How

In a world free of OOP baggage, ADTs tend to be implemented via a blob of bytes with a tag at the front (sometimes called a discriminated union), so that the pattern matcher implementation can use the tag to figure out which case is present and then pull data out based on that case's static structure. Something like this terrible C code (ignoring data alignment concerns):

struct {
  uint8 tag;
} Option;

#define OPTION_NONE 0
struct {
  uint8 tag; // always OPTION_NONE
} Option_None;

#define OPTION_SOME 1
struct {
  uint8 tag; // always OPTION_SOME
  void* value;
} Option_Some;

void do_something (Option* opt) {
  switch (opt.tag) {
    case OPTION_NONE: {
      Option_None* optNone = (Option_None*)opt;
      // do stuff
      break;
    }
    case OPTION_SOME: {
      Option_Some* optSome = (Option_Some*)opt;
      // do stuff, probably with optSome->value
      break;
    }
  }
}

But if we're already in a language that's going to support OOP, then it can make sense to "use the vtable" (or rather "use RTTI") to do our discrimination for us, and so we model ADTs using simple class hierarchies. (Note the below is made up hypothetical language syntax.)

data Dir { North East South West }

// desugars into

abstract class Dir {}
object North : Dir {}
object East : Dir {}
object South : Dir {}
object West : Dir {}

This is convenient, and essential when we're supporting the use of ADTs as abstract classes, but it's also a lot of overhead. In some cases (like the Dir example above) you want your enum to actually just be an alias for int, and in other cases (like Option which ends up being extremely pervasive in a language without nulls), you don't want the overhead of a full object header (nor reference semantics) if you can avoid it.

So for unignorable technical reasons, you probably want to support all three kinds of ADT implementation (type alias for int, simple structs, and full-blown class hierarchy), and because all abstractions end up leaking a little bit, it won't likely be possible to hide this all behind the scenes as compiler optimizations.

In hypothetical language, I would "default" to struct-based ADTs, and allow you to specifically restrict an ADT to a pure integer enumeration or promote an ADT to a full-fledged class hierarchy. In a backend based on something like LLVM, differentiating between a tagged struct and an int might not be worth the trouble because int tag isn't very different from struct { int tag } but in a backend that compiled to JavaScript or Java bytecode, this would be meaningfully different. Similarly, in an "OOP-only" backend, the only meaningful distinction would be int or full-fledged class, so the promotion distinction would be meaningless. Such are the fun complexities of supporting many target environments.

Wherefore

Now the aforementioned design considerations, aka niggling bits.

To nest or not to nest?

There's a question of where in the namespace to put the individual case types of an ADT, and depending on that choice, whether to do anything special to ease their use.

One can put the case types in the same namespace as the ADT name itself:

data Dir { North East West South }
let dir = North

I believe this is what Haskell does, but my Haskell-fu is weak, so I may be mistaken.

Or one can nest the case types inside the ADT, like so:

data Dir { North East West South }
let dir = Dir.North

The former approach suffers from namespace crowding and collisions, and the latter approach suffers from verbosity. Java takes the latter approach but then tries to ease the pain with custom hackery for switch statements:

enum Dir { NORTH, EAST, WEST, SOUTH }

void foo () {
  Dir dir = Dir.NORTH; // have to prefix with Dir here
  switch (dir) {
  case NORTH: // don't have to prefix here
  // ...
  }
}

Swift extends this special name resolution to everywhere the type of the enum is known, but requires that you prefix the name with a dot:

enum Dir {
  case North, East, West, South
}

let dir = Dir.North // need prefix here, don't know type
switch dir {
  case .North: // don't need prefix here, just a .
  // ...
}

func foo (dir :Dir) {}
foo(.East) // don't need prefix here either

I think Swift makes a good compromise here, in that I like the case type names being nested in the top-level ADT, but I don't like having to repeat the ADT name (or manually import it) all over the place.

I waver on the .-prefixing, because a naming conflict would either be wildly contrived or flat out impossible (depending on how flexible pattern matching is), so why add the syntactic noise? One man's noise may be another man's useful documentation, but I lean toward no prefix.

Free-standing destructuring binds

Scala allows free-standing destructuring binds like this:

def danger (opt :Option[String]) {
  val Some(str) = opt
  println(s"Woo! $str")
}

But I named that danger because you're basically inviting runtime failure over for dinner:

scala> def danger (opt :Option[String]) {
     |   val Some(str) = opt
     |   println(s"Woo! $str")
     | }
danger: (opt: Option[String])Unit

scala> danger(None)
scala.MatchError: None (of class scala.None$)
  at .danger(<console>:12)
  ... 30 elided

I'm not sure why they even allow it. It's just asking a programmer to shoot themselves in the foot. That said, there are cases where destructuring binds outside a pattern match could be useful, and hypothentical language should support those cases.

The above code would be perfectly reasonable in a conditional. Swift allows this (though perhaps only for it's built in option type), so we can do something similar:

def safe (opt :Option[String]) {
  if (let Some(str) = opt) { println("Woo $str") }
}

That's much preferable to how you have to do it in Scala today:

def safe (opt :Option[String]) {
  opt match {
    case Some(str) => println("Woo $str")
    case None => // nothing to see here, move it along
  }
}

Now of course some Scala programmer will pipe up with how I'm doin' it wrong, and I should use:

def safe (opt :Option[String]) {
  opt foreach { str => println("Woo $str") }
}

or some other more functional programmery approach. Fair enough, but is it not a bit misleading that I'm using a function called foreach to check whether my option is defined and use its value? The fewer idioms we can get away with, the better. This approach also comes at non-trivial abstraction cost: maybe that closure is optimized away, maybe not. In the limit you can be sure the answer is not.

It's also not unreasonable to allow a destructuring bind where it's known to be safe. Sometimes you happen to know that you have a Foo(a, b, c) and it's nice to just write let Foo(a, b, c) = foo and then use a, b, and c as you wish, rather than writing foo.a, foo.b, and foo.c all over the place.

That said, this particular kind of destructuring might be better handled by a special ProductN type which could be used to destructure anything that implements ProductN:

// the built-in tuple mechanism would naturally use ProductN
let triple = (1, 2, "five")
let (a, b, c) = triple

// ADTs could also implement the appropriate ProductN
let list = Cons("foo", Nil)
let (head, tail) = list

// and end users could implement ProductN manually
class Point (val x :Int, val y :Int) : Product2[Int,Int] {
  def _0 = x
  def _1 = y
}
let point = Point(5, 3)
let (x, y) = point

Or one could just do things entirely with names (which in simple cases is not a one way ticket to bad compiler error message hell). We could just say that a destructuring bind desugars in a very simple way:

let bippy = // whatever!
let (foo, bar, baz) = bippy
// desugars to
let foo = bippy._0
let bar = bippy._1
let baz = bippy._2

If you screw up, we could generate an error message that's not totally inscrutable:

class Bippy used in three argument bind but does not define 'def _2 :???':

  let (foo, bar, baz) = bippy
                 ^

By the way, I don't love _0, _1, etc. as the names for the product accessors (which are what Scala uses), but I was not able to come up with an obviously better alternative in the time it took to write this article. So more thinking is needed on that front.

Type inference

In many circumstances it's useful for each ADT case to be its own type (or singleton type for cases that have no attached data). However, it's almost universally a bad idea to infer those types.

For example, if I write:

data Tree[T] {
  Leaf (value :T)
  Branch (left :Tree[T], right :Tree[T])
}
class Blah {
  def root = Leaf(0)
}

I don't want to infer the return type of root to be Leaf[Int], I want to infer it to be Tree[Int]. This is a problem with variables as well:

var foo = Leaf(0)
foo = Branch(foo, foo) // type error because foo is Leaf[Int]

This happens quite often in Scala with None and Some which are subtypes of Option. Particularly because Scala infers refined return types when you override a method, so you get this classic blunder:

abstract class Foo {
  def bar :Option[String]
}
class Bar extends Foo {
  override def bar = None
}
class Baz extends Bar {
  override def bar = Some("bippy")
  // fail: Bar.bar has return type None.type, not Option[String]
}

Anyhow, tips from the pros: don't infer ADT case types and don't infer refined types when overriding a method.

Great artists steal

There are a couple of other things that make pattern matching more powerful and pleasant to use that we can lift wholescale from Scala.

Extractors: Scala allows one to define an object with an unapply method (called an extractor) which allows one to plug arbitrary logic into the pattern matching process. These are useful and powerful. This article is already too long to go into more detail, but you can read more if you're interested.

Capturing names: Pattern matching does two important things: it checks for a match (by comparing type tags, structure and values) and it binds names to the matched data. When you have a simple pattern match, that just happens naturally:

trait Staff
case class Artist (name :String, faveColor :String) extends Staff
case class Programmer (name :String, faveLang :String) extends Staff

def faveThing (staff :Staff) = staff match {
  case Artist(_, faveColor) => faveColor
  case Programmer(_, faveLang) => faveLang
}

But sometimes you actually need to tell the compiler that you want a name for something:

def printSalaryOfPinkLovers (staff :List[Staff], salaries :Map[Staff,Int]) {
  for (s <- staff) s match {
    case artist @ Artist(name, "pink") => println(s"$name earns $${salaries(artist)}")
    case _ => // ignore
  }
}

Say what?

So that's a quick tour of why ADTs are a very important addition to any civilized new programming language, and a few of the whats and hows of integrating them into a multi-paradigm language which seeks to both honor their functional heritage and integrate them nicely with all the OOP features that moved into the neighborhood in more recent years.