An algebraic data type is a type defined via constructors that can subsequently – often in a functional language setting – be used in pattern matching. The typical example is (using Haskell syntax):

One can view the type constructors (Cons and Empty above) as regular functions acting on the specified types, so that the nested application
Cons 42 Empty
creates a proper IntStack. But how the heck are these two functions (Cons and EmptyStack) defined? I sure cannot see any definition in there. I am confused.

Well, just like the Herbrand Universe is in some sense the simplest underlying set for a theory, we also here deal with a simple one-to-one mapping between syntactical constructions and the meaning, so that the value of the expression above is nothing else but that expression itself. Cool, eh?

Ok, maybe not, since we do not seem to gain anything by defining the value of the application to be the syntactical application itself. For you math savvy people out there, think free algebrae, i.e., the algebra based on the primitives we saw without any collapse of elements. That simple.

What can these syntactical applications be used for? For pattern matching. One can define a function ‘pop’ as

An interesting aspect is the duality between algebraic data types and abstract data types – where the former is syntax and the latter is anything but concrete syntax.

There are extensions supporting freer functions operating on algebraic data types in some form, such as Generalized Algebraic Data Types (GADT). See http://research.microsoft.com/~akenn/generics/gadtoop.pdf for more information.

I will talk about the possibility of making the aforementioned duality an analogy, by introducing quite abstract syntax – and pattern matching – into a language. But that will have to wait till another post.