Total marks: 100
Reading period: 15 Minutes duration (no use of keyboard or selection of answers).
Writing period: 180 Minutes duration.
Permitted materials: One A4 page with notes on both sides, Unannotated paper-based dictionary.
Note that links to the specification of the Prelude and Data.List libraries are provided.
Questions are not of equal value.
All questions must be completed on this web form.
Your work is automatically saved and recorded as you type.
This is a closed examination. You may not copy this exam.
Question 1
[30 Marks]
Multiple choice questions
For each of the following questions, mark the single correct answer.
1 i)
[2 Marks]
Haskell Interpreter
Which of the following statements about Haskell's interpreter is true?
The interpreter transforms a whole program | |
The interpreter executes code line-by-line | |
The interpreter turns machine-level programs into high-level programs | |
The interpreter translates between imperative and declarative programming | |
1 ii)
[2 Marks]
Built-in functions
Consider the function
between1And10 :: Int -> Bool
between1And10 n
| n < 1 = False
| n > 10 = False
| otherwise = True
Which of the following definitions of between1And10
is functionally the same as the one above? (Two functions are functionally the same if they return the same output whenever they are given the same input.)
between1And10 n = not ((n < 1) && (n <= 10)) | |
between1And10 n = not (10 < n) || (n < 1) | |
between1And10 n = not (10 < n) && not (n < 1) | |
between1And10 n = (1 <= n <= 10) | |
1 iii)
[2 Marks]
Types and Data
Which of the following is not a valid definition in Haskell?
type IntTimesBool = (Int, Bool) | |
data IntTimesBool = Combine (Int, Bool) | |
type IntTimesBool = Combine Int Bool | |
data IntTimesBool = Combine Int Bool | |
1 iv)
[2 Marks]
Associativity of ->
Which of the following options is the same as a -> (a -> b) -> a
?
(a -> (a -> b)) -> a | |
(a -> a -> b) -> a | |
a -> ((a -> b) -> a) | |
a -> (a -> (b -> a)) | |
1 v)
[2 Marks]
Testing
Which of the following statements about testing is true?
If testing of your code does not give any errors, then you know that the code has no bugs. | |
In black box tests, special cases should be tested individually. | |
White box tests are written without looking at the code, while black box tests are motivated by the code. | |
You need to write new black box tests every time the code changes. | |
1 vi)
[2 Marks]
Anonymous functions
Consider the function
myFunction :: Int -> Int -> Int
myFunction x y = x + 2 * y
Which of the following anonymous functions is functionally the same? (Recall that two functions are functionally the same if they return the same output whenever they are given the same input.)
\y -> \x -> y + x + x | |
\x y -> (2 + x) * y | |
\x -> x + \y -> 2 * y | |
\x -> \y -> y + x + x | |
\y -> \x -> x + 2 * y | |
1 vii)
[2 Marks]
Errors
Consider the following Haskell code:
3 minusTwo :: Int -> Int
4 minusTwo n = minusOne (n-1)
5 where minusOne m = m-1
6
7 minusThree :: Int -> Int
8 minusThree n = minusTwo (minusOne n)
9
When compiling this we get the following error:
error: Variable not in scope: minusOne :: Int -> Int
|
8 | minusThree n = minusTwo (minusOne n)
| ^^^^^^^^
How can we make the file compile without errors?
Remove the indentation on line 5 before the where clause | |
Copy the where clause from line 5 to line 9 | |
Change every occurrence of n on line 8 to m | |
Swap the order of minusTwo and minusOne on line 8 | |
1 viii)
[2 Marks]
Folds
When we write foldr f
then each time the function f
is called, its inputs will be
First the base case, then a list | |
First the head of a list, then the result of the recursive call on the tail of that list | |
First the head of a list, then the value accumulated from the initial part of the original list | |
First a list, then the base case | |
First the result of the recursive call on the tail of a list, then the head of that list | |
First the value accumulated from the initial part of the original list, then the head of a list | |
1 ix)
[2 Marks]
Game Trees
Assume that it is our move next in a two player game. In this game moves alternate strictly between the players. We are trying to maximise a heuristic, while our opponent is trying to minimise that number. Given the game tree below, what value will the minimax algorithm return for the root?
0 | |
1 | |
3 | |
8 | |
9 | |
1 x)
[2 Marks]
Ad Hoc Polymorphism
What is the most general correct type declaration for the following function definition?
foo x y = show (x == y)
foo :: Eq a => a -> a -> String | |
foo :: (Eq a, Eq b) => a -> b -> String | |
foo :: (Eq a, Show a) => a -> a -> String | |
foo :: (Eq a, Show a, Eq b, Show b) => a -> b -> String | |
foo :: Show a => a -> a -> String | |
foo :: (Show a, Show b) -> a -> b -> String | |
1 xi)
[2 Marks]
Evaluation Order
Recall that id
is the polymorphic identity function, and that negate
is the function in Num
with default behaviour
negate x = 0 - x
Thinking about the evaluation order of Haskell, how will the following program evaluate?
id (negate (id 5))
⟹ id (negate 5) ⟹ id (0 - 5) ⟹ 0 - 5 ⟹ -5 | |
⟹ id (negate 5) ⟹ id (0 - 5) ⟹ id (-5) ⟹ -5 | |
⟹ id (negate 5) ⟹ negate 5 ⟹ 0 - 5 ⟹ -5 | |
⟹ negate (id 5) ⟹ 0 - id 5 ⟹ 0 - 5 ⟹ -5 | |
⟹ negate (id 5) ⟹ negate 5 ⟹ 0 - 5 ⟹ -5 | |
1 xii)
[2 Marks]
Complexity
Consider the function
eraseOne :: Eq a => a -> [a] -> [a]
eraseOne x list = case list of
[] -> []
y:ys
| x == y -> ys
| otherwise -> y : eraseOne x ys
How could you describe the best case, with respect to 'Big O' time complexity, of eraseOne x list
?
list has exactly one element, which is equal to x | |
list is empty | |
the head of list is equal to x | |
the last element of list is equal to x | |
x is not in list | |
1 xiii)
[2 Marks]
Complexity
What is the worst case time complexity of eraseOne
?
O(1) | |
O(n) | |
O(n2) | |
O(n3) | |
O(n4) | |
O(2n) | |
1 xiv)
[2 Marks]
Complexity
Consider the function
largest :: Ord a => [a] -> a
largest list = case list of
[] -> error "empty list"
x:xs -> foldr max x xs
What is the worst case time complexity of largest
?
O(1) | |
O(n) | |
O(n2) | |
O(n3) | |
O(n4) | |
O(2n) | |
1 xv)
[2 Marks]
Complexity
Consider the function
largeSort :: Ord a => [a] -> [a]
largeSort list = case list of
[] -> []
_ -> largeSort (eraseOne large list) ++ [large]
where
large = largest list
What is the worst case time complexity of largeSort
?
O(1) | |
O(n) | |
O(n2) | |
O(n3) | |
O(n4) | |
O(2n) | |
Question 2
[10 Marks]
Numbers.hs
The following instructions apply to all programming questions below and should be read carefully.
There are seven Haskell files to complete. Files contain various numbers of functions to complete. Each function is worth 5 marks. Completion of the later functions in files do not require you to complete the earlier functions, except where noted otherwise in the file's text. You will find the template Haskell files in a folder on your desktop, and in VSCodium.
You may define helper functions if you wish. You may use any Haskell function available in the Prelude or basic libraries. The doctests in the file are intended to help you, but are not intended to be exhaustive, and do not replace your need to test your own code. Your code will be marked both for correctness and for other aspects of quality, such as style.
Please submit by dragging and dropping each Haskell file into the white box below each question. Do not rename the files before submission. You should be able to see the text of the file you have submitted in the box. No further testing feedback will be supplied to you. You may submit to the same question multiple times; if you do so, your previous submission will be overwritten. Your work will only be visible to markers if you submit it correctly. Therefore it is essential that you upload your code into this exam by dragging your file into the appropriate box.
Complete the program Numbers.hs
in your final exam VSCodium project.
Question 3
[10 Marks]
Stomachs.hs
Complete the program Stomachs.hs
in your final exam VSCodium project.
Question 4
[5 Marks]
Fliponacci.hs
Complete the program Fliponacci.hs
in your final exam VSCodium project.
Question 5
[10 Marks]
ListInsertions.hs
Complete the program ListInsertions.hs
in your final exam VSCodium project.
Question 6
[10 Marks]
FunctionLists.hs
Complete the program FunctionLists.hs
in your final exam VSCodium project.
Question 7
[15 Marks]
Trees.hs
Complete the program Trees.hs
in your final exam VSCodium project.
Question 8
[10 Marks]
UnitLists.hs
Complete the program UnitLists.hs
in your final exam VSCodium project.