PROGRAMMING AS PROBLEM SOLVING (INCLUDING ADVANCED)
COMP1100/COMP1130
checksum:
AAAAA
bytes:
60
Important notice: Code templates for programming questions in this exam can be found in the accompanying VSCodium project. You can place this Web page for the exam next to the VSCodium project window, so that you can conveniently switch between them while working on your answers. You will also want to open the Terminal tool in VSCodium, in which you test your solution code with ghci. You can also make use of doctest for testing.

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

  [10 Marks]

  True/False questions

This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.

Consider the following type declarations:

mystery :: Bool -> Int -> String -> Bool
 enigma  :: (String -> Bool) -> Bool

Mark True for each of the following statements if it is correct, and False if it is not.

Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark, while a question left unanswered neither loses nor gains marks. The minimum total mark for this question is 0.

TrueFalse
mystery True has type Int -> String -> Bool
mystery . enigma is a valid composition
If mystery is given only one input, the result can be used as input to enigma
mystery . mystery is a valid composition
The type of enigma is the same as String -> Bool -> Bool

Question 2

  [20 Marks]

  Multiple choice questions

All questions in this section are for BOTH COMP1100 and COMP1130 students.

For each of the following questions, mark the single correct answer.

Each correct answer gains you 2 marks. Each incorrect answer or question left unanswered neither loses nor gains marks.

2 i)

  [2 Marks]

  Haskell variables

Which statement about variables in Haskell is false?

Their names must start with lower case letters
Their names should be chosen to be informative to readers of the program
They are used similarly to mathematics to refer to unknown values
They can appear between \ and -> in the syntax of anonymous functions
They refer to parts of the computer's memory which can be read or written to

2 ii)

  [2 Marks]

  Haskell syntax

Which of the following can be done with the Haskell keyword type?

Define a constructor that acts on types, such as Maybe
Define a new algebraic datatype
Define a synonym for a previously defined datatype
Output the type of the program it is applied to
Print to the screen or accept input from the keyboard

2 iii)

  [2 Marks]

  Lists

Which of the following statements about lists are correct?

The pattern x:y:xs represents a list with at least two elements
The pattern _:xs represents a list with a single element
The type [a] represents a list with a single element of any type
The type [[a]] represents a list of single element lists
The empty list is represented by the pattern [_]

2 iv)

  [2 Marks]

  Parametric polymorphism

Consider the following type declaration:

calculate :: a -> [a] -> b -> [(a,b)]

Which of the following statements is correct?

The first and third arguments cannot both be Int
It is possible for the first argument to be a Char and the second and third arguments to be String
If calculate were given a Double as its only input, the resulting function's first argument could have any type
The output of the function is a list of pairs where the two items in each pair must be different types
It is possible for the first argument to be an Int and the second and third arguments to be String

2 v)

  [2 Marks]

  Style

Consider the function:

hasTrue :: [Bool] -> Bool
 hasTrue list = case list of
   []   -> False
   b:bs -> b || hasTrue bs

Which of the following is the best comment for this function?

[Written next to final line] -- b is the head of the list, bs is the tail of the list
-- I think I could use a higher order function for this but I don't remember which one
-- Recurses through the input list, returning False in the base case and using || in the step case
-- Returns True if any Bool in the input list is True; False otherwise
None of these comments is adequate on their own; combining several is necessary

2 vi)

  [2 Marks]

  Folds

Which of the following pairs of functions are not mathematically equal, when we instantiate the type variables in foldl and foldr to both be Double:

foldr (+) and foldl (+)
foldr (*) and foldl (*)
foldr (**) and foldl (**)
foldr (\_ _ -> 0) and foldl (\_ _ -> 0)
foldr min and foldl min

2 vii)

  [2 Marks]

  Binary Search Trees

Given the standard definition of Binary Tree:

data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)

suppose we have the Binary Search Tree of Ints:

Node (Node (Node Null 16 Null) 19 Null) 24 (Node (Node Null 26 Null) 28 (Node Null 31 Null))

If we search this tree for the number 27, using the usual Binary Search algorithm, which nodes will we visit?

19, 24, 26, 28, 31
24, 26, 28
26, 28
26, 28, 31
All nodes; in this worst case using a Binary Search Tree does not help

2 viii)

  [2 Marks]

  Complexity

Which of the following mathematical functions has the best (smallest) Big-O complexity?

f(x) = x2 + 1500
f(x) = 2x3 + 4
f(x) = 2x + 1
f(x) = x * log x + 2000
f(x) = x + x3

2 ix)

  [2 Marks]

  More Complexity

Consider the following function:

multiplyAll :: [Int] -> Int
 multiplyAll list = case list of
   []   -> 1
   x:xs -> x * multiplyAll xs


What is the worst case time complexity of multiplyAll?

O(log n)
O(n)
O(n2)
O(n log n)
O(2n)

2 x)

  [2 Marks]

  Sorting

Recall the definition of Merge Sort:

merge :: Ord a => [a] -> [a] -> [a]
 merge list1 list2 = case (list1,list2) of
   (list,[]) -> list
   ([],list) -> list
   (x:xs,y:ys)
     | x <= y    -> x : merge xs (y:ys)
     | otherwise -> y : merge (x:xs) ys

mSort :: Ord a => [a] -> [a]
 mSort list = case list of
   []  -> []
   [x] -> [x]
   _   -> merge (mSort firsthalf) (mSort secondhalf)
   where
     firsthalf = take half list
     secondhalf = drop half list
     half = (length list) `div` 2


What is the worst case time complexity of mSort?

O(n log n)
O(n2)
linear
exponential
O(n4)

Question 3

  [5 Marks]

  InLimits.hs

The following instructions apply to all programming questions below and should be read carefully.

There are seven Haskell files for COMP1100 students to complete and six Haskell files for COMP1130 students to complete. Files contain various numbers of functions to complete. Each function is worth 5 marks, except as otherwise noted in the text of HigherOrder.hs 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 InLimits.hs in your final exam VSCodium project. This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.

Question 4

  [10 Marks]

  Monsters.hs

Complete the program Monsters.hs in your final exam VSCodium project. This question is for COMP1100 STUDENTS ONLY. Do NOT attempt if you are a COMP1130 Student.

Question 5

  [5 Marks]

  JumpAdd.hs

Complete the program JumpAdd.hs in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 6

  [15 Marks]

  Maze.hs

Complete the program Maze.hs in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 7

  [10 Marks]

  HigherOrder.hs

Complete the program HigherOrder.hs in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 8

  [15 Marks]

  Managers.hs

Complete the program Managers.hs in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 9

  [10 Marks]

  EqLists.hs

Complete the program EqLists.hs in your final exam VSCodium project. This question is for BOTH COMP1100 AND COMP1130 STUDENTS.

Question 10

  [5 Marks]

  TypeChecking.hs

Complete the program TypeChecking.hs in your final exam VSCodium project. This question is for COMP1130 STUDENTS ONLY. Do NOT attempt if you are a COMP1100 student.

Question 11

  [20 Marks]

  Lambda Calculus

All questions in this section are for COMP1130 STUDENTS ONLY. Do NOT attempt if you are a COMP1100 student.

In your answers below you may write \ for λ and |- for . Write -> to indicate that an expression beta-reduces to another, and = for alpha-equality.

If asked to present a typing derivation, use a numbered list of typing judgements, with a clear justification beside each line, e.g.

1. x : Bool -> alpha, y : Bool |- x : Bool -> alpha [Variable]
 2. x : Bool -> alpha, y : Bool |- y : Bool [Variable]
 3. x : Bool -> alpha, y : Bool |- x y : alpha [1,2,Application]
 4. x : Bool -> alpha |- \x. x y : Bool -> alpha [3,Lambda]

11 i)

  [3 Marks]

Recall the encodings of the Boolean constants from lectures:

True as λx.λy. x
False as λx.λy. y

and consider the lambda term

A = λx.λy. y True (x False True)

Show using non-deterministic beta-reduction that A True False is beta-equal to False. Present every step of the reduction.

11 ii)

  [2.5 Marks]

Present every step of the lazy evaluation of the term:

(λw.λy. w w) y ((λy.λx. y x) (x z))

11 iii)

  [2.5 Marks]

Present every step of the strict evaluation of the same term:

(λw.λy. w w) y ((λy.λx. y x) (x z))

11 iv)

  [4 Marks]

Suggest encodings into the untyped lambda calculus of three functions called left, right, and case, obeying the following two properties:

case (left A) B C is beta-equal to B A
case (right A) B C is beta-equal to C A

for any lambda terms A, B, and C.

You may use any the following combinators presented in lectures: True, False, if...then...else, <...,...>, fst, snd, all natural numbers, isZero, succ, pred, and the fixed-point combinator Y. If you use any of these combinators you should not refer to the details of their particular encodings; you may simply assume that they have been correctly encoded.

11 v)

  [3 Marks]

Suppose we have two different correct encodings of the natural numbers and their operations isZero, succ, and pred. To tell them apart, call the parts of one encoding

0A,1A,2A,...,isZeroA,succA,predA

and the parts of the other encoding

0B,1B,2B,...,isZeroB,succB,predB

Define a lambda term called translate so that

translate nA is beta-equal to nB

for any natural number n. You may use combinators for Booleans, pairs, and the fixed-point combinator Y, as for the previous question.

11 vi)

  [5 Marks]

Give the principal type of

λx.λy.λz. x y (z y)

Justify your answer by presenting a full typing derivation.