*by Carl Burch, Hendrix College, August 2012*

Haskell Types by Carl Burch is licensed under a Creative Commons Attribution-Share Alike 3.0 United States License.

Based on a work at

1. Polymorphic functions

2. Classes

3. Enumerated types

4. Types with nested data

5. Parameterized types

2. Classes

3. Enumerated types

4. Types with nested data

5. Parameterized types

In our function types thus far, we've worked with specific
types. But Haskell also has a feature where functions can work
with arbitrary types.
Recall, for example, our

function.`threshold`

`threshold` **::** `Double` **->** (`Double` **->** `Double`) **->** (`Double` **->** `Double`)

`threshold z f` **=** `g` **where** `g x` **=** `min z` (`f x`)

We've written the type for

so that the
function only works for functions from `threshold`

s to
`Double`

s. But we can be more lenient:
`Double`

would work just as well
on functions from `threshold`

s to `Integer`

s, or for
functions from `Double`

s to `String`

s.`Double`

Enter polymorphic functions, where we can have type “variables” (there's that nasty word again) that represent an abstract type to based on how the function is actually used. In Haskell, each type variable is generally a lower-case letter.

`threshold` **::** `Double` **->** (`Double` **->** `a`) **->** (`Double` **->** `a`)

In this case, we're saying to let `a` be the
type of the first parameter function's parameter;
the returned function's parameter must also be of that type.

The composition function `(.)`

is an interesting case to
study with polymorphic types.
Recall that we defined it as the following.

`f` . `g` **=** `h` **where** `h x` **=** `f` (`g x`) *-- as defined in the Prelude*

Now what's the most general type we could assign to this function?

We'll start with `x`, the parameter to `h`, the return
value, and assign it a type variable

.
Notice that `a``x` is passed to `g` also, so `g` must also take a
parameter of type

.
Let's suppose that `a``g` returns a value of type

(which may or may not be the same as `b`

).
To compute `a``h`, the return value of `f` is passed into `f`, so
`f`'s parameter type must be

.
Whatever `b``f` returns — call it

— is likewise
returned by `c``h`. This leads to the following type declaration.

`(.) `**::** (`b` **->** `c`) **->** (`a` **->** `b`) **->** (`a` **->** `c`)

Below is a definition of the built-in function

. What
type should it have?`min`

`min x y` **= if** `x` < `y` **then** `x` **else** `y`

The simple thing to do would be to define

to
simply take two `min`

s as parameters and return a
`Double`

. But declaring it that way means that we can't
use `Double`

to work on integers or strings — though it
seems quite reasonable that it should work on integers and
strings. We'd like a more generic type for this function.`min`

We can see that

, `x`

, and the return value must all
be of the same type, which suggests “`y`

” as
`a` **->** `a` **->** `a`

's type. But this is too broad: We have to be able to use the
less-than operation on `min`

and `x`

. We need some way
to be able to constrain `y`

to be a type that supports
less-than comparisons.`a`

Haskell has an answer for that, called **classes**, where
we can say that a type belongs to a class (is a **class
instance**) since it includes functions that the class
requires.
Despite the usage of the word *class* and
*instance*, this has nothing
to do with object-oriented programming; a Haskell *class*
is closer to a Java *interface*.

In this case, we want the built-in class named

.
To be an instance of that class, a type must include the
comparison operators
`Ord``<`

,
`>`

,
`<=`

,
`>=`

,
`==`

, and
`/=`

. The built-in types

and `Integer`

are instances of the `Double`

class (as is `Ord`

).`String`

The following type signature indicates that

's type
uses a type variable `min`

that must represent an instance
of `a`

:`Ord`

`min` **::** `Ord a` **=>** `a` **->** `a` **->** `a`

We can similarly use

to give `Ord`

additional flexibility, so that it can work with functions whose
return values are strings or integers, in addition to functions
whose return values are `threshold`

s.`Double`

`threshold` **::** `Ord a` **=>** `a` **->** (`b` **->** `a`) **->** (`b` **->** `a`)

We can also define new types beyond those built into Haskell. For example, suppose that we want to have a type for playing cards. We first want to declare a data type for card suits, which we can accomplish as follows.

**data** `Suit` **=** `Clubs` **|** `Diamonds` **|** `Hearts` **|** `Spades`

In this case, we've declared that

is a new type
with four possible values.
We could very reasonably wish to ensure that this new `Suit`

type is an instance of some class.
For example, if we want to allow the equality operator `Suit``==`

to apply to

s, we might write the following.`Suit`

**instance** `Eq Suit` **where**

`Clubs` == `Clubs` **=** `True`

` Diamonds` == `Diamonds` **=** `True`

` Hearts` == `Hearts` **=** `True`

` Spades` == `Spades` **=** `True`

` x` == `y` **=** `False`

The first line here says that we're trying to justify that

is part of the `Suit`

class, a built-in class
that includes `Eq``==`

and `/=`

. (We saw

earlier: It extends `Ord`

by adding the comparison operators
`Eq``<`

, `<=`

, `>`

and >= ?.)
Following the

, we need to define the **where**`==`

operator as it applies to

.
In this case, we define `Suit``==`

by first listing the cases
where they are equal, and then by listing a catch-all case so
that any other combination is treated as unequal.

The

class also requires the `Eq``/=`

operator.
However, it also defines that if `/=`

is not defined for a type,
then it can be derived from the definition of `==`

.
So we can safely omit it, and `/=`

will automatically be
defined for

based on our definition of `Suit``==`

.

Our definition of

's `Suit``==`

function does
look rather repetitive. In fact, Haskell provides a shortcut
for types that simply enumerate the possible values, including

: When we define the type, we use the `Suit`

keyword
to indicate that a default implementation should be defined.**deriving**

**data** `Suit` **=** `Clubs` **|** `Diamonds` **|** `Hearts` **|** `Spades` **deriving** (`Eq`, `Show`)

Here, we've said that our new

type should be given
a simplistic definition of `Suit`

and `Eq`

. The
default definition for `Show`

is what we have already seen.
We haven't seen the `Eq`

class, but it requires the
definition of the `Show`

function that maps values of the
class to strings. Because `show`

now is an instance of `Suit`

,
we can give a `Show`

value to the `Suit`

function to
get its corresponding string: “`show`

”
yields the string “`show Hearts``Hearts`”.

Note that

can **deriving***only* be used for
data types that are defined by listing the individual values to
be used. In the remainder of this document, we'll define some
other data types (

and `Card`

) that are
more flexible, and we cannot use `BinTree`

for them.**deriving**

Now that

is defined, we can go on to define the
type for an individual playing card. One way we could do this
would be to simply list all the possible values
(`Suit`

, `AceOfSpades`

, `TwoOfClubs`*et cetera*),
but that's unwieldy. Instead, we'll build up the type using
other types at our disposal.

**data** `Card` **=** `Joker` **|** `Ranked Integer Suit`

We've listed

as one particular value that
`Joker`

can have. But we've also listed `Card`

,
which is essentially a two-parameter function that creates a
`Ranked`

value. In a program, I could write
“`Card`

” to represent the two of
clubs.`Ranked` `2` `Clubs`

To define a function involving cards, we will typically use pattern-matching both to address possible cases and to retrieve any data nested in the value.

`isFaceCard` **::** `Card` **->** `Bool`

`isFaceCard Joker` **=** `False`

`isFaceCard` (`Ranked r s`) **=** `r` > `10`

We can similarly use this pattern-matching technique to indicate that we should be able to test whether two cards are equal.

**instance** `Eq Card` **where**

`Joker` == `Joker` **=** `True`

` Ranked r s` == `Ranked r' s'` **=** `r` == `r'` && `s` == `s'`

` Joker` == `Ranked r s` **=** `False`

` Ranked r s` == `Joker` **=** `False`

We haven't seen strings yet, but we'll soon see that we can
use double-quotes to talk about a string constant and `++`

to catenate two strings together. Using this, we can define

as an instance of `Card`

as well.`Show`

**instance** `Show Card` **where**

`show Joker` **=** `"Joker"`

`show` (`Ranked r s`) **=** (`show r`) ++ `" of "` ++ (`show s`)

When we define a data type, we're also allowed to include a
variable that represents some other type. (This is akin to a
*generic class* in Java or *template* in C++.)
For example, we would want to define a binary tree so that the
type of value stored in each node can be customized.

**data** `BinTree a` **=** `Empty` **|** `Node a` (`BinTree a`) (`BinTree a`)

With this in hand, we can now work with a

,
or a `BinTree Integer`

, or even a `BinTree String`

.
Note that in any of these cases, it is a recursive type:
A `BinTree Card`

has not only a value but also two more
`Node`

's within it (but of the same types as the overall
tree.`BinTree`

The following illustrates how one can creating a particular binary tree (namely, the one illustrated at right).

`ps` **=** `Node` `7`

(`Node` `3` (`Node` `2` `Empty Empty`) (`Node` `5` `Empty Empty`))

(`Node` `11` `Empty Empty`)

One function we might want to define on this is a function to compute the height of a tree. In this case, we don't care about the individual values stored in the tree at all.

`depth` **::** `BinTree a` **->** `Integer`

`depth Empty` **=** `0`

`depth` (`Node` **_** `left right`) **=** `1` + `max` (`depth left`) (`depth right`)

A more involved function would be to use this for a binary
search tree, and then to define a function to determine whether
a value exists in the tree. We'll need the values to have the
various comparison operators associated with it, so we'll need
to require that the values within each node have a type that
conforms to the

class.`Ord`

`contains` **::** `Ord a` **=>** `a` **->** `BinTree a` **->** `Bool`

`contains x Empty` **=** `False`

`contains x` (`Node val left right`) **= if** `x` == `val` **then** `True`

**else if** `x` < `val` **then** `contains x left`

**else** `contains x right`

Now let's define

to be an instance of the
`BinTree`

class. Doing this will involve testing that the value
within each corresponding node is equal, so we will need the
values' type itself to be an instance of the `Eq`

class.
We'd wrie this constraint into the first line as follows.`Eq`

**instance** `Eq a` **=>** `Eq` (`BinTree a`) **where**

`Empty` == `Empty` **=** `True`

(`Node v lft rt`) == (`Node v' lft' rt'`) **=** `v` == `v'` && `lft` == `lft'` && `rt` == `rt'`

Similarly, we can define

to be an instance of
`BinTree`

, but we'll need a way to convert each individual
value within each node into a string — so the type of the
node's values would need to be an instance of sh Show ? as
well.`Show`

**instance** (`Show a`) **=>** `Show` (`BinTree a`) **where**

`show Empty` **=** `"()"`

`show` (`Node val Empty Empty`) **=** `"("` ++ (`show val`) ++ `")"`

`show` (`Node val left right`) **=** `"("` ++ (`show val`) ++ `" "` ++

(`show left`) ++ `" "` ++ (`show right`) ++ `")"`

Finally, let's define an

function that adds a
value into a binary search tree. In an imperative language, we'd
do this by altering a single pointer at the bottom of the tree
to point to a new node (figure (a) below).
Of course, this isn't possible in a functional
language, since it involves changing the state of the tree.
But we can simply “rebuild” the nodes along the path
to where the value should be inserted (figure (b) below).`insert`

(a) imperative insert | (a) functional insert |

The following function definition implements this rebuilding process to construct a new root with the value inserted.

`insert` **::** `Ord a` **=>** `a` **->** `BinTree a` **->** `BinTree a`

`insert x Empty` **=** `Node x Empty Empty`

`insert x` (`Node val left right`) **= if** `x` < `val`

**then** `Node val` (`insert x left`) `right`

**else** `Node val left` (`insert x right`)