Tuesday, June 3, 2003
11.15 a.m. – 12.30 p.m.
University of Glasgow
DEGREES OF M.Eng., B.Eng., B.Sc., M.A. and M.A. (Social Sciences)
COMPUTING SCIENCE 2S
FUNCTIONAL PROGRAMMING 2
(Answer all 6 questions.)
1.Evaluate the following Haskell expressions, giving a value and type. If the expression is an error, explain why.
(i) [‘a’,’b’] ++ “cde”
(ii) head [[42,15],[19,10,13]]
(iii) tail [42,15]:
(v) fold ++ 0 [“hello”,”world”]
(vi) [x*2| x<- [1..10]
(vii) [(x,y)| x<-[1..3],y <- “ab”]
(viii) foldr * 0 [4,5,6]
(ix) fold ++ [“hello”,”world”]
(x) f 10 where f x y = x * y
(xi) g “3” where g x = x:”45”
(xii) [3| x <- [1..3]]
2. Define a Haskell type for a binary search tree, and then define the following functions on binary search trees.
a) Insert an item into a binary search tree, avoiding duplication.
b) Return the total number of items in a binary search tree.
c) List the items in the binary search tree, in descending order.
3. Given the following Haskell type for Integer binary trees:
data Tree = Nil | Node Int Tree Tree
define the following functions (including the type of function)
a) sumtree, which returns the sum of the integers in a tree
b) double, which doubles all the integers in a tree.
Then prove the following theorem by induction:
c) for all finite binary trees t. ( sumtree t) * 2 = sumtree (double t).
Justify every step of your proof.
4. Deduce Haskell types for the following functions.
(a) f x y (z:zs) = (y (x+z)) : f x y zs
(b) f x y w z = foldr x y (z:w)
5. Give a definition of the Haskell function foldr which applies a binary operator all elements of a lists and a “stopping” value.
6. Define a Haskell algebraic type to represent course modules. Each module has the following attributes: the module name, the number of students taking the module, and a list of matric numbers of the students who have passed the module.
(a) Define a function passboth which, for given modules x and y, returns the number of students who have passed both modules x and y.
(b) Define a function passeither which, for given modules x and y, returns the number of students who have passed either module x or module y. The list should not contain duplicates.
(c) Define a function passrate which, for given modules x and y, returns the proportion of students who have passed either module x or module y.