User Defined Types in Haskell

Note

This is a literate Haskell page: you can load it directly into ghci by following these steps.

In this note, we’ll look at how to define our own data types in Haskell.

Example: Seasons Type

Seasons is an example of a user-created data type:

> data Season = Winter | Spring | Summer | Fall
>    deriving (Eq, Show)

Season is the name of the type, and it’s four possible values are Winter, Spring, Summer, and Fall. It is similar to an enumerated type in a language like C++ or Java.

The Eq in the deriving clause lets us use == and /= with Season. Show lets Season values be converted to strings so that, for instance, they can be printed in the interpreter.

For example:

> Winter
Winter

> :type Winter
Winter :: Season

> Summer == Fall
False

> Summer /= Summer
False

Here’s an example of how to use it in a function:

> seasonCode :: Season -> Int
> seasonCode Winter = 1
> seasonCode Spring = 2
> seasonCode Summer = 4
> seasonCode Fall   = 6

For example:

> seasonCode Spring
2

> seasonCode Fall
6

Example: Basic Shape Type

BasicShape is a newly created type that represents circles and rectangles. It has two values, and both take inputs. Circle is a data constructor for BasicShape, and it takes one Float as input (the radius), while Rect is a data constructor that takes two Floats as input (width and height):

> data BasicShape = BasicCircle Float | BasicRect Float Float
>    deriving Show

For example:

> BasicCircle 5
BasicCircle 5.0

> :type BasicCircle 5
BasicCircle 5 :: BasicShape

> BasicRect 2.2 3
BasicRect 2.2 3.0

> :type BasicRect 2.2 3
BasicRect 2.2 3 :: BasicShape

Give a BasicShape value, we don’t know if it’s a circle or a rectangle, so we have to check for both cases. For example:

> basicArea :: BasicShape -> Float
> basicArea (BasicCircle r) = pi * r^2
> basicArea (BasicRect w h) = w * h

Each equation in basicArea defines area formula for the possible shapes.

You call it like this:

> basicArea (BasicCircle 2)
12.566371

> basicCircum (BasicRect 2 4)
12.0

Here’s another function that calculates the circumference of a basic shape:

> basicCircum :: BasicShape -> Float
> basicCircum (BasicCircle r) = 2 * pi * r
> basicCircum (BasicRect w h) = 2 * (w + h)

Again, notice that we handle each case of BasicShape separately.

Example: the Shape Type

Here’s a slightly more sophisticated example where we use a Point data type to create a Shape date type:

> data Point = Point Float Float
>    deriving (Show, Eq)

This function calculates the distance between two points:

> dist :: Point -> Point -> Float
> dist (Point x1 y1) (Point x2 y2) = sqrt (dx^2 + dy^2)
>                                    where dx = x1-x2
>                                          dy = y1-y2

As an aside, we can now define a function that calculates the distance from a point to the origin very simply like this:

> dist_to_origin :: Point -> Float
> dist_to_origin = dist (Point 0 0)

Since dist is a curried function, dist (Point 0 0) evaluates to a function that takes one Point as input and returns a Float. Notice there is no need to write an variable for dist_to_origin.

Now lets create a Shape data type that uses Point:

> data Shape = Circle Point Float | Rect Point Float Float
>     deriving (Show, Eq)

The idea is that a circle stores its location and radius, and a rectangle stores its location and dimensions.

Here are some sample functions:

> area :: Shape -> Float
> area (Circle (Point x y) r) = 2 * pi * r
> area (Rect (Point x y) w h) = 2 * (w + h)

Notice that we don’t need a shape’s location to calculate its area, and so we could write underscores in place of x and y:

-- Alternative implementation using _ for unused variables:
area :: Shape -> Float
area (Circle _ r) = 2 * pi * r
area (Rect _ w h) = 2 * (w + h)

Next, here’s a helper function for getting a shape’s location:

> location :: Shape -> Point
> location (Circle (Point x y) _) = (Point x y)
> location (Rect (Point x y) _ _) = (Point x y)

Notice how Haskell’s pattern matching makes it relatively easy for us to extract the data in Shape objects. Again, underscores are put in place of unused variable names to avoid cluttering up the source code.

And finally a function that calculates the distance between two shapes:

> shapeDist :: Shape -> Shape -> Float
> shapeDist s1 s2 = dist (location s1) (location s2)

Parameterized Type Example: Maybe

Haskell lets you create types that take a type as input, e.g.:

data Maybe a = Nothing | Just a  -- pre-defined in Haskell

Here, a is a type variable that can be any type. The idea is that a value of type Maybe a could either be a value of type a, or it could be nothing at all. You might find it useful to think about a Maybe a value as a box: the box either contains an a value, or it is empty and contains nothing.

For instance, you could use Maybe to represent a list that may have some unknown values:

> lst = [Just 3, Just 6, Nothing, Just 2]

> lst
[Just 3,Just 6,Nothing,Just 2]

> :type lst
lst :: [Maybe Integer]

This kind of list might be generated by a hardware sensor that, due to hardware errors, sometimes returns incorrect results. The Nothing value indicates when a invalid value occurs.

You can sum a list of Maybe Integers like this:

> maybeSum :: [Maybe Integer] -> Integer
> maybeSum []            = 0
> maybeSum (Nothing:xs)  = maybeSum xs
> maybeSum ((Just x):xs) = x + (maybeSum xs)

The basic idea is to ignore the Nothing values, i.e. treat them as 0.

You can also use Maybe in calculations where the result might fail, e.g.:

> safeInvert :: Float -> Maybe Float
> safeInvert 0.0 = Nothing
> safeInvert x   = Just (1.0 / x)

For instance:

> safeInvert 2
Just 0.5

> safeInvert 0
Nothing

You can’t directly use the result of invert in calculations with Haskell’s regular arithmetic operators, like + and *, because it returns values of type Maybe Float, not Float. You are forced to handle the case when the result is Nothing, which, while perhaps tedious, ensures errors are not ignored.

> maybeAdd :: Maybe Float -> Maybe Float -> Maybe Float
> maybeAdd Nothing _         = Nothing
> maybeAdd _ Nothing         = Nothing
> maybeAdd (Just x) (Just y) = Just (x + y)

For example:

> maybeAdd (safeInvert 2) (safeInvert 2)
Just 1.0

> maybeAdd (safeInvert 2) (safeInvert 0)
Nothing

Parameterized Type Example: Either

The Either type is defined in the standard Haskell prelude like this:

data Either a b = Left a | Right b   -- defined in the prelude

So the type Either a b represents a single value that is either of type a, or of type b. For example:

> :type [Left 1, Right "cat", Left 2, Right "dog"]
Num a => [Either a [Char]]

In a way, this lets us have lists stores two different types of values.

Either a b is often used as an error type, where the a value is the error result, and the b is the non-error (i.e. the “right”) result.

Recursive Type Example: Binary Search Trees

As another example of parameterized types, lets implement a basic binary search tree:

> data BST a = EmptyBST | Node a (BST a) (BST a)
>      deriving (Show, Read, Eq)

This says that a BST is either empty, or it is a Node consisting of a value of type a (i.e. the data stored in the node), and two trees of type BST a (i.e. the left and right subtrees of the node).

For example:

> bstInsert :: Ord a => BST a -> a -> BST a
> bstInsert EmptyBST x              = Node x EmptyBST EmptyBST
> bstInsert (Node val left right) x = if x < val then
>                                         Node val (bstInsert left x) right
>                                     else
>                                         Node val left (bstInsert right x)

Ord a says that type a must be a type that can be compared with operators like < and >=.

> bstInsert (bstInsert EmptyBST 5) 9
Node 5 EmptyBST (Node 9 EmptyBST EmptyBST)

> bstInsert (bstInsert (bstInsert EmptyBST 5) 9) 2
Node 5 (Node 2 EmptyBST EmptyBST) (Node 9 EmptyBST EmptyBST)

> bstInsert (bstInsert (bstInsert (bstInsert EmptyBST 5) 9) 2) 3
Node 5 (Node 2 EmptyBST (Node 3 EmptyBST EmptyBST)) (Node 9 EmptyBST EmptyBST)

bstContains tests if a value is a BST or not:

> bstContains :: Ord a => BST a -> a -> Bool
> bstContains EmptyBST _              = False
> bstContains (Node val left right) x
>            | val == x = True
>            | val < x  = bstContains right x
>            | val > x  = bstContains left x

For example:

> t = bstInsert (bstInsert (bstInsert (bstInsert EmptyBST 5) 9) 2) 3

> bstContains t 3
True

> bstContains t 4
False

An inorder traversal of a BST visits the elements in ascending sorted order:

> bstInorder :: BST a -> [a]
> bstInorder EmptyBST              = []
> bstInorder (Node val left right) = (bstInorder left) ++ [val] ++ (bstInorder right)

For example:

> let t = bstInsert (bstInsert (bstInsert (bstInsert EmptyBST 5) 9) 2) 3

> bstInorder t
[2,3,5,9]

We can now implement a basic version of tree sort. Just insert all the elements of a list into a BST, and then extract them with bstInorder:

> toBST :: Ord a => [a] -> BST a
> toBST []     = EmptyBST
> toBST (x:xs) = bstInsert (toBST xs) x
>
> treesort :: Ord a => [a] -> [a]
> treesort x = bstInorder (toBST x)

For example:

> treesort [81, 79, 81, 82, 90, 77, 75]
[75,77,79,81,81,82,90]