Making Data Types
=================
.. note:: :doc:`This is a literate Haskell page: you can load it directly into
ghci by following these steps <literate_haskell>`.
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
<https://en.wikipedia.org/wiki/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]