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 out own data types in Haskell.

Example: Seasons Type

Seasons is a newly created data type with four possible values:

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

Season is the name of the new 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. The Show allows Season values to be converted to strings so that, among other things, Season values can be printed in the interpreter.

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

> seasonCode :: Season -> String
> seasonCode Winter = "Win"
> seasonCode Spring = "Spr"
> seasonCode Summer = "Sum"
> seasonCode Fall   = "Fall"

Example: Basic Shape Type

BasicShape is a newly created type that represents circles and rectangles. Instead of constant values, it’s types take inputs. The Circle data constructor takes one Float as input (the radius), and the Rect data constructor takes two Floats as input (width and height):

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

Here are some sample functions:

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

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

Notice how these two functions use pattern matching to conveniently bind variables to their inputs.

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

Now we can create the 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)

Again we use underscores for the variables that we don’t care about. Extra variables clutter up the source code, making it harder to read.

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 values of type Maybe a could either be a value of type a, or they could be nothing at all. For instance, you could use Maybe to represent a list that may have some unknown values:

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

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

> :type lst
lst :: [Maybe Integer]

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.

Recursive Type Example: Binary Search Trees

The BST type implements as binary 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 can be any 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:

> let 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]