Transcript Week 5

COSC 4P41 – Functional Programming
Modules in Haskell
Using modules to structure a large program has a number of advantages:
• Parts of the system can be built separately from each other.
• Parts of the system can be compiled separately.
• Libraries of components can be reused, by importing the appropriate
module containing them.
module Ant where
type Ants = …
antEater x = …
The convention for file names is that a module Ant resides in the Haskell
file Ant.hs or Ant.lhs.
© M. Winter
5.1
COSC 4P41 – Functional Programming
Importing a module
module Bee where
import Ant
beeKeeper = …
Importing the module Ant means that the visible definitions from the
module can be used in Bee. By default the visible definitions in a module
are those which appear in the module itself.
module Cow where
import Bee
The definitions of Ant are not visible in Cow.
© M. Winter
5.2
COSC 4P41 – Functional Programming
Export control
We can control what is exported by following the name of the module
with a list of what is to be exported.
• module Bee (beeKeeper, Ants, antEater) where …
• module Bee (beeKeeper, module Ant) where …
• module Fish where
type Fish = (String,Size)
• module Fish (Fish(..),…) where
newtype Fish = F (String,Size)
• module Fish (Fish,…) where
newtype Fish = F (String,Size)
© M. Winter
5.3
COSC 4P41 – Functional Programming
Import control
Examples:
• import Ant (Ants)
• import Ant hiding (antEater)
• module Bear where
import qualified Ant
antEater x = … Ant.antEater x …
• import Insect as Ant
• import Prelude hiding (words)
• import qualified Prelude
© M. Winter
5.4
COSC 4P41 – Functional Programming
Overloading and type classes
A polymorphic function such as length has a single definition which
works over all its types.
length :: [a] -> Int
length = foldl' (\n _ -> n + 1) 0
An overloaded function like equality (==), + and show can be used at a
variety of types, but with different definitions being used at different
types.
© M. Winter
5.5
COSC 4P41 – Functional Programming
Why overloading?
elemBool :: Bool -> [Bool] -> Bool
elemBool x []
= False
elemBool x (y:ys)
= (x ==Bool y) || elemBool x ys
elemInt :: Int -> [Int] -> Bool
elemInt x []
= False
elemInt x (y:ys)
= (x ==Int y) || elemInt x ys
Generalization may lead to the definition:
elemGen :: (a -> a -> Bool) -> a -> [a] -> Bool
elemGen p x []
= False
elemGen p x (y:ys) = p x y || elemGen x ys
but this is too general in a sense, because it can be used with any
parameter of type a -> a -> Bool rather than just an equality check.
© M. Winter
5.6
COSC 4P41 – Functional Programming
Why overloading? (cont’d)
Generalization in the following way will not work. The definition
elem :: a -> [a] -> Bool
elem x []
= False
elem x (y:ys) = (x == y) || elem x ys
will cause an error
No instance for (Eq a)
arising from a use of `=='
In the first argument of `(||)', namely `x == y'
In the expression: x == y || elem x ys
In an equation for `elem`: elem x (y : ys) = x == y || elem x ys
because this definition requires that (==) :: a -> a -> Bool is
already defined.
© M. Winter
5.7
COSC 4P41 – Functional Programming
Classes
A type class or simply a class defines a collection of types over which
specific functions are defined.
class Eq a where
(==) :: a -> a -> Bool
Members of a class are called instances. Built-in instances of Eq include
the base types Int, Float, Bool, Char, tuples and lists built from types
which are themselves instances of Eq, e.g., (Int,Bool) and [[Char]].
elem :: Eq a => a -> [a] -> Bool
elem x []
= False
elem x (y:ys) = (x == y) || elem x ys
© M. Winter
5.8
COSC 4P41 – Functional Programming
Classes (cont’d)
(+1) :: Int -> Int
elem (+1) [] causes an error
No instance for (Eq (a0 -> a0))
arising from a use of `elem'
Possible fix: add an instance declaration for (Eq (a0 -> a0))
In the expression: elem (+ 1) []
In an equation for `it': it = elem (+ 1) []
which conveys the fact that Int -> Int is not an instance of the Eq class.
© M. Winter
5.9
COSC 4P41 – Functional Programming
Instances of classes
Examples:
instance
True
False
_
Eq
==
==
==
Bool where
True = True
False = True
_
= False
instance Eq a
[]
==
(x:xs) ==
_
==
=> Eq [a]
[]
=
(y:ys) =
_
=
where
True
x==y && xs==ys
False
instance (Eq a, Eq b) => Eq (a,b) where
(x,y) == (z,w) = x==z && y==w
© M. Winter
5.10
COSC 4P41 – Functional Programming
Default definitions
The Haskell Eq class is in fact defined by
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y
= not (x==y)
x == y
= not (x/=y)
Both functions have default definitions in terms of the other function. At
any instance a definition of at least one of == and /= needs to be provided.
© M. Winter
5.11
COSC 4P41 – Functional Programming
Derived classes
To be ordered, a type must carry operations >, >= and so on, as well as the
equality operations.
class (Eq a) => Ord a where
compare
:: a -> a -> Ordering
(<), (<=), (>=), (>)
:: a -> a -> Bool
max, min
:: a -> a -> a
© M. Winter
5.12
COSC 4P41 – Functional Programming
Example
class Visible a where
toString
:: a -> String
size
:: a -> Int
instance Visible Bool
toString True
=
toString False
=
size _
=
where
”True”
”False”
1
instance Visible a => Visible [a] where
toString
= concat . map toString
size
= foldr (+) 1 . map size
© M. Winter
5.13
COSC 4P41 – Functional Programming
Example (cont’d)
sort :: Ord a => [a] -> [a]
vSort :: (Ord a, Visible a) => [a] -> String
vSort = toString . sort
class (Ord a, Visible a) => OrdVis a
vSort' :: OrdVis a => [a] -> String
vSort' = toString . sort
© M. Winter
5.14
COSC 4P41 – Functional Programming
A tour of the built-in Haskell classes
Many of the Haskell built-in classes are numeric, and are built to deal with
overloading of the numerical operations. We will not study those classes.
Class Eq:
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y
= not (x==y)
x == y
= not (x/=y)
Instances: All except of IO, ->
© M. Winter
5.15
COSC 4P41 – Functional Programming
Class Ord
class (Eq a) => Ord a where
compare
:: a -> a -> Ordering
(<), (<=), (>=), (>)
:: a -> a -> Bool
max, min
:: a -> a -> a
-- Minimal complete definition: (<=) or compare
-- using compare can be more efficient for complex types
compare x y | x==y
= EQ
| x<=y
= LT
| otherwise = GT
x <= y
= compare x y /= GT
x < y
= compare x y == LT
x >= y
= compare x y /= LT
x > y
= compare x y == GT
max x y
| x <= y
= y
| otherwise
= x
min x y
| x <= y
= x
| otherwise
= y
Instances: All except IO, IOError, ->
© M. Winter
5.16
COSC 4P41 – Functional Programming
Class Enum
class Enum a where
succ, pred
toEnum
fromEnum
enumFrom
enumFromThen
enumFromTo
enumFromThenTo
::
::
::
::
::
::
::
a -> a
Int -> a
a -> Int
a -> [a]
a -> a -> [a]
a -> a -> [a]
a -> a -> a -> [a]
-----
[n..]
[n,m..]
[n..m]
[n,n'..m]
-- Minimal complete definition: toEnum, fromEnum
succ
= toEnum . (1+)
. fromEnum
pred
= toEnum . subtract 1 . fromEnum
enumFrom x
= map toEnum [ fromEnum x ..]
enumFromTo x y
= map toEnum [ fromEnum x .. fromEnum y ]
enumFromThen x y
= map toEnum [ fromEnum x, fromEnum y ..]
enumFromThenTo x y z = map toEnum
[ fromEnum x, fromEnum y .. fromEnum z ]
Instances: (), Bool, Char, Int, Integer, Float Double
© M. Winter
5.17
COSC 4P41 – Functional Programming
Class Bounded
class Bounded a where
minBound, maxBound :: a
-- Minimal complete definition: All
Instances: Int, Char, Bool (but not Integer)
© M. Winter
5.18
COSC 4P41 – Functional Programming
Class Show
type ShowS = String -> String
class Show a where
show
:: a -> String
showsPrec :: Int -> a -> ShowS
showList :: [a] -> ShowS
-- Minimal complete definition: show or showsPrec
show x
= showsPrec 0 x ""
showsPrec _ x s = show x ++ s
showList []
= showString "[]"
showList (x:xs) = showChar '[' . shows x . showl xs
where
showl []
= showChar ']'
showl (x:xs) = showChar ',' . shows x .
showl xs
Instances: All except ->
© M. Winter
5.19
COSC 4P41 – Functional Programming
Class Read
type ReadS a = String -> [(a,String)]
class Read a where
readsPrec :: Int -> ReadS a
readList :: ReadS [a]
-- Minimal complete definition: readsPrec
readList
= readParen False (\r -> [pr | ("[",s) <- lex r,
pr
<- readl s ])
where readl s = [([],t)
| ("]",t) <- lex s] ++
[(x:xs,u) | (x,t)
<- reads s,
(xs,u) <- readl' t]
readl' s = [([],t)
| ("]",t) <- lex s] ++
[(x:xs,v) | (",",t) <- lex s,
(x,u)
<- reads t,
(xs,v) <- readl' u]
Instances: All except IO, ->
© M. Winter
5.20