examstyle

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]:[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]