Algebraic Datatypes

While functions are, of course, central in functional programming, they have to have values to process. Haskell classifies values by means of types and provides a number of built-in types such as Integer and Bool. Yet, these integer types are rather limited and rather generic. For this reason, Haskell provides a facility for defining user-defined datatypes, called algebraic datatypes.

This chapter explains how algebraic datatypes work. We first study two simple forms of algebraic datatypes (enumerations and records) that have well-known counterparts in other programming languages. Then, we merge the two features into the full-blown form of algebraic datatypes. We learn about the different elements of an algebraic datatype definition: the type name, the data constructors, and their fields. We see how algebraic datatype values are created and how they are taken apart by pattern matching. Finally, we see how both functions and algebraic datatypes can be parameterized...

Enumerations

We start with one of the simplest use cases of ADTs, which are often called enumerations, or enums for short. An enumeration type is a type with a finite number of distinct values. Many programming languages provide specific support for enums, but in Haskell, they are just a special case of ADTs and not especially distinguished from other ADTs.

A game of rock-paper-scissors

We illustrate the use of enumeration types with the well-known game of rock-paper-scissors.

Rock-paper-scissors is a two-player game. There are three possible outcomes for the first player (and likewise for the second player) – lose, draw, or win:

data Outcome = Lose | Draw | Win

The data keyword signals that this is the definition of a new datatype. Next comes the name of the new datatype, Outcome. Finally, the possible values are enumerated: Lose, Draw, and Win. These values are called data constructors, value constructors, or constructors for short. Observe that both the names...

Records

A second use case of ADTs is often called record or struct types. The purpose of records is to group or structure several related pieces of data.

People

We create the Person ADT as a first simple example of a record datatype:

data Person = MkPerson String Int

Just like in the previous section, a new ADT is announced by the data keyword, followed by the name of the new type, which is Person in this case. Whereas the enumeration examples were defined in terms of a number of alternatives separated by | characters, a record type has only one alternative. This alternative is the MkPerson data constructor. What’s new is that this constructor takes two parameters, also called fields, of the String and Int types, respectively.

We create a new Person by calling the constructor on values of the appropriate type:

tom :: Person
tom = MkPerson "Tom" 45

In fact, the constructor behaves essentially like a function:

*Main> :t MkPerson
MkPerson :: String...

Full-blown algebraic datatypes

Full-blown algebraic datatypes combine the capabilities of both enumeration types and record types. Indeed, an ADT can have one or more data constructors, and each data constructor can have zero or more fields.

Shapes

The following Shape datatype features two constructors with a number of fields:

data Shape = Circle Double
           | Rectangle Double Double

A shape can be either a circle with a given radius or a rectangle with a given width and height. The next function computes the area of such a shape:

area :: Shape -> Double
area (Circle r)      = pi * r**2
area (Rectangle w h) = w * h

This function has two equations, one with a pattern for each of the two Shape constructors. This case analysis is a common template for writing functions over an ADT. The general shape of such a function for Shape is as follows:

f :: Shape -> …
f (Circle...

Parametric polymorphism

While we have so far been focusing on custom ADTs and functions that process them, there are actually other functions that do not care about the type of values they are processing. Such functions are (parametrically) polymorphic.

The identity function

One of the most trivial functions is the identity function, which just returns its input. What should be the type of this function? It works on any possible type of input. Thus we could create many copies of this function, one for each type we want to use it with:

idInt :: Int -> Int
idInt x = x
idBool :: Bool -> Bool
idBool x = x
idChar :: Char -> Char
idChar x = x

However, this leads to an unfortunate duplication of essentially the same logic. Moreover, our job is never done, as we would have to write another copy whenever we create a new ADT. Hence, instead, Haskell allows us to write a single generic definition that simultaneously works at all types:

Prelude
id :: a -> a
id x = x

...

Parametric ADTs

In this section, we integrate parametric polymorphism in algebraic datatypes.

Tuples

Haskell already has several parametric datatypes built in. A common family of these are generic record types, where the types of the fields are parameters, known as tuples.

If we were to define such tuple types ourselves as ADTs, we would probably write something like this:

data Tuple2 a b     = MkTuple2 a b
data Tuple3 a b c   = MkTuple3 a b c
data Tuple4 a b c d = MkTuple4 a b c d
…

However, the actual built-in tuple types come with a special syntax, following the mathematical notation for tuples. The type names are written as a pair of parentheses with a comma-separated list of type parameters between them:

(a,b)
(a,b,c)
(a,b,c,d)
…

Tuple values are written with essentially the same syntax:

*Main> :t ('a',True)
('a',True) :: (Char,Bool)

The ('a',True) tuple value has the...

Summary

This chapter has explained to us how to define and use algebraic datatypes, with pattern matching as a notable concept for taking values apart. First, we have seen the restricted forms of enumeration types and record types. Next, we have seen how these can be in their more general form by combining features of the two. We have also introduced parametric polymorphism, a powerful mechanism for abstracting over types, that can be used in function signatures and in the definition of algebraic datatypes.

In Chapter 3, Recursion, we will learn about recursive definitions, which can be used for both functions and datatypes. Recursive function definitions are the counterpart of imperative loops and enable (both bounded and unbounded) repetition of computation. Recursive datatype definitions enable data structures of arbitrary size and are typically processed by recursive functions.

Questions

1. How can you define and use enumeration types?
2. How does the record syntax work?
3. What do algebraic datatype definitions look like and how do you use them?
4. How can the same function definition be reused for different types of input?
5. How can the same datatype definition be reused for different types of fields?

Answers

1. Enumeration types are defined with the syntax data ET = K1 | … | Kn, where ET is the name of the type and K1…Kn are the names of the data constructors. Each of the constructors is a value of the enumeration type. Values can be distinguished by means of pattern matching, writing one equation of a function per constructor:

   f K1 = ..
   …
   f Kn = …

2. Record types are defined with the syntax data RT = RK {f1 :: T1, …, fn :: Tn}, where RT is the name of the record type and RK is its constructor. The fields are named f1...fn and have the T1...Tn types, respectively. A value of RT is created with the syntax RT { f1 = e1, …, fn=en}, where e1...en are expressions of the T1...Tn types that yield the values for the fields. Given a value of the record type, a field can be extracted by using the field name as a function, fi :: RT -> Ti.
3. An algebraic datatype is defined with the syntax data AT = K1 T11… | … | Kn Tn1 …...