12/08/2020 Quiz (Week 7)
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
1/8
Quiz (Week 7)
Functors Question 1
Which of the following type de nitions admit law-abiding instances of Functor ?
1. ✔ 2. ✗ 3.✔ 4.✔ 5. ✔ 6. ✔ 7. ✔
for any for any
Maybe
String
(->) a
a
(,) a
a
IO
[]
8. ✔
Gen
Tree where:
data Tree a = Leaf | Branch a (Tree a) (Tree a)
Every one of these is a functor except for String , which is not a type constructor and therefore cannot be a Functor . IO is an abstract type that implements
, as is . The others have the following implementations:
Functor
Gen
instance Functor Maybe where
fmap :: (a -> b) -> Maybe a -> Maybe b
fmap f (Just x) = Just (f x)
fmap f Nothing = Nothing
instance Functor ((->) x) where
fmap :: (a -> b) -> (x -> a) -> (x -> b)
fmap ab xa x = ab (xa x)
instance Functor ((,) x) where
fmap :: (a -> b) -> (x, a) -> (x, b)
fmap f (x, a) = (x, f x)
instance Functor [ ] where
fmap :: (a -> b) -> [a] -> [b]
12/08/
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html 2/8
2020 Quiz (Week 7)
Question 2
Here is a data type de nition for a rose tree in Haskell.
Which of the following are law-abiding Functor instances for Rose ? 1. ✗
2. ✔
3. ✗
4. ✗
Option 1 does not type check. Options 3 and 4 don’t obey the functor laws.
Applicatives Question 3
data Rose a = Node a [Rose a]
instance Functor Rose where
fmap f (Node x xs) = Node (f x) (fmap f xs)
instance Functor Rose where
fmap f (Node x xs) = Node (f x) (fmap (fmap f) xs)
instance Functor Rose where
fmap f (Node x xs) = Node (f x) [f x]
instance Functor Rose where
fmap f (Node x xs) = Node (fmap x) (fmap f (head xs))
fmap = map
instance Functor Tree where
fmap :: (a -> b) -> Tree a -> Tree b
fmap f Leaf = Leaf
fmap f (Branch x l r) = Branch (f x) (fmap f l) (fmap f r)
12/08/2020 Quiz (Week 7)
Which of the following type de nitions are examples of ?
1. ✔ 2. ✗ 3.✔ 4.✗ 5. ✔ 6. ✔ 7. ✔
for any for any
Gen
Maybe
String
(->) a
IO
a
(,) a
a
[]
Once again, is not a type constructor, so cannot be an Applicative . Furthermore does not admit a law-abiding applicative instance either, as we cannot implement :
Of the other options, Gen and IO are both applicatives, as are Maybe , (->) a and as follows:
String
(,) a
pure
instance Applicative ((,) x) where
pure :: a -> (x, a)
pure a = (??? , a)
[]
instance Applicative Maybe where
pure x = Just x
Just f <*> Just x = Just (f x)
_ <*> _ = Nothing
instance Applicative ((->) x) where
pure a = \x -> a
(xf <*> xa) x = xf x (xa x)
instance Applicative [ ] where
pure a = [ a ]
[] <*> ys = []
(f:fs) <*> xs = map f xs ++ (fs <*> xs)
Question 4
Here is a data type de nition for a non-empty list in Haskell.
data NonEmptyList a = One a | Cons a (NonEmptyList a)
Applicative
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
3/8
12/08/2020 Quiz (Week 7)
Which of the following are law-abiding instances for ? 1. ✔
instance Applicative NonEmptyList where
pure x = Cons x (pure x)
(One f) <*> (One x) = One (f x)
(One f) <*> (Cons x _) = One (f x)
(Cons f _) <*> (One x) = One (f x)
(Cons f fs) <*> (Cons x xs) = Cons (f x) (fs <*> xs)
2. ✗
instance Applicative NonEmptyList where
pure x = One x
(One f) <*> (One x) = One (f x)
(One f) <*> (Cons x _) = One (f x)
(Cons f _) <*> (One x) = One (f x)
(Cons f fs) <*> (Cons x xs) = Cons (f x) (fs <*> xs)
3. ✔
Applicative
NonEmptyList
instance Applicative NonEmptyList where
pure x = One x
One f <*> xs = fmap f xs
(Cons f fs) <*> xs = fmap f xs `append` (fs <*> xs)
where
append (One x) ys = Cons x ys
append (Cons x xs) ys = Cons x (xs `append` ys)
4. ✗
instance Applicative NonEmptyList where
pure x = Cons x (pure x)
One f <*> xs = fmap f xs
(Cons f fs) <*> xs = fmap f xs `append` (fs <*> xs)
where
append (One x) ys = Cons x ys
append (Cons x xs) ys = Cons x (xs `append` ys)
Option 3 is analogous to the same Applicative instance we knows from regular
lists, so is a valid Applicative law,
instance, analogous to the library.
instance. Options 2 and 4 don’t obey the rst . Option 1 is also a valid applicative
instance available in the Haskell standard
Applicative
pure id <*> v = v
ZipList
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
4/8
12/08/2020 Quiz (Week 7)
Question 5
Suppose I wanted to write a function pair , which takes two Applicative data structures and combines them in a tuple, of type:
Select all correct implementations of pair . 1. ✗
2. ✗
3. ✔
4. ✔
5. ✗ There is no way to implement this function.
Monads Question 6
Which of the following type de nitions are examples of Monad , or admit law-abiding Monad instances?
1. ✔
2. ✗
3. ✔ (->) a for any a
pair :: (Applicative f) => f a -> f b -> f (a, b)
pair fa fb = pure fa <*> pure fb
pair fa fb = pure (,) <*> pure fa <*> pure fb
pair fa fb = pure (,) <*> fa <*> fb
pair fa fb = fmap (,) fa <*> fb
Options 1 and 2 are not type correct.
Options 3 and 4 are both correct, and equivalent, as fmap f x = (pure f <*> x) , if the Applicative and Functor instances are law-abiding.
Maybe
String
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
5/8
12/08/2020 Quiz (Week 7)
4.✗ for any 5. ✔
6. ✔
7. ✔
8. ✗
Tree where:
(,) a
IO
[]
Gen
a
data Tree a = Leaf | Branch a (Tree a) (Tree a)
Monad instances can be written for ,
are abstract types that also implement
(straightforward) instance of , as we would have to somehow transform a
Tree (Tree a) into a in a structure-preserving way, which I’m pretty sure is impossible.
Maybe
(->) a
. The
and , and IO and Gen type is not a
[]
Monad
Monad
Tree
Tree a
instance Monad Maybe where
Just x >>= f = f x
Nothing >>= f = Nothing
instance Monad ((->) x) where
(xa >>= axb) = \x -> axb (xa x) x
instance Monad [ ] where
xs >>= each = concatMap each xs
Question 7
We wish to write a function
unpack each given value of type m a and collect their results into a list. Which of the following is a correct implementation of this function?
1. ✗
s of type
[m a] -> m [a] , for any monad
m . It will
s :: Monad m => [m a] -> m [a]
s [] = []
s (a:as) = do
x <- a
xs <- s as
pure (x : xs)
2. ✗
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
6/8
12/08/2020 Quiz (Week 7)
3. ✔
s :: Monad m => [m a] -> m [a]
s [] = return []
s (a:as) = do
x <- a
xs <- s as
pure (x : xs)
4. ✗
s :: Monad m => [m a] -> m [a]
s [] = return []
s (a:as) = do
a
s as
pure (a : as)
Only answer 3 is type correct.
Question 8
Now suppose we wish to write a function m of type, which applies a given function to each element of a list and collects the results:
What is a correct implementation of m ? 1. ✗
m :: Monad m => (a -> m b) -> [a] -> m [b]
s :: Monad m => [m a] -> m [a]
s [] = return []
s (a:as) = do
x <- a
xs <- as
pure (x : xs)
m :: Monad m => (a -> m b) -> [a] -> m [b]
m f [] = []
m f (x:xs) = do
y <- f x
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
7/8
12/08/2020 Quiz (Week 7)
2. ✗
m :: Monad m => (a -> m b) -> [a] -> m [b]
m f [] = []
m f (x:xs) = do
y <- f x
ys <- f xs
return (y:ys)
3. ✔
4. ✗
m :: Monad m => (a -> m b) -> [a] -> m [b]
m f = s . map f
m :: Monad m => (a -> m b) -> [a] -> m [b]
m = s . map
Only answer 3 is type correct.
Submission is already closed for this quiz. You can click here to check your submission (if any).
ys <- m f xs
return (y:ys)
www.cse.unsw.edu.au/~cs3141/20T2/Week 07/quiz.html
8/8