Algebraic Datatypes

Haskell has a system called algebraic datatypes for defining new types. This sounds fancy, but is rather simple. Let’s dive in by looking at the standard library definitions of some familiar types:

data Bool = True | False
data Ordering = LT | EQ | GT

With this syntax you too can define types:

-- definition of a type with three values
data Color = Red | Green | Blue

-- a function that uses pattern matching on our new type
rgb :: Color -> [Double]
rgb Red = [1,0,0]
rgb Green = [0,1,0]
rgb Blue = [0,0,1]

Prelude> :t Red
Red :: Color
Prelude> :t [Red,Blue,Green]
[Red,Blue,Green] :: [Color]
Prelude> rgb Red
[1.0,0.0,0.0]

Fields

Types like Bool, Ordering and Color that just list a bunch of constants are called enumerations or enums in Haskell and other languages. Enums are useful, but you need other types as well. Here we define a type for reports containing an id number, a title, and a body:

data Report = ConstructReport Int String String

This is how you create a report:

Prelude> :t ConstructReport 1 "Title" "This is the body."
ConstructReport 1 "Title" "This is the body." :: Report

You can access the fields with pattern matching:

reportContents :: Report -> String
reportContents (ConstructReport id title contents) = contents
setReportContents :: String -> Report -> Report
setReportContents contents (ConstructReport id title _contents) = ConstructReport id title contents

Constructors

The things on the right hand side of a data declaration are called constructors. True, False, Red and ConstructReport are all examples of constructors. A type can have multiple constructors, and a constructor can have zero or more fields.

Here is a datatype for a standard playing card. It has five constructors, of which Joker has zero fields and the others have one field.

data Card = Joker | Heart Int | Club Int | Spade Int | Diamond Int

Constructors with fields have function type and can be used wherever functions can:

Prelude> :t Heart
Heart :: Int -> Card
Prelude> :t Club
Club :: Int -> Card
Prelude> map Heart [1,2,3]
[Heart 1,Heart 2,Heart 3]
Prelude> (Heart . (\x -> x+1)) 3
Heart 4

Sidenote: Deriving

By the way, there’s something missing from our Card type. Look at how it behaves compared to Ordering and Bool:

Prelude> EQ
EQ
Prelude> True
True
Prelude> Joker
<interactive>:1:0:
    No instance for (Show Card)
        arising from a use of `print' at <interactive>:1:0-4
    Possible fix: add an instance declaration for (Show Card)
    In a stmt of a 'do' expression: print it

The problem is that Haskell does not know how to print the types we defined. As the error says, they are not part of the Show class. The easy solution is to just add a deriving Show after the type definition:

data Card = Joker | Heart Int | Club Int | Spade Int | Diamond Int
    deriving Show

Prelude> Joker
Joker

The deriving syntax is a way to automatically make your class a member of certain basic type classes, most notably Read, Show and Eq. We’ll talk more about what this means later.

Algebraic?

So why are these datatypes called algebraic? This is because, theoretically speaking, each datatype can be a sum of constructors, and each constructor is a product of fields. It makes sense to think of these as sums and products for many reasons, one being that we can count the possible values of each type this way:

data Bool = True | False            -- corresponds to 1+1. Has 2 possible values.
data TwoBools = TwoBools Bool Bool  -- corresponds to Bool*Bool, i.e. 2*2. Has 4 possible values.
data Complex = Two Bool Bool | One Bool | None
                                    -- corresponds to Bool*Bool+Bool+1 = 2*2+2+1 = 7. Has 7 possible values.

There is a rich theory of algebraic datatypes. If you’re interested, you might find more info here or here.

Exercises

All exercises can be found in Set5a and Set5b. Please pay attention in the title of the exercise in which file the exercises of this section can be found.

Exercises from 5a:

You can check your current points from the blue blob in the bottom-right corner of the page.