Functional Programming
12. Types

## 12.1 Expression Trees

In the previous section we defined a simple binary tree data structure (BinTree), and two operations (makeBinTree and size). This is a simple algebraic data type.

We also have a defintion of binary expression trees (ExpTree). Note how this has the names 'a' and 'f' which are type variables. This enables us to construct polymorphic data types. The type variables serve to both parameterize the structure, and to restrict it. So in the expression trees, once you start with an integer at the leaf, you need to make sure all values are integers and all the functions are the same type. In this case, the function need not actually operate on the type expressed for the leaves.

 `    ``-- Here is a simple binary tree, with only structure, no data in it` `    `` ` `    ``data BinTree = L | N BinTree BinTree deriving (Eq, Show)` `    `` ` `    ``-- and two functions on BinTree` `    `` ` `    ``makeBinTree 0 = L` `    ``makeBinTree n = N (makeBinTree (n-1)) (makeBinTree (n-1))` `    `` ` `    ``size L = 1` `    ``size (N t1 t2) = 1 + size t1 + size t2` `    `` ` `    ``-- Now lets build expression trees` `    ``-- a is the type of the values in the tree, ` `    ``-- f is the type of the operations performed on the values` `    `` ` `    ``data ExpTree a f = V a | Op f (ExpTree a f) (ExpTree a f) deriving (Eq, Show)` `    `` ` `    ``t1 = (Op (+) (V 10) (V 20))` `    `` ` `    ``t2 = (Op (*) (V 4) (V (- 1)))` `    `` ` `    ``t3 = (Op (+) t1 t2)` `    `` ` `    ``-- and here is an evaluator on expression trees` `    ``evalExp (V n) = n` `    ``evalExp (Op f e1 e2) = (f (evalExp e1) (evalExp e2))` `    `` ` `    ``-- evalExp t1` `    ``-- evalExp t2` `    ``-- evalExp t3` `    `` ` `    ``-- Note that the trees are functions of the types, so here is a tree containing` `    ``-- lists, and operations between lists` `    `` ` `    ``tl1 = (V [1, 2, 3])` `    ``tl2 = (V [4, 5, 6, 7])` `    ``tl3 = (Op (++) tl1 tl2)` `    `` ` `    ``-- evalExp tl1` `    ``-- evalExp tl2` `    ``-- evalExp tl3` `    `` ` `    ``-- Now try ` `    ``-- tm1 = (Op (++) tl3 t3)` `    `` `
 `    ``--` `    ``-- pairs of Int` `    ``--` `    `` ` `    ``data Pair = P Int Int deriving (Show, Eq)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y` `    `` ` `    ``instance Ord Pair where` `    ``  compare (P x1 y1) (P x2 y2) = ` `    ``    case compare x1 x2 of EQ -> compare y1 y2` `    ``                          LT -> LT` `    ``                          GT -> GT` `    ``--` `    ``-- pairs of things of type a` `    ``--` `    `` ` `    ``data Pair a = P a a deriving (Show, Eq)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y` `    `` ` `    ``-- ordering on same kinds of pairs pairs of the same type of thing` `    `` ` `    ``instance Ord a => Ord (Pair a) where` `    ``  compare (P x1 y1) (P x2 y2) = ` `    ``    case compare x1 x2 of EQ -> compare y1 y2` `    ``                          LT -> LT` `    ``                          GT -> GT` `    ``--` `    ``-- pairs of things of type a and b` `    ``--` `    `` ` `    ``data Pair a b = P a b deriving (Show, Eq)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y` `    `` ` `    ``-- ordering on same kinds of pairs pairs of the same type of thing` `    `` ` `    ``instance (Ord a, Ord b) => Ord (Pair a b) where` `    ``  compare (P x1 y1) (P x2 y2) = ` `    ``    case compare x1 x2 of EQ -> compare y1 y2` `    ``                          LT -> LT` `    ``                          GT -> GT` `    ``--` `    ``-- pairs of things of type a and b, automatic deriving` `    ``--` `    `` ` `    ``data Pair a b = P a b deriving (Show, Eq, Ord)` `    `` ` `    ``pairFst (P x y ) = x` `    ``pairSnd (P x y ) = y` `    `` ` `    ``:t (<) P 1 2` `    ``:t (<) P 1 'a'` `    ``:t (<) P 1 "a"` `    `` ` `    `` ` `    ``--` `    ``-- fancier data types` `    ``--` `    `` ` `    ``data Fn1 = Fn1 (Int -> Int)` `    ``exec1 (Fn1 f) = f 0` `    `` ` `    ``data Fn2 a = Fn2 (a -> a)` `    ``exec2 (Fn2 f) = f 0` `    `` ` `    ``-- Fn1 2` `    ``-- :t (Fn2 (\x -> x ++ "hello"))` `    `` ` `    ``--` `    ``-- type synonyms` `    ``--` `    `` ` `    ``type Inc = Int -> Int` `    `` ` `    ``inc1 :: Inc` `    ``inc1 x = x + 1` `    `` ` `    ``inc2 :: Inc` `    ``inc2 x = x + 2` `    `` ` `    ``twice :: Inc -> Int -> Int` `    ``twice i x = (i (i x))` `    `` ` `    ``nof :: Inc -> Int -> Int -> Int` `    ``nof i 0 x = x` `    ``nof i n x = (i (nof i (n-1) x))` `    `` ` `    ``-- :t nof (\x -> x + 3)` `    `` ` `    ``data Wrapper = Wrap Inc` `    ``unwrap :: Wrapper -> Inc` `    ``unwrap (Wrap x) = x` `    `` ` `    ``apply :: Wrapper -> Int -> Int` `    ``apply (Wrap f) x = f x` `    `` `