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)