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]