PROGRAMMING AS PROBLEM SOLVING (ADVANCED)
COMP1130
checksum:
AAAAA
bytes:
60
Important:. Code templates for answers to questions in this exam can be found in the accompanying IntelliJ project. You can place this Web page for the exam in a window side-by-side with the IntelliJ 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 IntelliJ in which you can load your solution codes into GHCi and test them out.
Modify only the undefined function—do not modify anything apart from their definitions. Simply replace the undefined body of each function with your definition. Make sure to give both type signature and definition. The specifications of the function are provided in the comments immediately above the definitions. You must adhere to those specifications. The comments also show sample tests of your solutions, which you can try in GHCi, or use with doctest.
Code questions are auto-graded, so you will be graded according to how many tests you pass, including those given in the comments. The auto-grader will only mark what you upload to the exam. Therefore it is essential that you upload your code into this exam, in the browser. Incorrect answers that somehow manage to pass tests will still be penalized accordingly.

Total marks: 60
Writing period: 60 minutes duration.
Permitted materials: None, aside from the software environment provided.

You should attempt to answer all questions.
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

  [15 Marks]

For each of the following questions, identify the choice that provides the best answer.

1 i)

  [2.5 Marks]

  Binary representations

Using an unsigned binary interpretation, what is 100111 in decimal?

4
39
32
42

1 ii)

  [2.5 Marks]

  Binary representations

Using a two's complement 8-bit signed binary interpretation, what is 11001100 in decimal?

-42
-52
-50
42

1 iii)

  [2.5 Marks]

  Binary representations

Using a two's complement 8-bit signed binary interpretation, what is the highest positive decimal number that can be represented?

8
16
127
128

1 iv)

  [2.5 Marks]

  Binary representations

How many distinct values can be represented in 8 bits

8
16
128
256

1 v)

  [2.5 Marks]

  Haskell function declarations

Which of the following is not a valid Haskell function type signature?

sum x y = x + y
sum :: Integer -> Integer
sum :: Integer -> Integer -> Integer
rotate :: Picture -> Picture

1 vi)

  [2.5 Marks]

  Haskell function declarations

Which of the following is a valid Haskell function type signature for the following Haskell function?

plus x y = x + y

plus :: Integer -> Integer
plus :: Integer -> Integer -> Integer
sum :: Integer -> Integer -> Integer
plus :: String -> String -> String

Question 2

  [5 Marks]

  Haskell function signatures

Consider the following function signature, which uses the CodeWorld Picture type:

scale :: Picture -> Integer -> Picture
Given the following True/False questions about the function scale, mark each either True or False. If uncertain, use the 'Clear' button to clear your answer.
Each correct answer gains you 1 mark, each incorrect answer loses you 0.5 mark, while a question left unanswered neither loses nor gains marks.
The final mark for this question is calculated by bounding the sum of marks between 0 and 5. For example, if you answered all questions correctly you would gain 5 (not 8) for this question. If you answer 3 correctly, 2 incorrectly and leave the remaining 3 unanswered you would gain 2/5 for this question.

TrueFalse
The function takes three arguments
The function can be applied to a Picture and then to an Integer.
The function can be applied to a Picture and then to an Integer and then to a Picture.
The function can be applied to a Picture, producing a value that can then be applied to an Integer.
[Hint: be careful with this one!]
The function can be applied to an Integer, producing a value that can then be applied to a Picture.
[Hint: be careful with this one!]
The function modifies the first input argument.
The function has a side-effect.
The function is pure.

Question 3

  [5 Marks]

  Function definition (Minimum.hs)

Using the incomplete template for Minimum.hs in your mid-semester exam IntelliJ project, complete a definition for the function min. You may not use the function min from the Prelude.

Upload the Minimum.hs file, either by clicking on the 'Choose File' button, or by dragging the file from IntelliJ onto the 'Choose File' button.

Question 4

  [10 Marks]

  Enumeration types, function definitions (Cities.hs)

Using the incomplete template for Cities.hs in your mid-semester exam IntelliJ project, provide definitions of the functions stateOfCity and isCityInState.

Upload the Cities.hs file, either by clicking on the 'Choose File' button, or by dragging the file from IntelliJ onto the 'Choose File' button.

Question 5

  [5 Marks]

  Primitive recursion and the fixpoint combinator (Fixpoint.hs)

Using the incomplete template for Fixpoint.hs in your mid-semester exam IntelliJ project, provide a definition of the function fact.

Upload the Fixpoint.hs file, either by clicking on the 'Choose File' button, or by dragging the file from IntelliJ onto the 'Choose File' button.

Question 6

  [10 Marks]

  Lists and recursion (SumLists.hs)

Using the incomplete template for SumLists.hs in your mid-semester exam IntelliJ project, provide a definition of the function sumLists.

Upload the SumLists.hs file, either by clicking on the 'Choose File' button, or by dragging the file from IntelliJ onto the 'Choose File' button.

Question 7

  [10 Marks]

  The Lambda Calculus

Each correct answer gains you 2 marks, each incorrect answer loses you 1 mark.

Consider the following lambda terms. For each, choose the correct evaluation of the term, to the point where no further beta-reductions can be applied.

7 i)

  [2 Marks]

(λx.x) y

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

7 ii)

  [2 Marks]

(λx.xy) (λz.z)

x
y
z
x y

7 iii)

  [2 Marks]

(λx.λy.x) w z

x
y
z
w

7 iv)

  [2 Marks]

(λx.λy.y) y x

x
y
y x
λy.x

7 v)

  [2 Marks]

Which of the following terms is equivalent to λx.λy.(y w) up to renaming of bound variables?

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