Transcript Functional Programming - University of Glasgow

Functional Programming
Lecture 12 more higher order
functions
Recursion over two arguments
The function zip “zips” together two lists, to produce a
new list of pairs.
zip :: [a] -> [b] -> [(a,b)]
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _ _ = []
or
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip [] (y:ys) = []
zip xs [] = []
(Why not zip (x:xs) [] = [] ?)
E.g. zip [1,2,3] [‘a’,’b’,’c’] => [(1,’a’), (2,’b’), (3,’c’)]
zip [1,2,3] [‘a’,’b’] => [(1,’a’), (2,’b’)]
The function unzip “unzips” a list of pairs to produce a
pair of lists.
unzip :: [(a,b)] -> ([a],[b])
tricky definition
unzip [] = ([],[])
unzip (x,y):zs = (x:xs,y:ys)
where (xs,ys) = unzip zs
What is unzip [(1,’a’), (2,’b’), (3,’c’)]?
=> ([1,2,3],[‘a’,’b’,’c’])
What is unzip (zip xs ys) ?
=> (xs,ys) if xs and ys have same length
What is zip (unzip zs)?
=> type error, unzip has produced a tuple!
What is zip (fst (unzip zs)) (snd (unzip zs)) ?
=> zs
Fold and Foldr
Consider computing the sum of the elements of a list
[e1, e2, … en] i.e. e1 + (e2 +( … + en )).
sumlist :: [Int] -> Int
sumlist [x] = x
sumlist (x:xs) = x + sumlist xs
Now consider computing the maximum of the elements
of a list [e1, e2, … en]
i.e. e1 max (e2 max ( … max en)).
maxlist :: [Int] -> Int
maxlist [x] = x
maxlist (x:xs) = max x (maxlist xs)
In both cases, we are “folding” the binary function +
and max through a non-empty list.
Fold
Define fold as the function
fold :: (a -> a -> a) -> [a] -> a
a binary function a list the result
fold f [x] = x
fold f (x:xs) = f x (fold f xs)
Note: although [x] matches the second equation, we
will always apply the first equation.
Examples
fold (||) [False, True, False]
=> True
fold (++) [“Hello “, “world”, “!”]
=> “Hello world!”
fold (*) [1..5]
=> 120 n.b infix op. Becomes prefix in ‘(‘ ‘)’
But fold has not been defined for an empty list.
What would we like to define
fold (||) [] and
fold (*) [] as ?
There is no general answer, we must provide one for
each function we give to fold.
The function which defines fold for an empty list is
foldr.
Foldr
Define foldr as the function
foldr :: (a -> b -> b) -> b -> [a] -> b
a binary function empty value
a list the result
Note: foldr has a more general type.
foldr f st [] = st
foldr f st (x:xs) = f x (foldr f st xs)
Note: foldr means fold right. Usually the extra
argument is the identity element, i.e. the stopping value
st is the identity for f.
foldr is defined in the standard prelude.
Examples
foldr (||) False [False, True, False]
=> True
foldr (&&) True [True, True]
=> True
foldr (&&) False [True, True]
=> False
foldr (*) 1 [1..5]
=> 120
1 is an identity for *
foldr (*) 0 [1..5]
=> 0
because 0 is a zero for *
fac n = foldr (*) 1 [1..n]