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.

code/Haskell/ExpTrees/exptree.hs

    -- 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)
     
Notice how the tree evaluator (evalExp) is defined by a simple induction on the data structure.

12.2 Type Classes



code/Haskell/ExpTrees/type-class-eg.txt

    --
    -- 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
     
12. Types
Notes on Functional Programming / Version 2.10 2014-02-24