User Defined Types in Haskell

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 programmer defined 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 the input to 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 pt _) = pt
location (Rect pt _ _) = pt

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  -- Maybe is 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 can think of Maybe a like a box that either contains an a value, or it is empty and contains Nothing.

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, say, a sensor that, due to hardware imperfections, sometimes returns incorrect results. The Nothing value indicates when an invalid value was returned.

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 idea here is to treat the Nothing values 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 also 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 a generalization of Maybe, and is defined in the standard Haskell prelude like this:

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

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]