When reasoning about functional types it sometimes helps to take a step away from the compiler and delvelop some informal intuitions about why things work the way that they do.

When I read about algebraic data types they seemed rather complex notions. Algebraic data types, I discovered from wikipedia are composite types, usually product types and sum types. I found myself asking but how is a tuple like a product?

and how is a Maybe like a sum?

.

This article is about the way that I understand the notions, it’s not a rigorous discussion. I have linked to a couple of further resources which in the related links, I recommend Chris Taylor’s Algebra of Algebraic Data Types in particular.

## Product types

Haskell, ML and many other languages support some notion of product and sum types. I will look at product types first.

A product type is a tuple or a record. I think the ML syntax is instructive here.

```
$ rlwrap sml
Standard ML of New Jersey v110.76 [built: Sun Jun 29 03:29:51 2014]
- (4,5);
val it = (4,5) : int * int
```

I created a tuple containing the integers 4 and 5, giving a type signature of int * int. The * looks a lot like the product sign (or multiplication operator) and for good reason.

You could think of the (4,5) being like a co-ordinate in 2d Cartesian space — an ordered pair of x and y. The type signature tells us that both the x and y axes are measured by ints and that the entire possible space that the types cover is x * y.

Perhaps we can make this way of looking at things even more explicit. Let’s call our type point.

```
- type point = int * int;
type point = int * int
- (7,6):point;
val it = (7,6) : point
```

For the sake of simplicity say there were no negative integers and that the maximum int was 1,024 then the "area" in 2d space covered by our type would be:

1,024â‹…1,024

Which is the *product* of the maximum value of each co-ordinate, hence why it is called a product type.

In reality this area is rather larger. From the ML manual

val minInt : int option

val maxInt : int option

The minimal (most negative) and the maximal (most positive) integers, respectively, representable by int. If a value is NONE, int can represent all negative (respectively, positive) integers, within the limits of the heap size.

If precision is SOME(n), then we have:

minInt = -2(n-1) and maxInt = 2(n-1) - 1.

But you get the point (crap pun slightly intended). You can think of tuples as being points in some imaginary space constrained by the types from which they are formed.

Adding extra dimensions or different types makes the imaginary space more complex, but with a bit of mental wiggling I can just about think of co-ordinates in a 3d space with strings on the x axis, ints on the y and chars on the z axis. At least if I have had enough coffee.

```
- ("x12",4,#"z"):point3d;
val it = ("x12",4,#"z") : point3d
```

If you’re more into logic than maths, another nice way to think about product types is as if there were a logical *and* in them — a point3d is a string *and* an int *and* a char. One of the insights in the Curry-Howard isomorphism is that you can associate product types with logical conjunction in just this way.

## Sum types

Sum types are the dual of product types. Also known as discriminated unions, they capture a notion of a type which can be of one value or another — like a disjoint union in set theory or a coproduct in category theory.

Here I think that the logical way of looking at things is nicely reflected in Haskell syntax. I will create a new boolean type with much superior (well, shorter) syntax than the built in boolean type.

```
$ ghci
GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> data Boo = T | F
Prelude> let n = T
Prelude> :t n
n :: Boo
```

The thing to notice here is the symbol (|) for disjuntion — a logical or. A Boo is either T *or* F.

So where does the notion of sum come from?

If you think about the number of values that Boo can have, you can "add them up" that is a Boo’s possible values could be

T + F

Hence why a sum type — you can sum the possible value choices that a Boo could have!

What about more complex sum types? I will carry on "improving" Haskell’s syntax with a Perhaps type — usually known as Maybe in Haskell or an option in Scala or ML.

`data Perhaps a = Perhaps a | BuggerAll deriving (Show)`

The definition is slightly more complicated because I use a polymorphic a as a placeholder for a type and because of deriving Show — that was just so I could print out this to show it worked.

```
Prelude> Perhaps 12
Perhaps 12
Prelude> BuggerAll
BuggerAll
```

Now I can calculate the potential "space" covered by this new sum type. If I know how much space is covered by my a type, it must be that plus the BuggerAll state (of which there is just one).

a + 1

## Wrapping up, other articles

If you’d like a rigorous discussion of the ideas, you may want to look at some of the related links.