CSCE 314 Lecture 9

« previous | Friday, September 16, 2011 | next »

User-defined Types

3 ways to define a type:

• data
• type

data Bool = False | True

• Bool is the data type
• True and False are constructors (must begin with capital letter and must be unique within entire module)
• "|" means "or": values of type Bool are True or False.

Constructors serve as patterns on which functions can be built:

data Weekday = Mon | Tue | Wed | Thu | Fri | Sat | Sun
next :: Weekday -> Weekday
next Mon = Tue
next Tue = Wed
next Wed = Thu
next Thu = Fri
next Fri = Sat
next Sat = Sun
next Sun = Mon

workDay :: Weekday -> Bool
workDay Sat = False
workDay Sun = False
workDay _ = True

Constructors with arguments

Constructors allow user to construct data representations and destruct them in pattern matching (like any of the built-in data types)

Person :: Name -> Gender -> Age -> Person
data Person = Person Name Gender Age
type Name = String
data Gender = Male | Female
type Age = Int

-- sample usage
let x = Person "Hermione" Female 13
    y = Person "Harry" Male 15
in ...

-- pattern matching
name :: Person -> String
name (Person n _ _) = n

oldMan :: Person -> Bool
oldMan (Person _ Male 40) | a > 40 = True
oldman (Person _ _ _) = False

> let jaakko = Person "Jaakko" Male 100
  in oldMan jaakko
True

findPerson :: String -> [Person] -> Person
findPerson n (p@(Person m _ _):ps)
    | n == m = p
    | otherwise = findPerson n ps

-- construction and destruction:
data Pair a b = Pair a b

apply :: (a -> a') -> (b -> b') -> Pair a b -> Pair a' b'
apply f g (Pair x y) = Pair (f x) (g y)

Built-in Maybe data type holds a value of any type or holds nothing:

data Maybe a = Nothing | Just a

lookup :: (Eq a) => a -> [(a,b)] -> Maybe b
lookup key [] = Nothing
lookup key ((x,y):xys)
    | key == x  = Just y
    | otherwise = lookup key xys

Recursive Data Types

data Nat = Zero | Succ Nat

Implementing a Binary Tree

data Tree a = Tnil | Node a (Tree a) (Tree a)

-- find an element in the tree (search, but not binary search)
treeElem :: (a -> Bool) -> Tree a -> Maybe a
treeElem p Tnil = Nothing
treeElem p t@(Node v left right)
    | p v = Just v
    | otherwise treeElem p left 'combine' treeElem p right
    where
        combine (Just v) r = Just v
        combine Nothing r = r

-- think "replace all Tnil constructors with f, all Node constructors with g"
treeFold :: t -> (a -> t -> t -> t) -> Tree a -> t
treeFold f g Tnil = f
treeFold f g (Node x l r) = g x (treeFold f g l) (treeFold f g r)

Deriving: Haskell Inheritance

Places the type as a subtype of other typeclasses:

data Bool = False | True
    deriving (Eq, Ord, Enum, Read, Show, Bounded)

All functions in the derived typeclasses must be defined for the given type.

Type Classes

class Eq a where
    (==), (/=) :: a -> a -> Bool
    x /= y = not (x == y)
    x == y = not (x /= y)

instance Eq Bool where
(==) False False = True
(==) True True = True
(==) _ _ = False