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 Integer
s:
> 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 Nothing
s 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]