June FP2 Exam – Sample answers.

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

i) [`a’,`b’] ++ “cde” = “abcde” ::String

ii) head [[42,15],[19,10,13]] = [42,15]:: [Int]

iii) tail [42,15]:[22] = error

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

v) fold ++ 0 [“hello”,”world”] = type error

vi) [x*2| x<- [1..10]] = [2,4,6,8,10,12,14,16,18,20] ::[Int]

vii) [(x,y)| x<-[1..3],y <- “ab”] =

[(1,`a`),(1,`b`),(2,`a`),(2,`b`),(3,`a`),(3,`b`)]::[(Int,Char)]

viii) foldr * 0 [4,5,6] = 4*5*6*0=0 ::[Int]

ix) fold ++ [“hello”,”world”] = “helloworld” :: String

x) f 10 where f x y = x * y = f 10 :: Int -> Int

xi) g “3” where g x = x:”45” = error

xii) [3|x <- [1..3]] = [3,3,3]

2.

Data BST a = Node a (BST a) (BST a) | Nil

a) insert :: Ord a => a -> (BST a) -> BST a

insert x Nil = Node x Nil Nil

insert x (Node y t1 t2)

|(x<y) = Node y (insert x t1) t2

| (x==y) = Node y t1 t2

| otherwise = Node y t1 (insert x t2)

b) total :: BST -> Int

total Nil = 0

total (Node x t1 t2) = (total t1) + 1 + (total t2)

c) desc :: (BST a) -> [a]

desc Nil = []

desc (Node x t1 t2) = desc t2 ++ [x] ++ desc t1

3.

sumtree : Tree -> Int

sumtree Nil = 0

sumtree Node x t1 t2 = x + sumtree t1 + sumtree t2

double :: Tree -> Tree

double Nil = Nil

double Node x t1 t2 = Node (2*x) (double t1) (double t2)

Theorem: for all finite binary trees t. ( sumtree t) * 2 = sumtree (double t).

Proof by induction on trees.

Base case: trivial

Inductive case: Assume ( sumtree t1) * 2 = sumtree (double t1), ( sumtree t2) * 2 = sumtree (double t2).

Show (sumtree (Node x t1 t2))*2 = sumtree(double (Node x t1 t2)).

(sumtree (Node x t1 t2))*2 = ( x + sumtree t1 + sumtree t2)*2 sumtree.1

= x*2 + sumtree t1 * 2 + sumtree t2 *2 arithemetic

= x*2 + sumtree (double t1) + sumtree (double t2) assumption

= sumtree (Node (x*2) (double t1) (double t2) ) sumtree.2

= sumtree (double (Node x t1 t2) ) double

(I have been lax with my brackets!)

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)

a) x ::Int, z::Int therefore zs :: [Int]

y:: Int -> a

f:: Int -> (Int -> a) -> [Int] -> [a]

b) z::a, w::[a], (z:w)::[a],

x: a -> a -> b, y :: b, x:: (a->b->b)

f: (a->b->b) -> b -> [a] -> a -> b

5.

foldr :: (a -> b -> b) -> b -> [a] -> b

foldr f s [] = s

foldr f s (x:xs) = f x (foldr f s xs)

6.

data Module = Mod String Int [Int]

a)passboth :: Module -> Module -> Int

passboth (Mod s1 n1 l1) (Mod s2 n2 l2) = intersect l1 l2

where

intersect :: [Int] ->[Int] -> [Int]

intersect [] l = []

intersect l [] = []

intersect (x:xs)

|(in x ys) = x:( intersect xs ys )

| otherwise = intersect xs ys

in x [] = False

in x (y:ys) = if (x==y) then True else in x ys

b)passeither :: Module -> Module -> Int

passeither (Mod s1 n1 l1) (Mod s2 n2 l2) = union l1 l2

where

union xs ys = xs ++ f xs ys

f xs [] = []

f xs (y:ys) = if (y in xs) then f xs ys else (y: f xs ys)

c)passrate :: Module -> Module -> Float

passrate (Mod s1 n1 l1) (Mod s2 n2 l2) = (union l1 l2) / (n1 + n2)