COMP3141
Software System Design and Implementation
SAMPLE EXAM
Term 2, 2020
Declaration
I, Stefan Gao (5211215), declare that these answers are entirely my own, and that I did
not complete this exam with assistance from anyone else.
Part A (25 Marks)
Answer the following questions in a couple of short sentences. No need to be verbose.
1. (3 Marks) What is the difference between a partial function and partial application?
2. (3 Marks) Name two methods of measuring program coverage of a test suite, and
explain how they differ.
3. (3 Marks) How are multi-argument functions typically modelled in Haskell?
Total Number of Parts: 5.●
Total Number of Marks: 125●
All parts are of equal value.●
Answer all questions.●
Excessively verbose answers may lose marks●
Failure to make the declaration or making a false declaration results in a 100% mark
penalty.
●
Ensure you are the person listed on the declaration.●
All questions must be attempted individually without assistance from anyone else.●
You must save your exam paper using the button below before time runs out.●
Late submissions will not be accepted.●
You may save multiple times before the deadline. Only your final submission will be
considered.
●
4. (3 Marks) Is the type of getChar below a pure function? Why or why not?
getChar :: IO Char
5. (3 Marks) What is a functional correctness specification?
6. (3 Marks) Under what circumstances is performance important for an abstract model?
7. (3 Marks) What is the relevance of termination for the Curry-Howard correspondence?
8. (4 Marks) Imagine you are working on some price tracking software for some company
stocks. You have already got a list of stocks to track pre-defined.
data Stock = GOOG | MSFT | APPL
stocks = [GOOG, MSFT, APPL]
Your software is required to produce regular reports of the stock prices of these
companies. Your co-worker proposes modelling reports simply as a list of prices:
type Report = [Price]
Where each price in the list is the stock price of the company in the corresponding
position of the stocks list. How is this approach potentially unsafe? What would be a
safer representation?
Part B (25 Marks)
The following questions pertain to the given Haskell code:
getChar
getChar ::
data Stock = | |
stocks = [,,]
type Report = [Price]
foldr :: (a → b → b) → b → [a] → b
foldr f z (x : xs) = f x (foldr f z xs) -- (1)
foldr f z [] = z -- (2)
1. (3 Marks) State the type, if one exists, of the expression
foldr ( : ) ([] :: [Bool]).
2. (4 Marks) Show the evaluation of foldr ( : ) [] [1, 2] via equational
reasoning.
3. (2 Marks) In your own words, describe what the function foldr ( : ) [] does.
4. (12 Marks) We shall prove by induction on lists that, for all lists xs and ys:
foldr ( : ) xs ys = ys ++ xs
i. (3 Marks) First show this for the base case where ys = [] using equational
reasoning. You may assume the left identity property for ++, that is, for all ls:
ls = [] ++ ls
ii. (9 Marks) Next, we have the case where ys = (k : ks) for some item k
and list ks.
a. (3 Marks) What is the inductive hypothesis about ks?
foldr :: (a → b → b) → b → [a] → b
foldr f z (x : xs)
foldr f z []
=
=
f x (foldr f z xs)
z
--
--
()
()
foldr (:) ([] :: [])
foldr (:) [] [1, 2]
foldr (:) []
xs ys
foldr (:) xs ys = ys ++ xs
ys = []
++ ls
ls = [] ++ ls
ys = (k : ks) k
ks
ks
b. (6 Marks) Using this inductive hypothesis, prove the above theorem for the
inductive case using equational reasoning.
5. (2 Marks) What is the time complexity of the function call foldr ( : ) [] xs,
where xs is of size n?
6. (2 Marks) What is the time complexity of the function call
foldr (λa as → as ++ [a]) [] xs, where xs is of size n
Part C (25 Marks)
A sparse vector is a vector where a lot of the values in the vector are zero. We represent a
sparse vector as a list of position-value pairs, as well as an Int to represent the overall
length of the vector:
data SVec = SV Int [(Int, Float)]
We can convert a sparse vector back into a dense representation with this expand
function:
expand :: SVec → [Float]
expand (SV n vs) = map check [0. . n − 1]
where
check x = case lookup x vs of
Nothing → 0
Just v → v
For example, the SVec value SV 5 [(0, 2.1), (4, 10.2)] is
foldr (:) [] xs
xs n
foldr (λa as → as ++ [a]) [] xs xs n

data SVec = [(, )]
expand
expand :: SVec → []
expand ( n vs) = map check [0. . n − 1]
where
check x = case lookup x vs of

v
→
→
0
v
SVec 5 [(0, 2.1), (4, 10.2)]
expanded into [2.1, 0, 0, 0, 10.2]
1. (16 Marks) There are a number of SVec values that do not correspond to a
meaningful vector - they are invalid.
i. (6 Marks) Which two data invariants must be maintained to ensure validity of an
SVec value? Describe the invariants in informal English.
ii. (4 Marks) Give two examples of SVec values which violate these invariants.
iii. (6 Marks) Define a Haskell function
wellformed:: SVec → Bool which returns True iff the data invariants hold for
the input SVecvalue. Your Haskell doesn't have to be syntactically
perfect, so long as the intention is clear.
You may find the function nub:: (Eq a) ⇒ [a] → [a]
useful, which removes duplicates from a list.
2. (9 Marks) Here is a function to multiply a SVec vector by a scalar:
vsm:: SVec → Float → SVec
vsm (SV n vs) s = SV n (map (λ(p, v) → (p, v ∗ s)) vs)
i. (3 Marks) Define a function vsmA that performs the same operation, but for
dense vectors (i.e. lists of Float).
ii. (6 Marks) Write a set of properties to specify functional correctness of this function.
Hint: All the other functions you need to define the properties have already been
mentioned in this part. It should maintain data invariants as well as refinement
from the abstract model.
[2.1, 0, 0, 0, 10.2]
SVec
SVec
SVec
wellformed :: SVec → Bool

SVecvalue
nub :: ( a) ⇒ [a] → [a]
SVec
vsm :: SVec → Float → SVec
vsm ( n vs) s = n (map (λ(p, v) → (p, v ∗ s)) vs)
vsmA

Part D (25 Marks)
1. (10 Marks) Imagine you are working for a company that maintains this library for a
database of personal records, about their customers, their staff, and their suppliers.
newtype Person = …
name:: Person → String
salary :: Person → Maybe String
fire :: Person → IO ()
company:: Person → Maybe String
The salary function returns Nothing if given a person who is not a
member of company staff. The fire function will also perform no-op unless the
given person is a member of company staff. The company function will return
Nothing unless the given person is a supplier.
Rewrite the above type signatures to enforce the distinction between the different
types of person statically, within Haskell's type system. The function name must
work with all kinds of people as input.
Hint: Attach phantom type parameters to the Person type.
2. (15 Marks) Consider the following two types in Haskell:
newtype Person = …
name :: Person → String
salary :: Person → String
fire :: Person → ()
company :: Person → String
salary
fire
company

name
Person
data List a where
Nil :: List a
Cons :: a → List a → List a
data Nat = Z | S Nat
data Vec (n :: Nat) a where
VNil :: Vec Z a
VCons :: a → Vec n a → Vec (S n) a
What is the difference between these types? In which circumstances would Vec be
the better choice, and in which List?
i. (5 Marks)
ii. (5 Marks) Here is a simple list function:
zip :: List a → List b → List (a, b)
zip Nil ys = Nil
zip xs Nil = Nil
zip (Cons x xs) (Cons y ys) = Cons (x, y) (zip xs ys)
Define a new version of zip which operates on Vec instead of List
wherever possible. You can constrain the lengths of the input.
data List a where


data Nat = | Nat
data Vec (n :: Nat) a where


::
::
::
::
List a
a → List a → List a
Vec a
a → Vec n a → Vec ( n) a
Vec
List
zip :: List a → List b → List (a, b)
zip
zip
zip

xs
( x xs)
ys

( y ys)
=
=
=


(x, y) (zip xs ys)
zip Vec List
iii. (5 Marks) Here is another list function:
filter :: (a → Bool) → List a → List a
filter p Nil = Nil
filter p (Cons x xs)
| p x = Cons x (filter p xs)
| otherwise = filter p xs
Define a new version of filter which operates on Vec instead of List
wherever possible.
Part E (25 Marks)
1. (10 Marks) An applicative functor is called commutative iff the order in which actions
are sequenced does not matter. In addition to the normal applicative laws, a
commutative applicative functor satisfies:
f ⟨$⟩ u ⟨ ∗ ⟩ v = flip f ⟨$⟩ v ⟨ ∗ ⟩ u
i. (2 Marks) Is the Maybe Applicative instance commutative? Explain your
answer.
filter :: (a → ) → List a → List a
filter p =
filter p ( x xs)
| p x
| otherwise
=
=
x (filter p xs)
filter p xs
filter Vec List
f ⟨$⟩ u ⟨∗⟩ v = flip f ⟨$⟩ v ⟨∗⟩ u

ii. (3 Marks) We have seen two different Applicative instances for lists.
Which of these instances, if any, are commutative? Explain your answer.
iii. (5 Marks) A commutative monad is the same as a commutative applicative, only
specialised to monads. Express the commutativity laws above in terms of monads,
using either do notation or the raw pure/bind functions.
2. (10 Marks) Translate the following logical formulae into types, and provide Haskell
types that correspond to proofs of these formulae, if one exists. If not, explain why not.
i. (2 Marks) (A ∨ B) → (B ∨ A)
ii. (2 Marks) (A ∨ A) → A
iii. (3 Marks)
(A ∧ (B ∨ C)) → ((A ∧ B) ∨ (A ∧ C))
iv. (3 Marks) ¬((A → ⊥) ∨ A)
3. (5 Marks) Here is a Haskell data type:

do
(A ∨ B) → (B ∨ A)
(A ∨ A) → A
(A ∧ (B ∨ C)) → ((A ∧ B) ∨ (A ∧ C))
¬((A → ⊥) ∨ A)
data X = First () A
| Second () Void
| Third (Either B ())
Using known type isomorphisms, simplify this type as much as possible.
END OF SAMPLE EXAM
(don't forget to save!)
data X =
|
|
()
()
( ())
Loading [MathJax]/jax/output/HTML-CSS/jax.js
Time Remaining
2h 9m 33s

Save