Making Data Types

Haskell has a number of ways to create new types. For instance, you can create a new type consisting of finite values like this:

> data Semester = Spring | Summer | Fall
>     deriving (Show, Eq, Enum)

This is similar to enumerated types in languages like C++ or Java. The deriving statement adds some convenience functions: Show converts the type values to strings (of the same name), Eq allows for comparisons with == and \=, and Enum allows the use of functions like succ (successor) and pred (predecessor). For example:

> show Fall
"Fall"

> Spring == Summer
False

> Spring /= Summer
True

> succ Spring
Summer

> pred Spring
*** Exception: pred{Semester}: tried to take `pred' of first tag in enumeration

> pred Fall
Summer

A type synonym is another name for an existing type, and it works essentially the same way as typedef in C/C++. In Haskell, use type to create a type synonym:

> type Year = Int  -- type synonym
>
> data Campus = Burnaby | Surrey | Vancouver
>    deriving (Show, Eq, Enum)
>
> type CourseOffering = (Year, Semester, Campus)  -- type synonym

Here, CourseOffering is another name for the type (Year, Semester, Campus).

Algebraic Data Types

Types created with data are called algebraic data types, and they go well beyond the enumerations of C++ or Java. For instance, consider this type:

> data Shape = Circle Float | Rectangle Float Float
>      deriving (Show)

Shape is a type that denotes either a Circle or a Rectangle object. A Circle takes one Float value (representing it’s radius) as input, while a Rectangle takes two Float values (its width and height). Circle and Rectangle are called value constructors.

For example:

> area :: Shape -> Float
> area (Circle radius)          = pi * radius ^ 2  -- pi is pre-defined in Haskell
> area (Rectangle width height) = width * height

> area (Circle 2) 12.56

> area (Rectangle 4 6) 24.0

Parameterized Types

Haskell also 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 be some value of type a, or they could be nothing at all. For instance, you could use Maybe to represent a list of values, where some of the values are unknown:

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

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

> :type lst
lst :: [Maybe Integer]

Here’s how you could sum a list of Maybe Integers:

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

The basic idea is that for each value on the list we check to see if it is Nothing, or if it is an integer. We’ve decided to treat Nothing as equivalent to 0 here, but for other functions it might make more sense to use a different value, e.g. for a maybeProduct function it would make more sense to treat Nothings as equivalent to 1.

You can 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

However, you can’t directly use the result of invert in calculations 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

Recursive Data Structures

In addition to type parameters, you can write recursive data types such as BST (short for 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 (EmptyBST), 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)
> 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]