02/08/2021 COMP3141 – Sample Exam
COMP3141 – Sample Exam
Student
Log out
COMP3141
Software System Design and Implementation SAMPLE EXAM
Term 2, 2021
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.
Part A
25 marks
Answer the following questions in a couple of short sentences. No need to be verbose.
Question 1 A 3 marks
What is the difference between a partial function and partial application?
Reference solution
A partial function is a function not defined for its whole domain, whereas partial application is where a (n)-argument function is applied to fewer than (n) values.
Question 2 A 3 marks
Name two methods of measuring program coverage of a test suite, and explain how they differ.
Reference solution
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
1/14
02/08/2021 COMP3141 – Sample Exam
Reference solution
COMP3141 – Sample Exam
Student
Function coverage measures whether or not a given function is executed by the test suite, whereas path coverage measures all possible execution paths. Function coverage is easier to
compute than path coverage.
Log out
Question 3 A 3 marks
How are multi-argument functions typically modelled in Haskell?
Reference solution
Mutliple argument functions are usually modelled by one-argument functions that in turn return functions to accept further arguments. For example, the add function (+) :: Int -> (Int -> Int) takes an Int and returns a function.
Question 4 A 3 marks
Is the type of getChar below a pure function? Why or why not?
getChar :: IOChar
Reference solution
It is not a pure function, but not because it is impure, but because it is not a function. It is instead an IO procedure.
Question 5 A 3 marks
What is a functional correctness specification?
Reference solution
A functional correctness specification is a set of properties that completely specify the definition of correctness for a program. It is often expressed as the combination of data invariants and a refinement from an abstract model.
Question 6 A 3 marks
Under what circumstances is performance important for an abstract model?
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
2/14
02/08/2021 COMP3141 – Sample Exam
pp
COMP3141 – Sample Exam
Student
If we are testing using an abstract model (for example with QuickCheck), then we are still computing with it and thus intractable or uncomputable abstract models would not be suitable.
Log out
Reference solution
Question 7 A 3 marks
What is the relevance of termination for the Curry-Howard correspondence?
Reference solution
The Curry-Howard correspondence assumes that function types are pure and total. Non- termination makes the logic the type system corresponds to inconsistent.
Question 8 A 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.
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:
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?
data Stock = GOOG | MSFT | APPL stocks = [GOOG, MSFT, APPL]
type Report = [Price]
Reference solution
It is not guaranteed that the prices will line up to the stocks, or that there will be a stock for every price and a price for every stock. An alternative would be:
This at least ensures that the right stocks are associated with the right price.
type Report = [(Stock, Price)]
25
Part B
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions 3/14
02/08/2021 COMP3141 – Sample Exam
Part B
COMP3141 – Sample Exam
marks
Student Log out
The following questions pertain to the given Haskell code:
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z (x:xs) = f x (foldr f z xs) — (1) foldrfz[] =z –(2)
Question 9 B 3 marks
State the type, if one exists, of the expression foldr (:) ([] :: [Bool]).
Reference solution
[Bool] -> [Bool]
Question 10 B 4 marks
Show the evaluation of foldr (:) [] [1,2] via equational reasoning.
Reference solution
foldr (:) [] [1,2] =1:(foldr(:)[][2]) –(1) = 1 : 2 : (foldr (:) [] []) — (1) = 1 : 2 : [] — (2)
Question 11 B 2 marks
In your own words, describe what the function foldr (:) [] does.
Reference solution
It is the identity function on lists.
Section B.IV 12 marks
We shall prove by induction on lists that, for all lists xs and ys:
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
4/14
02/08/2021 COMP3141 – Sample Exam
C
OMP3141 – Sample Exam
foldr (:) xs ys = ys ++ xs
Student
Log out
Question 12 B.IV 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.
Reference solution
foldr (:) xs []
= xs — (2)
= [] ++ xs — (id)
Section B.IV.1 9 marks
Next, we have the case where ys = (k:ks) for some item k and list ks.
Question 13 B.IV.1 3 marks
What is the inductive hypothesis about ks?
Reference solution
foldr (:) xs ks = ks ++ xs
Question 14 B.IV.1 6 marks
Using this inductive hypothesis, prove the above theorem for the inductive case using equational reasoning.
Reference solution
foldr (:) xs (k:ks)
= (:) k (foldr (:) xs ks) — (1) =k:(foldr(:)xsks) –simp
= k : (ks ++ xs) — I.H
= (k : ks) ++ xs — def. of (++) reversed
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
5/14
02/08/2021 COMP3141 – Sample Exam
(k : ks) xs def. of ( ) reversed
COMP3141 – Sample Exam
Student
Log out
Question 16 B 2 marks
What is the time complexity of the function call foldr (\a as -> as ++ [a]) [] xs, where xs is of size (n)?
Reference solution
O(n2)
Question 15 B 2 marks
What is the time complexity of the function call foldr (:) [] xs, where xs is of size (n)?
Reference solution
O(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:
We can convert a sparse vector back into a dense representation with this expand function:
For example, the SVec value SV 5 [(0,2.1), (4,10.2)] is expanded into [2.1,0,0,0,10.2]
data SVec = SV Int [(Int, Float)]
expand :: SVec -> [Float]
expand (SV n vs) = map check [0 .. n-1]
where
check x = case lookup x vs of
Nothing -> 0 Justv ->v
Section C.I 16 marks
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions 6/14
02/08/2021 COMP3141 – Sample Exam
There are a number of SVec values that do not correspond to a meaningful vector – they
COMP3141 – Sample Exam
Student
invalid.
are
Log out
Question 17 C.I 6 marks
Which two data invariants must be maintained to ensure validity of an SVec value? Describe the invariants in informal English.
Reference solution
For a value SV n vs, the list vs should contain only one value for a given position, and the positions of all values in vs should all be >= 0 and < n. Question 18 C.I 4 marks Give two examples of SVec values which violate these invariants. Reference solution 1. Violates “only one value for a position”: SV 2 [(1,1.1), (1,5.3)] 2. Violates “all positions >= 0 and < n”: SV 2 [(3,1.1)] Question 19 C.I 6 marks Define a Haskell function wellformed} :: SVec -> Bool which returns True iff the data invariants hold for the input SVec value. 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.
Reference solution
wellformed (SV n vs) = let
ps = map fst vs in
all (\x -> x >= 0 && x < n) ps && nub ps == ps Section C.II 9 marks https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions 7/14 02/08/2021 COMP3141 – Sample Exam COMP3141 – Sample Exam Student Log out 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)
Question 20 C.II 3 marks
Define a function vsmA that performs the same operation, but for dense vectors (i.e. lists of Float).
Reference solution
vsmA xs s = map (* s) xs
Question 21 C.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.
Reference solution
Data invariants:
Data refinement:
wellformed xs ==> wellformed (vsm xs s)
expand (vsm xs s) == vsmA (expand xs) s
Part D
25 marks
Question 22 D 10 marks
Imagine you are working for a company that maintains this library for a database of personal
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
8/14
02/08/2021 g y g p y COMP3141 – Sample Exam y p
records, about their customers, their staff, and their suppliers.
COMP3141 – Sample Exam
Student
Log out
newtype Person = {- … -} name :: Person -> String
salary :: Person -> Maybe String fire :: Person -> IO ()
company :: Person -> Maybe String
Section D.II 15 marks
Consider the following two types in Haskell:
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
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.
Reference solution
data Staff
data Customer
data Supplier
newtype Person t = {- … -}
name :: Person t -> String
— Maybe no longer needed here: salary :: Person Staff -> String fire :: Person Staff -> IO ()
— Maybe no longer needed here: company :: Person Supplier -> String
Question 23 D.II 5 marks
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
9/14
02/08/2021 COMP3141 – Sample Exam
What is the difference between these types? In which circumstances would Vec be the better
COMP3141 – Sample Exam
Student Log out
choice, and in which List?
Question 24 D.II 5 marks
Here is a simple list function:
Define a new version of zip which operates on Vec instead of List wherever possible. You can constrain the lengths of the input.
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)
Reference solution
zipV :: Vec n a -> Vec n b -> Vec n (a, b)
zipV VNil ys = VNil
zipV xs VNil = VNil
zipV (VCons x xs) (VCons y ys) = VCons (x, y) (zipV xs ys)
Reference solution
Vec tracks its length in the type level, whereas List does not. Usually, one would only use Vec if one frequently needed to express static pre-conditions about the length of the list. This way, the type checker can ensure these preconditions are met automatically.
Question 25 D.II 5 marks
Here is another list function:
Define a new version of filter which operates on Vec instead of List wherever possible.
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
Reference solution
We can’t return a Vec because we don’t know how long it will be.
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
10/14
02/08/2021 COMP3141 – Sample Exam
g
COMP3141 – Sample Exam
| p x = Cons x (filterV p xs) | otherwise = filterV p xs
Student
filterV :: (a -> Bool) -> Vec n a -> List a filterV p VNil = Nil
filterV p (VCons x xs)
Log out
Part E
25 marks
Section E.I 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
Question 26 E.I 2 marks
Is the Maybe Applicative instance commutative? Explain your answer.
Reference solution
Yes. If either u or v are Nothing, the result is Nothing on both sides of the law. If both are not Nothing, then the result is f applied to their contents.
Question 27 E.I 3 marks
We have seen two different Applicative instances for lists. Which of these instances, if any, are commutative? Explain your answer.
Reference solution
The ZipList instance obeys the law above – the size is the minimum of the two input lists, and each element is combined with f in the same order.
The combinatorial instance does not. For example if u = [2,3] and v = [4,5] and f = (*), then the left hand side of the law is [8,10,12,15] and the right hand side gives us [8,12,10,15] – they are different.
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
11/14
02/08/2021 COMP3141 – Sample Exam
COMP3141 – Sample Exam
Student
E.I 5 marks
Question 28
Log out
Section E.II 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.
Question 29 E.II 2 marks
(A ∨ B) → (B ∨ A)
Reference solution
f :: Either A B -> Either B A f(Left x)=Rightx
f (Right x) = Left x
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.
Reference solution
do
x <- u y <- v pure (f x y) == do y <- v x <- u pure (f x y) Question 30 E.II 2 marks (A ∨ A) → A Reference solution https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions 12/14 02/08/2021 COMP3141 – Sample Exam COMP3141 – Sample Exam f :: (Either A A) -> A f(Left x)=x
f (Right x) = x
Student
Log out
Question 31 E.II 3 marks
(A ∧ (B ∨ C)) → ((A ∧ B) ∨ (A ∧ C))
Reference solution
f :: (A, (Either B C) -> (Either (A, B) (A, C)) f(a,Left x)=Left(a,x)
f (a, Right x) = Right (a, x)
Question 32 E.II 3 marks
¬((A → ⊥) ∨ A)
Reference solution
f :: (Either (A -> Void) A) -> Void
This function cannot be implemented in Haskell or simply-typed lambda calculus as it states the law of the excluded middle is false. While constructive logics do not admit the law of the excluded middle, they do not refute it either.
Question 33 E 5 marks
Here is a Haskell data type:
Using known type isomorphisms, simplify this type as much as possible.
data X
= First () A
| Second () Void
| Third (Either B ())
Reference solution
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
13/14
02/08/2021 COMP3141 – Sample Exam
This is equivalent to (using plus for Either and times for products):
COMP3141 – Sample Exam
Student
Log out
END OF SAMPLE EXAM
(don’t forget to save!)
(() * A) + (() * Void) + (B + ()) = A + (Void + (B + ()))
= A + (B + ())
= A + B + ()
= Maybe (Either A B)
https://web.cse.unsw.edu.au/~cs3141/cgi-bin/exa/exam/sample/solutions
14/14