Quiz (Week 5)

1. Functors
- 1.1. Question 1
- 1.2. Question 2
2. Question 3
3. The State type
- 3.1. Question 7
- 3.2. Question 8

1 Functors

1.1 Question 1

Which of the following type definitions admit law-abiding instances of Functor?

✔[]
✔(,) a for any a
✔(->) a for any a
✔Gen
✗Pow
✔Maybe
✗String

✔

Tree where:

data Tree a = Leaf | Branch a (Tree a) (Tree a)
data Pow a = Pow (a -> Void)
data Void -- has no constructors

Every one of these is a functor except for String and Pow. The former, String, is not even of unary kind and therefore cannot be made an instance of Functor in any way. The latter, Pow, does not admit a law-abiding instance of Functor, as should be apparent after a bit of trial and error: given a -> b, a -> Void and b, we cannot possibly create an element of type Void: the given functions do not help, and Void itself has no constructor. The others have the following implementations:

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]
  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)

1.2 Question 2

Here is a data type definition for a non-empty list in Haskell.

data NonEmptyList a = One a | Cons a (NonEmptyList a)

Which of the following are law-abiding Functor instances for NonEmptyList?

✔

instance Functor NonEmptyList where
  fmap f (One x) = One (f x)
  fmap f (Cons x xs) = Cons (f x) (fmap f xs)

✗

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)

Option 1 obeys the functor laws. Proof by induction of the first law (fmap id xs = xs): Base case, when xs = One x:

fmap id (One x) = One (id x)   -- Definition of fmap
                = One x        -- Definition of id
                = xs           -- as required.

Inductive case, assuming xs = Cons x xs', with the inductive hypothesis that fmap id xs' = xs':

fmap id (Cons x xs') = Cons (id x) (fmap id xs')  -- Definition of fmap
                     = Cons x (fmap id xs')       -- Definition of id
                     = Cons x xs'                 -- Inductive hypothesis
                     = xs                         -- as required.

As discussed in Lecture 5, this is sufficient to guarantee that the second law also holds.

Options 2 and 3 do not obey the first law, as fmap id (Cons 3 (One 1)) does not equal Cons 3 (One 1), and option 4 is not type correct as f :: a -> b, not a -> a.

2 Question 3

Which of the following C functions could be considered pure?

✔sqrt()
✗printf()
✗rand()
✗strcpy()

Computing a square root is pure, as the result depends solely on the input to the function. Indeed, the square root is a function in the mathematical sense and therefore is, by definition, pure.

The printf() function is not pure as it performs I/O, a type of effect.

The rand() function is not pure as each time it is evaluated it can return different results. That is, the results are not dependent solely on the input arguments.

The strcpy() function is impure as it mutates its arguments.

2.1 Question 4

Imagine we had a function multiplier that behaved as follows on the repl:

*> multiplier 1
1
*> multiplier 7
7
*> multiplier 10
70
*> multiplier 0
0
*> multiplier 7
0

Why is multiplier impure?

✗It performs I/O
✗It manipulates memory
✔It does not depend solely on its arguments

The function does not perform I/O, it does manipulate memory (but so do pure functions). The thing that makes it impure is that the expression multiplier x does not always return the same value for the same argument x. That is, it depends on some hidden local state in addition to its argument. Thus option 3 is the correct answer.

2.2 Question 5

Which of the following effects is considered an internal effect?

✗Modifying global variables
✗Drawing on the screen
✔Modifying local variables
✔Allocating a data structure
✗Throwing an exception

Modifying global variables can have a non-local influence on other parts of the program, therefore is not internal. Drawing on the screen similarly is not internal as its effect can clearly be observed from outside the function. Modifying local variables is internal as no other part of the program can observe the modification (neither can the user). Allocating data structures is also considered internal (under the common abstraction that we have infinite memory) as such an allocation also cannot be observed externally. Throwing an exception can be observed externally, however (by catching it), and thus is not an internal effect.

2.3 Question 6

What does the type State String Int signify?

✗A program/expression that may access and update a state of type String before eventually returning an Int
✗A function from String to a pair of String and Int.
✔Both of the above views are valid interpretations.

As discussed during the lecture, Haskell's State type is equivalent to

State s a =~ s -> (s, a)

even though internally the mtl library implements it differently.

3 The State type

Recall that in Haskell's mtl library, the State type of Control.Monad.State provides the following functions:

get :: State s s
put :: s -> State s ()
return :: a -> State s a
(>>=) :: State s a -> (a -> State s b) -> State s b
runState :: State s a -> s -> (a, s) 
evalState :: State s a -> s -> a

The following questions concern this type and this interface.

3.1 Question 7

Below is an example of a small program using State String. Our program will repeatedly pad a string with spaces until it reaches a certain length:

leftPad :: Int -> State String ()
leftPad l = while ((< l) . length) $
              get >>= \str ->
              put (' ':str)

What is the type of while in this example?

✗Bool -> State String () -> State String ()
✗State String Bool -> State String () -> State String ()
✗(Bool -> State String ()) -> State String ()
✗(String -> Bool) -> State String ()
✔(String -> Bool) -> State String () -> State String ()

The while loop takes a state-dependent conditional, i.e a function that returns a Bool for a given String, and a stateful action for the loop body, State String (), finally producing a stateful action that runs the loop, State String (), hence option 5 is correct.

3.2 Question 8

Here is a program to detect if a string has balanced parentheses, ignoring all other characters.

matching :: String -> Int -> Bool
matching []       n = (n == 0)
matching ('(':xs) n = matching xs (n+1)
matching (')':xs) n = n > 0 && matching xs (n-1)
matching (oth:xs) n = matching xs n

Which of the following is an accurate translation of the above program using the State type?

✗

matching xs = snd (runState (go xs) 0) == 0
  where
    go [] = return True
    go (x:xs) | x == '('  = modify (+1) >>= \_ -> go xs
              | x == ')'  = modify (-1) >>= \_ -> go xs
              | otherwise = go xs

✗

matching xs = snd (runState (go xs) 0) == 0
  where
    go [] = return True
    go (x:xs) | x == '('  = modify (+1) >>= \_ -> go xs
              | x == ')'  = get >>= \n ->
                               if n > 0 then put (n - 1) >>= \_ -> go xs
                                        else return False
              | otherwise = go xs

✗

matching xs = fst (runState (go xs) 0)
  where
    go [] = return True
    go (x:xs) | x == '('  = modify (+1) >> go xs
              | x == ')'  = get >>= \n ->
                               if n > 0 then put (n - 1) >>= \_ -> go xs
                                        else return False
              | otherwise = go xs

✗

matching xs = let (b,n) = runState (go xs) 0
               in b && n == 0
  where
    go [] = return True
    go (x:xs) | x == '('  = modify (+1) >>= \_ -> go xs
              | x == ')'  = modify (-1) >>= \_ -> go xs
              | otherwise = go xs

✔

matching xs = fst (runState (go xs) 0)
  where
    go [] = get >>= return . (== 0)
    go (x:xs) | x == '('  = modify (+1) >>= \_ -> go xs
              | x == ')'  = get >>= \n ->
                               if n > 0 then put (n - 1) >>= \_ -> go xs
                                        else return False
              | otherwise = go xs

Option 1 checks if the final count is zero, but does not check if the count sinks below zero at any point, matching the strings )( for example. Option 2 does check if the count drops below zero, but then doesn't do anything with that information. Option 3 only checks if the count drops below zero, and not that the count is zero at the end. Option 4 does check both the boolean and the count at the end, however does not set the boolean to false when the count drops below zero. Option 5 does all the required checks and is therefore correct.

Submission is already closed for this quiz. You can click here to check your submission (if any).