Transcript CS321 Functional Programming 2

CS321 Functional Programming 2
CS321 Functional Programming 2
Dr John A Sharp
10 credits
Tuesday 10am
Thursday 11am
Robert Recorde Room
Robert Recorde Room
© JAS 2005
1-1
CS321 Functional Programming 2
Assessment
80% written examination in May/June
20% coursework
probably two assignments – roughly weeks 4 and 7
© JAS 2005
1-2
CS321 Functional Programming 2
Syllabus
(Provisional)
• Type Classes
• Programming with Streams
• Lazy Data Structures
• Memoization
• Lambda Calculus
• Type Checking and Inference
• Implementation Approaches
© JAS 2005
1-3
CS321 Functional Programming 2
Recommended Reading
Course will not follow any specific text
S Thompson, Haskell: The Craft of Functional Programming, Second
Edition, Addison-Wesley, 1999
P Hudak, The Haskell School of Expression – Learning Functional
Programming through Multimedia, Cambridge University press, 2000
R Bird, Introduction to Functional Programming using Haskell, Second
Edition, Prentice-Hall, 1998
A J T Davie, An Introduction to Functional Programming using Haskell,
Cambridge University Press, 1992
www.haskell.org
© JAS 2005
1-4
CS321 Functional Programming 2
Notes will be handed out in sections
mainly copies of PowerPoint slides
some Haskell programs
They will also be available on a course web page
www.cs.swan.ac.uk/~csjohn/cs321/main.html
© JAS 2005
1-5
CS321 Functional Programming 2
Assumptions from CS221 Functional Programming 1
•
•
•
•
•
Familiar with principles of Functional Programming
Able to write and run simple Haskell programs/scripts
Familiar with concepts of types and higher-order functions
Able to define own structured types
Familiar with basic λ calculus
© JAS 2005
1-6
CS321 Functional Programming 2
Type Classes
Monomorphic functions
add1 :: Int -> Int
add1 x = x + 1
Parametric polymorphic functions
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)
© JAS 2005
1-7
CS321 Functional Programming 2
Ad-hoc polymorphic functions
add :: Int -> Int -> Int
add x y = x + y
add :: Float -> Float -> Float
add :: Double -> Double -> Double
add :: Num a => a -> a -> a
add x y = x + y
© JAS 2005
1-8
CS321 Functional Programming 2
This sort of type expression is sometimes referred to as a
“Qualified Type”.
Num a is termed a predicate which limits the types for
which a type expression is valid. It is also termed the
context for the type.
Multiple predicates can be defined
contrived :: (Num a, Eq b)=>a->b->b->a
contrived x y z = if y == z
then x + x
else x + x + x
© JAS 2005
1-9
CS321 Functional Programming 2
For completeness we could specify an empty context for any
polymorphic function
map :: () => (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)
© JAS 2005
1-10
CS321 Functional Programming 2
The predicate restricts the set of types for which the expression
is valid.
Num a should be read as “for all types a that are members of
the class Num.
Members of a class (which are types) are also called instances
of a class.
© JAS 2005
1-11
CS321 Functional Programming 2
Type classes allow us to group together types which have common
properties (or more accurately common operations that can be
applied to them).
An obvious example is the types for which equality can be defined.
An appropriate Class is defined in the standard prelude:-
class Eq a where
(==), (/=) :: a -> a -> Bool
x /= y = not ( x == y )
© JAS 2005
1-12
CS321 Functional Programming 2
class Eq a where
header introducing name of class and parameters (a)
(==), (/=) :: a -> a -> Bool
signature listing functions applicable to instances of
class and their type
(==) and (/=) are termed member functions
x /= y = not ( x == y )
default definitions of member functions that can be
overridden
© JAS 2005
1-13
CS321 Functional Programming 2
Having defined the concept of an equality class the next step
is to define various instances of the class.
The following examples are again taken from the standard
prelude.
instance Eq Int where (==) = primEqInt
-- primEqint is a primitive Haskell function
instance Eq Bool where
True == True
= True
False == False
= True
_
== _
= False
-- defined by pattern matching
© JAS 2005
1-14
CS321 Functional Programming 2
instance Eq Char where
c == d = ord c == ord d
-- note the second == is defined on integers
instance (Eq a,Eq b) => Eq(a,b) where
(x,y) == (u,v) = x==u && y==v
-- pairwise equality
instance Eq a => Eq [a] where
[]
== []
= True
[]
== (y:ys) = False
(x:xs)== []
= False
(x:xs)== (y:ys) = x==y && xs==ys
-- extend to equality on lists
© JAS 2005
1-15
CS321 Functional Programming 2
These declarations allow us to obtain definitions for equality
on an infinite family of types involving pairs, and lists of
(pairs and lists of) Int, Bool, Char.
The general format of an instance declaration is
instance context => predicate where
definitions of member functions
We can define instances of Eq for user defined types.
© JAS 2005
1-16
CS321 Functional Programming 2
Consider a definition of Sets
data Set a = Set [a]
To make the type Set a a member of the class Eq we define an
instance of Eq.
Note that we do not use the standard (==) on the type a as we do
not require the elements of the Sets to be in the same order.
instance Eq a => Eq (Set a) where
Set xs == Set ys =
xs 'subset' ys && ys 'subset xs
where xs 'subset' ys =
all ('elem' ys) xs
© JAS 2005
1-17
CS321 Functional Programming 2
Some types (such as functions) can not be defined to be members of
the class Eq (for obvious reasons, I hope). The error message that
results from a mistaken attempt to test for equality can be obscure.
It is possible to make a test for equality on functions type check ok
and produce a run-time error message using the standard error
function defined in the standard prelude.
instance Eq (a->b) where
(==) = error "== not defined on fns"
© JAS 2005
1-18
CS321 Functional Programming 2
Anoperate
a
If the functions are defined to
on a finite set of elements
then a form of equality can be defined.
instance Eq a => Eq (Bool->a) where
f == g = f False == g False &&
f True == g True
It is possible to have instances for both Eq (a->b) and
Eq (Bool->a) as long as both are not required at the same time
in type checking some expression.
© JAS 2005
1-19
CS321 Functional Programming 2
Inheritance, Derived Classes, Superclasses, and Subclasses
In general a class declaration has the form
class context => Class a1 .. an where
type declarations for member functions
default declarations of member functions
where Class is the name of a new type class which takes n
arguments (a1 .. an ).
As with instances the context must be satisfied in order to
construct any instance of the Class.
The predicates in the context part of the declaration are called the
superclasses of Class. Class is a subclass of the classes in the
1-20
context.
© JAS 2005
CS321 Functional Programming 2
Consider a definition of a Class Ord whose instances have
both strict (<), (>) and non-strict (<=), (>=) versions of an
ordering defined on their elements.
class Eq a => Ord a
(<),(<=),(>),(>=)
max,min
x < y
x >= y
x > y
max x y | x >= y
| y >= x
min x y | x <= y
| y <= x
where
:: a->a->Bool
:: a->a->a
= x <= y && x /= y
= y <= x
= y < x
= x
= y
= x
= y
© JAS 2005
1-21
CS321 Functional Programming 2
Why define Eq as a superclass of Ord?
• the default definition of (<) relies on the use of (/=) taken
from the class Eq. Therefore every instance of Ord must
be an instance of Eq.
• given the definition of non-strict ordering (<=) it is always
possible to define (==) and hence (/=) using
x==y = x<=y && y<= x
so there will be no loss of generality in requiring Eq to be
a superclass of Ord.
© JAS 2005
1-22
CS321 Functional Programming 2
It is possible for some types to require a type to be an instance
of class Ord in order to define it to be an instance of the
class Eq.
For example consider an alternative way of defining equality
on Sets.
instance Ord (Set a) => Eq (Set a) where
x == y = x <= y && y <= x
instance Eq a => Ord (Set a) where
Set xs <= Set ys = all ('elem' ys) xs
© JAS 2005
1-23
CS321 Functional Programming 2
Numeric Class Hierarchy
Eq
All but IO, (->)
Show
All Prelude Types
Read
Ord
All but IO, (->),
IOError
Num
Int, Integer,
Float, Double
IO, [], Maybe
(), Bool, Char,
Int, Integer, Float,
Double, Ordering
Real
Int, Integer,
Float, Double
Bounded
All but IO, (->) Int, Char, Bool, (),
Ordering, tuples
Monad
Enum
Fractional
Float, Double
Int, Integer
RealFrac
Float, Double
Floating
Float, Double
RealFloat
Float, Double
Functor
MonadPlus
IO, [], Maybe
Integral
IO, [], Maybe
© JAS 2005
1-24
CS321 Functional Programming 2
Operations defined in these classes (red means must be provided)
Eq
Ord
Num
Real
Enum
== /=
< <= > >= max min compare
+ - * negate abs signum fromInteger
toRational
succ pred toEnum fromEnum enumFrom
enumFromThen enumFromTo
enumFromThenTo
Integral quot rem div mod quotRem divMod
toInteger
Fractional / recip fromRational
RealFrac properFraction truncate round
ceiling floor
© JAS 2005
1-25
CS321 Functional Programming 2
Floating
pi exp log sqrt ** logBase sin cos
tan asin acos atan sinh cosh tanh
asinh acosh atanh
RealFloat floatRadix floatDigits floatRange
decodeFloat encodeFloat exponent
significand scaleFloat isNaN
isInfinite isDenormalized isIEEE
isNegativeZero atan2
Show
showsPrec showList show
Read
readsPrec readList
Bounded
minBound maxBound
Monad
>>= >> return fail
Functor
fmap
© JAS 2005
1-26
CS321 Functional Programming 2
By introducing type classes Haskell has enabled programmers
to use numerical types in a manner similar to the way they
are used to in traditional imperative languages.
But what else are type classes useful for?
They can provide a mechanism for adding your own
numerical types eg complex numbers
They can provide a mechanism for a sort of object-oriented
programming
© JAS 2005
1-27
CS321 Functional Programming 2
Imperative O-O Classes = Data + Methods
Objects contain values which can be changed by methods
Classes inherit data fields and methods
FP Classes = Methods
Methods/Functions can be applied to variables whose type is an
Instance of a Class
Classes inherit methods/functions
© JAS 2005
1-28
CS321 Functional Programming 2
Implementing Type Classes – An Approach using Dictionaries
A function with a qualified type context=>type is implemented by
a function which takes an extra argument for every predicate in the
context.
When the function is used each of these parameters is filled by a
'dictionary' which gives the values of each of the member functions
in the appropriate class.
For example, for the class Eq each dictionary has at least two elements
containing the definitions of the functions for (==) and (/=).
© JAS 2005
1-29
CS321 Functional Programming 2
We will write
(#n d)
to select nth element of dictionary
{dict}
to denote a specific dictionary
( contents not displayed)
dnnn
for a dictionary variable representing an unknown
dictionary
d:: Class Inst
to denote that d is dictionary for the instance
Inst of a class Class
© JAS 2005
1-30
CS321 Functional Programming 2
The member functions of the class Eq thus behave as if defined
(==) d1 = (#1 d1)
(/=) d1 = (#2 d1)
The dictionary for Eq Int contains two entries:
d1 :: Eq Int
primEqInt
defNeq d1
© JAS 2005
1-31
CS321 Functional Programming 2
Evaluating 2 == 3
=>
(==) d1 2 3
Evaluating 2 /= 3
=>
(/=) d1 2 3
=>
=>
=>
(#1 d1) 2 3
primEqInt 2 3
False
=>
=>
=>
=>
=>
=>
=>
(#2 d1) 2 3
defNeq d1 23
not ((==) d1 2 3)
not ((#1 d1) 2 3)
not (primEqInt 2 3)
not False
True
© JAS 2005
1-32
CS321 Functional Programming 2
Now consider a more complex example
We have seen definitions of (==) in the instances of the class
Eq defined for pairs and lists.
eqPair d (x,y) (u,v) =
(==) (#3 d) x u && (==) (#4 d) y v
eqList d [] [] = True
eqList d [] (y:ys) = False
eqList d (x:xs) [] = False
eqList d (x:xs) (y:ys) =
(==) (#3 d) x y && (==) d xs ys
© JAS 2005
1-33
CS321 Functional Programming 2
The dictionary structure for Eq (Int, [Int]) is
d3 :: Eq (Int, [Int])
eqPair d3 defNeq d3
d2 :: Eq [Int]
eqList d3 defNeq d3
d1 :: Eq Int
primEqInt
defNeq d3
© JAS 2005
1-34
CS321 Functional Programming 2
(2,[1]) == (2,[1.3])
=>
eqPair
(==)
(#1 d3
d3)
d3 (2,[1]) (2,[1,3])
=> (==)
primEqInt
(#1
True
(#3
d1)
d1d3) 2 2 && (==)
eqList
(#1(#4
d2)
d2d2
d3) [1] [1,3]
=>
(==)
primEqInt
(#1
True
(#3
d1)d1
d2) 1 1
© JAS 2005
&& eqList
(==)
(#1 d2)
False
d2d2 []
[3]
1-35
CS321 Functional Programming 2
Dictionaries for superclasses can be defined in a similar way
as instance dictionaries.
For example for the Ord class which has Eq as a context
class Eq => Ord a where
(<),(<=),(>),(>=) :: a->a->Bool
max,min
:: a->a->Bool
the dictionary would contain the following
(<)
(<=)
(>)
(>=)
max min
Eq a
defLessThan d x y = (<=) d x y && (/=) (#7 d) x y
© JAS 2005
1-36
CS321 Functional Programming 2
Combining Classes
A dictionary consists of three (possibly empty) components:
• Superclass dictionaries
• Instance specific dictionaries
• Implementation of class members
instances of Eq have no superclass dictionaries
Eq Int has no instance specific dictionary
Classes with no member functions can be used as abbreviations for
lists of predicates
class C a where cee :: a -> a
class D a where dee :: a -> a
class (C a, D a) => CandD a
© JAS 2005
1-37
CS321 Functional Programming 2
Contexts and Derived Types
eg1 x = [x] == [x] || x == x
Since the (==) operation is applied to both lists and an argument x if
x::a then we would seem to require instances Eq a and Eq [a]
giving a type signature
(Eq [a], Eq a) => a -> Bool
with translation
eg1 d1 d2 x = (==) d1 [x] [x] || (==) d2 x x
© JAS 2005
1-38
CS321 Functional Programming 2
However, given d1::Eq[a] we can always find Eq a by taking
the third element of d1 ((#3 d1)::Eq a).
Since it is more efficient to select an element from a dictionary than
to complicate both type and translation with extra parameters the
type of eg1 is (by default) derived as
Eq [a] => a -> Bool
with translation
eg1 d1 x = (==) d1 [x] [x] ||(==) (#3 d1) x x
© JAS 2005
1-39
CS321 Functional Programming 2
If you definitely required the tuple context then this can be
produced by explicitly defining the type and context of eg1
eg2 = (\x y-> x ==x || y==y)
The type derived for this is
(Eq b, Eq a) => a -> b -> Bool
with translation
\d1 d2 x y ->
(==) d2 x x || (==) d1 y y
© JAS 2005
1-40
CS321 Functional Programming 2
If you wished to ensure that only one dictionary parameter is used you
could explicitly type is using
Eq (a,b) => a -> b -> Bool
with translation
\d1 x y ->(==) (#3 d1) x x || (==) (#4 d1) y y
© JAS 2005
1-41