CMPUT 325 Schedule and Outcomes
9. Week 7 - Feb 24

9.1 Topics

9.2 Flipped Work

9.3 Creating New Types

Type Synonyms

In order to improve the readability of your code, you can introduce type synonyms or aliases using type. This does not introduce a new type, but just gives an alternative name.


    -- type synonym that indicates a function from Int to Int that increments
    type Inc = Int -> Int
    inc1 :: Inc
    inc1 x = x + 1
    inc2 :: Inc
    inc2 x = x + 2
    twice :: Inc -> Inc
    -- could do this: twice i x = (i (i x))
    -- but this is beter
    twice i = i . i
    nof :: Inc -> Int -> Inc
    nof i 0 x = x
    nof i n x = (i (nof i (n-1) x))
    -- rewrite nof using composition like twice, without x
    -- :t nof (\x -> x + 3)
    -- any Int -> Int function will do
    inc3 :: Int -> Int
    inc3 x = x + 3

Simple New Types

With newtype you can introduce a new type, that uses existing types for its values, but tags the type so that the type checker can distiguish between the different uses of the value. These new types have no additional computational overhead since they have only one type constructor. code/Week07/newtype-1.hs

    -- this new type indicates an a Int wrapped as a parameter, so that not just
    -- any Int can be used.
    newtype Param = P Int deriving Show
    type Inc = Param -> Param
    x :: Param
    x = P 1
    inc1 :: Inc
    inc1 (P y) = P (y + 1)
    twice :: Inc -> Inc
    twice i =  i . i
    -- now any Int -> Int function will not do
    inc3 :: Int -> Int
    inc3 x = x + 3
    -- twice inc3 0

Algebraic Data Types

data is used to create new kinds of values in the form of new data structures with operations on them. Constructors tell you how to combine things to make a new value, pattern matchnig tells you how to take the values apart, these two let you build new operations.

For example, a pair of Int. Note how the Show and Eq subclass properties (see below) are derived from the corresponding classes of the types used to build the new type.


    data Pair = P Int Int deriving (Show, Eq)
    pairFst (P x y ) = x
    pairSnd (P x y ) = y

Generalize to a pair of anything of the same type, and introduce an ordering on pairs to make it also a subclass of Ord.


    -- 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 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

Generalize to a pair of two potentially differnt types of things, and derive the "natural" lexigographic ordering on pairs.


    -- 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"

Parameterized New Types

newtype can also be paramterized like data


    newtype Param a = P a deriving Show
    type Inc a = Param a -> Param a
    twice :: Inc a -> Inc a
    twice i =  i . i
    x :: Param Int
    x = P 1
    y :: Param String
    y = P "fred"
    inc1 :: Num a => Inc a
    inc1 (P y) = P (y + 1)
    -- we could declare inc2 :: Inc [Int]
    -- but actually it's more general derived type is Param [a] -> Param [a]
    inc2 (P y) = P (y ++ y)
    -- try: twice inc1 $ P 3
    -- now any Int -> Int function will not do
    inc3 :: Int -> Int
    inc3 x = x + 3
    -- try: twice inc2 $ P [ 1 , 2]
    -- twice inc3 0


    newtype Param a = P a deriving Show
    newtype Inc a = I (Param a -> Param a)
    twice :: Inc a -> Inc a
    twice (I i) =  I ( i . i )
    ap (I f) x = f x
    x :: Param Int
    x = P 1
    y :: Param String
    y = P "fred"
    -- IMPORTANT TRICK: when confused by the type signature, just define your
    -- function, then use :t to extract its type.
    inc1 :: Inc Integer
    inc1 = I f where
        f (P y) = P (y+1)
    -- we could declare inc2 :: Inc [Int]
    -- but actually it's more general derived type is
    inc2 :: Inc [ a ]
    inc2 = I f where
        f (P y) = P (y ++ y)
    -- try: twice inc1 $ P 3
    -- try:
    -- let g = twice inc1
    -- ap g (P 3)
    -- try: ap (twice inc2) $ P [ 1 , 2]
    -- now any Int -> Int function will not do, try this declaration
    -- inc3 = I f where
    --     f x = x + 3

Expression Trees


    -- 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)

Qualified Types and Type Classes

The data keyword lets you introduce new values. Haskell type classes let you package the new values with associated operations. This is done with the class keyword.

But first some notation we have been using. The => arrow is a type qualifier. When we have a type, say like this g :: a -> a we read this as function over any type a. Or more precisely, for all types a, g is a function of type a->a.

But many times this is too general. This function
g x = x + 1
only makes sense on values that have a + operation. So we might want to restrict it to numbers. What are numbers? In Haskell, there is a class called Num, and so we can restrict our function definition to only be on number-like instances:
g :: Num a => a -> a
g x = x + 1
which can be read as for any type a that is a member of the class Num, the function g has type a -> a.

There are some very important type classes: When you generate a new data type, you often want to establish that the new datatype is an instance of the these type classes. See the pair example above. In many cases, Haskell can derive the required instance information by induction on the constructors used to create the new values.



    module Tree ( Tree(Leaf,Branch), fringe ) where
    data Tree a = Leaf a | Branch ( Tree a ) ( Tree a )  deriving (Eq, Show)
    fringe :: Tree a -> [a]
    fringe ( Leaf x )            = [x]
    fringe ( Branch left right ) = fringe left ++ fringe right

9. Week 7 - Feb 24
CMPUT 325 Schedule / Version 2.31 2014-04-04