Sum type #

A sum type represents several alternative types.

in Haskell #

Syntax. A sum type in Haskell is declared as

data <sum type name> = <type 1> | ... | <type n>

Example. In the following declarations:

• Point is a product type, and
• Shape is a sum type.

-- a point in the Euclidean plane, represented by its coordinates
data Point = PointC Float Float

-- a shape, defined as either a triangle or a rectangle
data Shape = TriangleC Point Point Point | RectangleC Point Point Point Point

Note. in Haskell, an enumerated type is a sum type.

Precisely, the alternative “values” of an enumerated type are nullary constructors (i.e. constructors with no argument).

Pattern matching #

Like an enumerated type, a sum type lets us use alternative patterns.

Example (continued). Let us define a function perimeter that maps a Shape to its perimeter.

First, we define an auxiliary function distance that maps two points to their distance:

distance :: Point -> Point -> Float
distance (PointC x1 y1) (PointC x2 y2) = sqrt ( (x2 - x1) ^ 2 + (y2 - y1) ^ 2 )

We can now define our main function:

perimeter :: Shape -> Float
perimeter (TriangleC p1 p2 p3) = distance p1 p2 + distance p2 p3 + distance p1 p3
perimeter (RectangleC p1 p2 p3 p4) = 2 * (distance p1 p2 + distance p2 p3)

Recursive type #

A type can appear in its own definition.

Example. The following type is equivalent to the type [Int]:

data IntList = Nil | Cons Int IntList

where Nil stands for the empty list, and Cons stands for :.

We can rewrite our recursive function sum accordingly:

data IntList = Nil | Cons Int IntList
sum :: IntList -> Int
sum Nil = 0                    -- base case
sum (Cons x xs) = x + sum xs   -- inductive case

To go further. Recursive types are the standard way to define trees (and several other recursive structures) in Haskell.

Due to limited time, we will not study trees (or more generally, n-ary recursion) in Haskell, but in Java instead.