# Unit 9: Datatypes

## Enumerated types

As the name suggests an enumerated type in Haskell is introduced by listing its members. Say you want to make use of the type `Day` which contains the days of the week:

``````data Day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
deriving (Eq,Ord,Enum,Show)
``````

Note that not only the type `Day` must start with an uppercase letter, but also its members. The `deriving` clause ensures that the identity and ordering relations can be applied to members of `Day`, that they can be converted to integers and that they can be printed to the terminal. If `Enum` is included in the `deriving` clause, the functions `fromEnum` and `toEnum` are available, although they cannot be used directly:

``````fromDay :: Day -> Int

toDay :: Int -> Day
toDay = toEnum
``````

Functions can be defined that make use of user-defined types just as they can with built-in types:

``````weekend :: Day -> Bool
weekend Sun = True
weekend Sat = True
weekend _   = False
``````

## Composite types

``````data Tag = Tagi Int | Tagb Bool
deriving (Eq,Ord,Show)

isInt :: Tag -> Bool
isInt (Tagi _ ) = True
isInt (Tagb _ ) = False
``````

## Recursive types

``````data Btree a = Tip a | Bin (Btree a) (Btree a)
deriving (Eq,Ord,Show)

tree1 = Bin (Tip 1) (Bin (Tip 6) (Tip 5))

size :: Btree a -> Int
size (Tip _)   = 1
size (Bin s t) = size s + size t

depth :: Btree a -> Int
depth (Tip _)   = 0
depth (Bin s t) = 1 + max (depth s) (depth t)

flatten :: Btree a -> [a]
flatten (Tip x)     = [x]
flatten (Bin xt yt) = flatten xt ++ flatten yt

inodes :: Btree a -> Int
inodes (Tip _)     = 0
inodes (Bin xt yt) = 1 + inodes xt + inodes yt

maxBtree :: Ord a => Btree a -> a
maxBtree (Tip x)     = x
maxBtree (Bin xt yt) = max (maxBtree xt) ( maxBtree yt)
``````

It is possible to defines functions on binary trees analogous to the `map` and `fold` functions defined on lists:

``````mapBtree :: (a -> b) -> Btree a -> Btree b
mapBtree f (Tip x) = Tip (f x)
mapBtree f (Bin xt yt)
= Bin (mapBtree f xt) (mapBtree f yt)

foldBtree :: (a -> b) -> (b -> b -> b) -> Btree a -> b
foldBtree f g (Tip x) = f x
foldBtree f g (Bin xt yt)
= g (foldBtree f g xt) (foldBtree f g yt)
``````

Using the catamorphism `foldBtree` it is possible to define all the functions on `Btree` that were defined previously and also `mapBtree`:

``````size1 :: Btree a -> Integer
size1 = foldBtree (const 1) (+) where const x y = x

depth1 :: Btree a -> Integer
depth1 = foldBtree (const 0) op
where op m n = 1 + max m n; const x y = x

flatten1 :: Btree a -> [a]
flatten1 = foldBtree wrap (++) where wrap x = [x]

maxBtree1 :: Ord a => Btree a -> a
maxBtree1 = foldBtree id max

mapBtree1 :: (a -> b) -> Btree a -> Btree b
mapBtree1 f = foldBtree (Tip . f) Bin
``````

© Antoni Diller (31 May 2016)