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

1.Evaluate the following Haskell expressions, giving a value and type.  If the expression is an error, explain why.

(i)         [‘a’,’b’] ++ “cde”

(iii)       tail [42,15]:[22]

(iv)       (2,4):[(6,80)]

(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]]

[15]

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.

[15]

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.

[15]

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)

[15]

5.               Give a definition of the Haskell function foldr which applies a binary operator all elements of a lists and a “stopping” value.

[15]

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.

[15]