Question 1
(a) Select ONE answer for each section.
(i) Which of the following is an invalid list in Haskell:
1) [ 4,5,6]
2) [ “abc”, ‘c’ ] Answer
3) [[4], [4,5], [1..4], [] ]
4) [[True, True] , [True]]
(2 Marks)
(ii) The function swap defined by
swap(x,y) = (y,x)
has type:
1) a-> b-> b-> a
2) (a,b) -> b-> a
3) (a,b) -> (b,a) Answer
4) (a -> b) -> (b ->a)
(3 Marks)
(iii) Evaluating
[(x,y) | y <- [1..3], x <- [y..3]] gives:
1) [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
2) [(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)]
3) [(1,1),(2,1),(3,1),(2,2),(3,2),(3,3)] Answer
4) [(1,1),(2,1),(3,1),(1,2),(2,2),(3,2)] (3 Marks)
(iv) Evaluating
map (\x-> (if x>10 then 100 else x -5) ) [1, 10, 15] gives:
• []
• [-4,5,100] Answer
• -4 5 100
• [-4, 100, 100] (3 Marks)
(v) The expression Node (Leaf 1) (Leaf 2) is a value of the datatype:
• data Tree = Node | Leaf | Int
• data Tree = Leaf Int | Node Int Int
• data Tree = Leaf Tree | Node Int Int
• data Tree = Leaf Int | Node Tree Tree Answer
• data Tree = Leaf Tree | Node Tree Tree
(3 Marks)
(sub-total for part (a) = 15 Marks)
b) Define the following Prelude functions using
• recursion (2 Marks each) and
• foldr (3 Marks each) :
product :: [Int] -> Int
length :: [a] -> Int
reverse :: [a] -> [a]
recursion (2 Marks each)
foldr (3 marks each)
product [] = 1
product (x:xs) = x * product xs
product = foldr (*) 1
length [] = 0
length (_:xs) + length xs
length = foldr = (\ _ xs = 1 + xs) (0)
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
reverse = foldr (x xs xs ++ [x]) []
(3 x (2 + 3) = 15 Marks)
addOneIfOdd n = case odd n of True -> (\x -> x+1) n
False -> n
addOneIfOdd n = case odd n of True -> (\x -> x+1) n
False -> n
addOneIfOdd n = case odd n of
True -> f n
False -> n
where f n = n + 1
(2 Marks)
abs ::Integer -> Integer
abs = \x -> (if x>=0 then x else -x)
abs ::Integer -> Integer
abs = \x -> (if x>=0 then x else -x)
d) Write a lambda version of the abs function which takes an Integer and returns the non-negative value.
e.g. abs –1 = 1, abs 1 = 1.
(2 Marks)
(Total for question 1 = 34 Marks)
Question 2
• You are asked to write a function that you may have seen in your assignment to clean up ‘votes’ by removing duplicate preferences (and all that follow) and removing all preferences after a skip in preference (You may assume that the input list is sorted in ascending order) :
clean:: [Integer] -> [Integer]
that takes an (integer) list (of preferences) and returns the list with duplicates (and preferences larger than that) deleted. All preferences are deleted after a skip in preferences.
e.g. clean [1,2,3,4] = [1,2,3,4] — All preferences are valid
clean [1,2,2,3,4,5] = [1] — Delete preference 2 and all that follow
clean [1,2,4,5 ] = [1,2] — Delete all that follow the skipped preference (3)
removeDupsAndRest :: [Integer] -> [Integer]
removeDupsAndRest[] = []
removeDupsAndRest [x1, x2]
| x1 == x2 = []
| otherwise = [x1,x2]
removeDupsAndRest (x1:x2:xs)
| x1 == x2 = []
| otherwise = x1: removeDupsAndRest (x2:xs)
removeHole :: [Integer] -> [Integer]
removeHole xs = [ x | (x,y)<- zip [1..] xs, x ==y]
check :: [Integer] -> [Integer]
check xs = removeHole( removeDupsAndRest xs)
removeDupsAndRest :: [Integer] -> [Integer]
removeDupsAndRest[] = []
removeDupsAndRest [x1, x2]
| x1 == x2 = []
| otherwise = [x1,x2]
removeDupsAndRest (x1:x2:xs)
| x1 == x2 = []
| otherwise = x1: removeDupsAndRest (x2:xs)
removeHole :: [Integer] -> [Integer]
removeHole xs = [ x | (x,y)<- zip [1..] xs, x ==y]
check :: [Integer] -> [Integer]
check xs = removeHole( removeDupsAndRest xs)
(15 Marks)
(b ) Given that we can encode Booleans using the lambda calculus as in:
TRUE = λ x y. x
FALSE = λ x y. y
NOT = λ b.b FALSE TRUE
NOT = λ b.b FALSE TRUE
• NOT
• OR
OR =λ x y . x TRUE y
OR =λ x y . x TRUE y
• x 5 Marks)
remove :: Int -> [Int] -> [Int]
remove x xs = [y | y<- xs , y /= x]
remove :: Int -> [Int] -> [Int]
remove x xs = [y | y<- xs , y /= x]
remove :: Integer -> [Integer] -> [Integer]
which picks out all occurrences of an integer in a list. For instance:
remove 1 [1,2,3,4,1]
will return
[2,3,4]
• Marks)
elem’ :: Int -> [Int] -> Bool
elem’ x xs = remove x xs /= xs
elem’ :: Int -> [Int] -> Bool
elem’ x xs = remove x xs /= xs
elem:: Integer -> [Integer] -> Bool
which returns True if the Integer is an element of the list, and False otherwise.
(4 Marks)
(Total for question 2 = 33 Marks)
Question 3
• Define the higher-order function whileG in which a condition and the operation work over values of type a. Its type should be
whileG :: (a -> IO Bool) -> (a -> IO a) -> (a-> IO a)
whileG :: (a -> IO Bool) -> (a -> IO a) -> (a -> IO a)
whileG cond op x
= do test <- cond x
if test
then do op x
whileG cond op x
else return x
whileG :: (a -> IO Bool) -> (a -> IO a) -> (a -> IO a)
whileG cond op x
= do test <- cond x
if test
then do op x
whileG cond op x
else return x
whileG cond op x
has the effect of repeating
op x
while the condition cond x is True
(10 Marks)
• Explain how the do notation can be used to abbreviate a common pattern of monadic programming, and describe the behaviour of this notation for the particular case of the Result monad.
An expression of the form
do x1 <- m1
x2 <- m2
...
xn <- mn
f x1 x2 ... xn
abbreviates the following pattern:
m1 >>= \x1 ->
m2 >>= \x2 ->
…
mn >>= \xn ->
f x1 x2 … xn
For the case of the Result monad, such an expression only succeeds if each of the component expressions m1..mn succeeds, in which case the resulting values x1.. xn are combined into a single result value by applying the function f.
An expression of the form
do x1 <- m1
x2 <- m2
...
xn <- mn
f x1 x2 ... xn
abbreviates the following pattern:
m1 >>= \x1 ->
m2 >>= \x2 ->
…
mn >>= \xn ->
f x1 x2 … xn
For the case of the Result monad, such an expression only succeeds if each of the component expressions m1..mn succeeds, in which case the resulting values x1.. xn are combined into a single result value by applying the function f.
(8 marks)
• Using the do notation, define a function
sequence :: [Result a] → Result [a]
that transforms a list of results into a single result.
sequence [] = return []
sequence (mx:mxs) = do x <- mx
xs <- sequence mxs
return (x:xs)
sequence [] = return []
sequence (mx:mxs) = do x <- mx
xs <- sequence mxs
return (x:xs)
• Explain why sequence is not specific to the Result monad, and state the general type that can be specified for this function.
The sequence function is not specific to the Result monad because
its definition only makes use of the basic monadic operations return
and >>=, which are defined for any monad. Hence, we have:
sequence :: Monad m => [m a] -> m [a]
The sequence function is not specific to the Result monad because
its definition only makes use of the basic monadic operations return
and >>=, which are defined for any monad. Hence, we have:
sequence :: Monad m => [m a] -> m [a]
(7 marks)
(Total for question 3 = 33 Marks)
Question 4
(a ) Using the idea of the search tree, defined as follows:
data Tree a =
EmptyTree
| Node (Tree a) a (Tree a) deriving (Show, Read, Eq)
and
flatten :: Tree a -> [a]
flatten EmptyTree = []
flatten (Node EmptyTree x EmptyTree) = [x]
flatten (Node l x r) = flatten l
++ [x]
++ flatten r
flatten :: Tree a -> [a]
flatten EmptyTree = []
flatten (Node EmptyTree x EmptyTree) = [x]
flatten (Node l x r) = flatten l
++ [x]
++ flatten r
(given the usual meaning of flatten)
• Write the code for the function flatten.
(6 Marks)
occurs x (Node l y r)
| x == y = True
| x < y = occurs x l
| x > y = occurs x r
occurs x (Node l y r)
| x == y = True
| x < y = occurs x l
| x > y = occurs x r
occurs :: a -> Tree a -> Bool
which returns True if the given element exists in the tree and False otherwise.
(6 Marks)
(b ) Referring to the abstract machine below:
data Expr = Val Int | Add Expr Expr | Mult Expr Expr
data Op = EVAL Expr | ADD Int | MULT Int
type Cont = [Op]
eval:: Expr -> Cont -> Int
eval(Val n) c = exec c n
eval(Add x y) c = eval x (EVAL y: c)
exec :: Cont -> Int -> Int
exec [] n = n
exec (EVALy: c) n = eval y (ADD n: c)
exec (ADD n : c) m = exec c (n + m)
val :: Expr -> Int
val e = eval e []
(i) show how you would evaluate the following expression:
(Add (Add (Val 2) (Val 3) ) (Val 4))
ANS : show order of evaluation etc. result = 7
(4 Marks)
(ii) The abstract machine (as per above) only implements additon. Show how you would extend this implementation to implement mutliplication.
data Expr = Val Int | Add Expr Expr | Mult Expr Expr
data Op = EVALA Expr | EVALM Expr | ADD Int | MULT Int
type Cont = [Op]
eval:: Expr -> Cont -> Int
eval(Val n) c = exec c n
eval(Add x y) c = eval x (EVALA y: c)
eval(Mult x y) c = eval x (EVALM y: c)
exec :: Cont -> Int -> Int
exec [] n = n
exec (EVALA y: c) n = eval y (ADD n: c)
exec (EVALM y: c) n = eval y (MULT n:c)
exec (ADD n : c) m = exec c (n + m)
exec (MULT n : c) m = exec c (n * m)
val :: Expr -> Int
val e = eval e []
data Expr = Val Int | Add Expr Expr | Mult Expr Expr
data Op = EVALA Expr | EVALM Expr | ADD Int | MULT Int
type Cont = [Op]
eval:: Expr -> Cont -> Int
eval(Val n) c = exec c n
eval(Add x y) c = eval x (EVALA y: c)
eval(Mult x y) c = eval x (EVALM y: c)
exec :: Cont -> Int -> Int
exec [] n = n
exec (EVALA y: c) n = eval y (ADD n: c)
exec (EVALM y: c) n = eval y (MULT n:c)
exec (ADD n : c) m = exec c (n + m)
exec (MULT n : c) m = exec c (n * m)
val :: Expr -> Int
val e = eval e []
(8 Marks)
(c ) Define a function nestedreverse which takes a list of strings as its argument and reverses each element of the list and then reverses the resulting list. Thus,
nestedreverse [ “in”, “the”, “end” ] = [“dne”, “eht”, “ni” ]
nestedreverse :: [String] -> [String]
nestedreverse = reverse . map reverse
nestedreverse :: [String] -> [String]
nestedreverse = reverse . map reverse
(9 Marks)
(Total for question 4 = 33 Marks)