Charlie Harvey

Why sum and product types?

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.


Comments

  • Be respectful. You may want to read the comment guidelines before posting.
  • You can use Markdown syntax to format your comments. You can only use level 5 and 6 headings.
  • You can add class="your language" to code blocks to help highlight.js highlight them correctly.

Privacy note: This form will forward your IP address, user agent and referrer to the Akismet, StopForumSpam and Botscout spam filtering services. I don’t log these details. Those services will. I do log everything you type into the form. Full privacy statement.