OCaml

Algebraic Data Types

Algebraic data types are the fundamental building blocks of programs in ML-style languages like Haskell and OCaml. Since they play such an important role in these languages, it is well worth understanding how they work and where they come from—at first, the design may feel a bit arbitrary, but in reality it flows naturally from a reasonable starting point.

Algebraic data types are made up of two components: products (also known as structs, records or tuples) and variants (also known as tagged unions, sums or coproducts). Let’s take a look at each of these in turn, how they can be combined and how they’re related.

Products

Products are a construct that appears in most programming languages: it’s a type that contains multiple values. The simplest example in OCaml would be a pair (just like an ordered pair in mathematics):

# let pair = (1, 2);;
val pair : int * int = (1, 2)

This pair has the type int * int which means it has two members, both integers. In prose rather than code, this is often written as int × int because it corresponds to a cross-product of sets. Fundamentally, we can do two interesting things with a pair: get the first element or get the second element:

# let first (x, y) = x;;
val first : 'a * 'b -> 'a = <fun>
# let second (x, y) = y;;
val second : 'a * 'b -> 'b = <fun>

In OCaml, pattern matching makes the definitions pretty visual. The functions first and second are often abbreviated as fst and snd or π₁ and π₂ (π is used because these are projection functions).


Of course, we want to be able to build up more complicated types than pairs, so most languages support having any number of fields

let tuple = (1, 2, 3, 4);;
val tuple : int * int * int * int = (1, 2, 3, 4)

and giving fields names

# type blarg = { foo : int; bar : int };;
type blarg = { foo : int; bar : int; }
# let x = { foo = 1; bar = 2 };;
val x : blarg = {foo = 1; bar = 2}

This is very useful for actual programming, but does not really give us any new capabilities. Both larger tuples and records are isomorphic to constructions made up of just pairs; for example, we can go back and forth between int * int * int * int and int * (int * (int * int)) (made up of nested pairs):

let from (a, b, c, d) = (a, (b, (c, d)));;
let to' (a, (b, (c, d))) = (a, b, c, d);;

This is good news: it means that to understand products in their full generality, we just need to understand pairs. Other constructs like larger tuples and records come “for free” because we can always build up an equivalent structure just out of pairs.

You’ll note that records are very similar to features of languages like C that don’t have tuples at all—records are just like C structs! Even in Java, a language pretty far removed from OCaml, we have record-like functionality in the form of fields on objects; a value object is pretty much the same as an OCaml record:

public class Blarg {
  public final int foo, bar
}

So products are certainly a pretty universal construct. While these languages do not have tuples or pairs themselves, we can still think about their products in terms of tuples, which will let us reuse our theory of product types in a lot of different contexts.

Variants

The other component of algebraic data types are variants. Unlike products, variants only tend to exist directly in functional languages—most common OO and procedural languages do not support them directly, although certain common patterns try to emulate them. Happily, it looks like this is changing with the advent of languages like Rust and Swift which do support them.

Where products contain multiple values, variants can be any of multiple possibilities. Instead of having both field 1 and field 2, they have either field 1 or field 2. In fact, that’s what we can call our simple variant building block: either (in the spirit of Haskell):

type ('a, 'b) either = Left of 'a 
                     | Right of 'b

We can construct different values of this type:

# let left = Left 1;;
val left : (int, 'a) either = Left 1
# let right = Right 1;;
val right : ('a, int) either = Right 1

In real programming, we generally write custom variants for our types:

type AST = Expr of ...
         | Stmt of ...
         | Comment of ...

However, just like for products, these more complicated types are ultimately isomorphic to some nested series of eithers.

In a lot of ways, variants are like an extension of enumeration types (enums) in other languages. Enums in languages like Java also have a series of tags, those tags just can’t have any values attached to them. Here’s an example:

public enum State {
  Running, Paused, Stopped
}

This could be written with a variant by having constructors that do not carry any values:

type state = Running
           | Paused
           | Stopped

These sorts of types are pretty useful, but not nearly as versatile as full variants. For example, consider the option type which lets us make values nullable:

type 'a option = Some of 'a
               | None

This is only possible because a variant’s constructor can carry a value. It’s a very useful type in practice because it lets normal values in OCaml not be nullable. As a quick reference, we could express this in terms of our either type by making one of the branches hold unit:

type 'a option = ('a, unit) either
Left value
Right ()

Here, Right () plays the role of the constructor None. Whenever we see a constructor with no arguments, we can always express it as a branch of an either with unit.

To actually get data out of a tagged union, we have to pattern match on it providing a case for each possible constructor:

match my_either with
  | Left a  -> ...
  | Right b -> ...

Making Sense of Variants

Products are an entirely natural programming construct: putting multiple values together is something that emerges very naturally from any non-trivial program we may want to write. On the other hand, variants feel a bit more arbitrary: why the tags? Why not just a union type? I think this is part of the reason why variants are uncommon in more popular languages.

Compared to type unions, variants are generally safer: we always know what we put in at runtime. In fact, quite often, C unions are used to emulate variants with an explicit tag (hence the name “tagged union”):

enum Tag { Left; Right }

struct Either {
  enum Tag tag;
  union {
    int left;
    char* right;
  }
}

The idea is to check the tag each time you read the value, to make sure you’re getting the right sort of data from the union. Ultimately, this reasonably common pattern amounts to jury-rigging variants on top of enums and unions, without language support which makes it easier to make mistakes.

In object-oriented programming, the visitor design pattern serves a similar role. The visitor pattern uses OO mechanisms to emulate pattern matching in the OO language, letting us write variant-like code.

Already, we can see that variants aren’t completely arbitrary: one way or another, they tend to emerge as a coding pattern of some sort. At the same time, the fact that they emerge indirectly and often unacknowledged means that it’s a less intuitive concept than a product.

Another way of looking at how products and variants fit together is in terms of the “shape” of a product. What do I mean by that? Let’s start by drawing some diagrams about the types involved. Given a pair A × B, we have the two projection operations from it:

But what makes A × B particularly special compared to any other type C that also happens to have functions to A and B?

The core difference is that, in some sense, the product doesn’t carry any additional information beyond that of its fields. The only important things you can do with it are get the first value or get the second value out. This is not necessarily true of some other type C, even if it does let you get an A or a B out.

We can state this more formally as follows: for any type C with functions f : C → A and g : C → B, there is exactly one function t : C → A × B such that π₁ (t c) = f c and π₂ (t c) = g c for every value c of type C. In other words, either of the possible paths from C to A or B are equivalent (t is the function denoted by a dotted line):

This might seem a bit weird, until you look at how we can define t in general:

let t c = (f c, g c)

So really, this whole thing is a fancy way of saying that we can apply both functions and put them into a tuple!

But why is this interesting? Well, it turns out that we can draw a very similar diagram from a variant A + B. The only difference is that the arrows are flipped! Otherwise, the same sort of relationships hold.

So, in an abstract way, both products and variants have the same core structure, with a particular kind of symmetry between them. Technically speaking, they are duals of each other. To me, this symmetry is strong evidence that variants really make sense: they’re just a natural extension of products, which are entirely natural themselves.

This duality also makes certain other properties and behaviors of algebraic data types emerge. Many languages have subtyping for records (or record-like things—classes). The idea is simple: if we need something with two fields a and b, we can always substitute in a bigger record and just ignore the extra fields.

But how do we do subtyping with variants? Well, just like we flipped the arrows in the diagrams, we flip the requirement: we can always substitute in a smaller variant. In some sense, we get this relationship for free just by acknowledging the duality of products and variants. This is particularly relevant for OCaml because, unlike most other languages, it actually supports this sort of subtyping directly in the form of polymorphic variants.

Putting it all together

Products and variants together—with some nice syntax—give us algebraic data types, which form a surprisingly expressive basis for modeling different domains. We can write types that have multiple constructors, each having multiple arguments:

type foo = Foo of string * int
         | Bar of bool * float
         | Baz of int list

Below the fancy syntax, this is still isomorphic to a bunch of nested pairs and eithers. Reimplementing foo in these terms is a great exercise to really understand this relationship.

One of the most direct ways in which algebraic data types like this are useful is for working with abstract syntax trees. For example, here’s an AST for the simply typed λ-calculus with basic arithmetic:

We could represent it almost directly as an algebraic data type:

type expr = Unit
          | Integer of int
          | Plus of expr * expr
          | Variable of name
          | Lambda of name * type * expr
          | App of expr * expr

This makes for a definition that is fairly easy to follow, largely because it reflects the “shape” of the domain (the grammar) well. This becomes even more useful when you go to write an interpreter for this language: the eval function also follows the shape of the algebraic data type, guiding your implementation.

Another example in a similar vein is using an algebraic data type to represent JSON:

type json = Object of json StringMap
          | Array of json list
          | String of string
          | Number of float
          | True
          | False
          | Null

Apart from being a concise definition that captures all of JSON, this also makes traversing JSON values easy by pattern matching.

Ultimately, algebraic data types are just combinations of products and variants, which turn out to be symmetric concepts. There really isn’t much of a case for not including variants in your language when you already have product types, whether they are tuples or structs or records or even classes. They just fit too well together. And, from a practical standpoint, the combination of the two is an expressive way to declare the data types you’re working with.

Standard

5 thoughts on “Algebraic Data Types

  1. I think you have a typo :
    In the sentence “The functions first and second are often abbreviated as fst and snd or π₁ and π₁ (π is used because these are projection functions).”, “π₁ and π₁” should be “π₁ and π₂”

    Like

  2. Pingback: An Introduction To how to make a idm full version Programs - Softwarefullcrack.com | Free Download Software Full

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s