12/08/2020 Quiz (Week 2)
Quiz (Week 2) Types and Constructors
Consider the following type de nitions.
Question 1
Which of the following can identi ers can stand for types in the above de nitions? Check all that apply.
1. ✗ 2. ✔ 3. ✗ 4. ✔ 5. ✔ Y
Question 2
Which of the following identi ers can stand for constructors in the above de nitions? Check all that apply.
1. ✔ 2. ✔ 3. ✔ 4. ✗ 5. ✔ Y
type B = Bool data X = A X |BB |CY
newtype Y = Y B
A
B
C
X
Thethreetypesde nedare B, X,and Y.
A
B
C
X
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
1/8
12/08/2020 Quiz (Week 2)
Types in Design
For each of the following use cases, choose the type de nitions that best re ect this use case, eliminating as many possible errors or invalid values as possible.
Question 3
A connection is in one of three states: connected, connecting or disconnected. It also contains the following information:
● The destination IP address
● If it is in the disconnected state, the time it disconnected.
● If it is in the connected state, the arrival time of the most recent packet,
if one exists.
● If it is in the connected state, the size of the most recent packet, if one
exists.
● If it is in the connecting state, the time the connection was initiated.
1. ✗
data State = Connected | Connecting | Disconnected
data Connection
= Connection
{ destination :: IPAddress
, state :: State
, timeDisconnected :: Maybe Time
, timeInitiated
, packetArrival
, packetSize
}
:: Maybe Time
:: Maybe Time
:: Maybe Size
2. ✗
The type X introduces three constructors, A , B and C , and the newtype de nition de nes a constructor Y .
data State
= Connected { packetArrival :: Maybe Time
, packetSize :: Maybe Size
}
| Connecting { timeInitiated :: Time }
| Disconnected { timeDisconnected :: Time }
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
2/8
12/08/2020 Quiz (Week 2)
3. ✗
data State = Connected | Connecting | Disconnected
data Connection
= Connection
{ destination :: IPAddress
, state :: State
, timeDisconnected :: Maybe Time
, timeInitiated :: Maybe Time
, recentPacket :: Maybe (Time, Size)
}
4. ✔
data State
= Connected { recentPacket :: Maybe (Time, Size) }
| Connecting { timeInitiated :: Time }
| Disconnected { timeDisconnected :: Time }
data Connection
= Connection
{ destination :: IPAddress
, state :: State
}
The rst answer is very unstructured, as it does not enforce the relationship between the state the connection is in and the data that should be present in the connection. For example, this means that it’s possible to have a connection in the disconnected state, but without a timestamp. It also allows a packet arrival time to be present without a size, which is not possible.
The second answer does enforce the relationship between data and state, but does not x the problem with the packet size and time.
The third answer does x the problem with the packet size and time, but does not x the relationship between data and state.
The fourth answer is therefore correct.
data Connection
= Connection
{ destination :: IPAddress
, state :: State
}
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
3/8
12/08/2020 Quiz (Week 2)
Question 4
A message is encrypted using a password. The system will not allow messages to be encrypted with weak passwords. Messages can only be logged if encrypted.
1. ✗
2. ✗
3. ✔
4. ✗
checkStrength :: String -> Bool
encrypt :: String -> String -> String
log :: String -> Log -> Log
newtype Encrypted = E String
checkStrength :: String -> Bool
encrypt :: String -> String -> Encrypted
log :: Encrypted -> Log -> Log
newtype Password = P String
newtype Encrypted = E String
checkStrength :: String -> Maybe Password
encrypt :: String -> Password -> Encrypted
log :: Encrypted -> Log -> Log
newtype Password = P String
checkStrength :: String -> Maybe Password
encrypt :: String -> Password -> String
log :: String -> Log -> Log
There are three requirements:
1. We must prevent the password and message parameters to encrypt from being swapped.
2. We must not allow an unchecked password to be used for encryption. 3. We must not allow unencrypted messages to be logged.
The rst answer doesn’t meet any requirements. The second meets the third requirement only. The third is correct. The last one meets only the rst and second requirements.
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
4/8
12/08/2020 Quiz (Week 2)
Monoids and Semigroups Question 5
Which of the following Semigroup instances are lawful? 1. ✗
2. ✔
3. ✔
4. ✔
The only operation that is not associative is the rst one (implication)
newtype X = X Bool
instance Semigroup X where
X a <> X b = X (not a || b)
newtype X = X Bool
instance Semigroup X where
X a <> X b = X (a || b)
newtype X = X Bool
instance Semigroup X where
X a <> X b = X (a `xor` b)
where xor True x = not x
xor False x = x
newtype X = X Bool
instance Semigroup X where
X a <> X b = X a
Question 6
Which of the following is a valid monoid?
1. ✗ The type
2. ✗ The type
3. ✔ The type
4. ✗ The type Integer , the function
, the max function and identity element , the function and identity element
, the function and identity element
element 0 .
Integer
Bool
(&&)
False
Bool
(&&)
True
0
, and identity
(\a b -> (a + b) `div` 2)
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
5/8
12/08/2020 Quiz (Week 2)
Relations Question 7
Check all of the following that are valid equivalence relations.
1. ✔
2. ✔
3. ✗
4. ✗ (/=)
Question 8
Here is a data type de nition for a non-empty list in Haskell.
Which of the following are law-abiding Functor instances for NonEmptyList ? 1. ✔
(==)
\x y -> x `mod` 10 == y `mod` 10
(>=)
Equality is an equivalence relation, as is congruence mod 10. That is because they satisfy re exivity, transitivity and symmetry. The ordering >= is not symmetric, and inequality is not re exive or transitive either.
data NonEmptyList a = One a | Cons a (NonEmptyList a)
instance Functor NonEmptyList where
fmap f (One x) = One (f x)
fmap f (Cons x xs) = Cons (f x) (fmap f xs)
2. ✗
The rst answer is not a monoid because 0 is not an identity element for max . For example max (-1) 0 == 0 .
The second answer is not a monoid because False is not an identity element for (&&),as a&&False==False forall a.
The third answer is a monoid, as (&&) is associative and True is its identity. The last is not a monoid, because the given average function is not associative.
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
6/8
instance Functor NonEmptyList where
fmap f (One x) = One (f x)
fmap f (Cons x xs) = One (f x)
instance Functor NonEmptyList where
fmap f (One x) = One (f x)
fmap f (Cons x xs) = Cons (f x) (Cons (f x) (fmap f xs))
instance Functor NonEmptyList where
fmap f (One x) = One (f x)
fmap f (Cons x xs) = Cons (f (f x)) (fmap f xs)
fmap id xs =
xs
xs = One x
fmap id (One x) = One (id x)
= One x
= xs
— Definition of fmap — Definition of id — as required.
fmap id xs’ = xs’
xs = Cons x xs’
fmap f (fmap g xs) = fmap (f . g) xs
a ->
Cons 3 (One 1)
fmap id (Cons 3 (One 1))
f :: a -> b
a
Submission is already closed for this quiz. You can click here to check your submission (if any).
12/08/2020 Quiz (Week 2)
3. ✗
4. ✗
Option 1 obeys the functor laws. Proof by induction of the rst law (
): Base case, when :
Inductive case, assuming :
, with the inductive hypothesis that
fmap id (Cons x xs’) = Cons (id x) (fmap id xs’) — Definition of fmap
The composition law (
parametricity. parametricity
= Cons x (fmap id xs’)
= Cons x xs’
= xs
— Definition of id
— Inductive hypothesis — as required.
) follows from
does not , not
Options 2 and 3 do not obey the rst law, as
equal , and option 4 is not type correct as
.
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
7/8
12/08/2020 Quiz (Week 2)
www.cse.unsw.edu.au/~cs3141/20T2/Week 02/quiz.html
8/8