FP 2022 Past Paper

Question 1: Maps (Dictionaries) and Types

1a)

Question

What is the role of ⇒, i.e. the ‘fat arrow’ notation, in a Haskell type? Explain using a simple example if necessary.

Answer

It is a typeclass (0.5 mark) constraint (0.5 mark). It expresses some behavioural constraint on the relevant polymorphic type variable (1 mark). For example, Eq a => a -> a means that the type denoted by a must be an instance of the Eq typeclass (1 mark).

1b)

Abstract

(b) Consider using a list of (key, value) pairs in Haskell to represent an associative data structure, like a Python dictionary. Given generic type variables k for the key type and v for the value type, a potential type for the lookup function is given below: lookup :: [(k,v)] -> k -> Maybe v

(i) Which constraint should we add to the lookup function type, and why?

Answer

Answer: To allow key comparisons (1 mark) we would prepend typeclass constraint Eq k => (1 mark) to the type. Also accept Ord for comparisons.

(ii) Why is the return type for the lookup function wrapped up as a Maybe value?

Answer

• We may lookup a key that is not present in the list of pairs
• The Maybe a type extends the set of possible values by one more than the original set of values in a.
• The appropriate value to return for missing keys is Nothing, which indicates the absence of a value

(iii) Write a Haskell definition for the lookup function using the function type you defined in part (i) above and using a higher-order list processing function.

Answer

lookup :: Eq k => [(k,v)] -> k -> Maybe v
lookup l k =
  let res = filter (\(k', _) -> k == k') l
  in 
  	if null res then 
  		Nothing
  	else  
  		Just $ snd (head res)

(Accept alternative solutions with fold but with a lower mark)

1c)

Question

Why might a list of tuples be an inappropriate representation for an associative data structure like a dictionary?

Answer

• Linear search time in size of dictionary
• Other operations likely to be O(n) too.
• No constraints to prevent repeat keys stored with diff values
• Accept other reasonable answers.

1d)

Question

How would you define a type alias in Haskell for the [(k,v)] data structure when it is used to implement a dictionary?

Answer

type Dictionary k v = [(k,v)]

Question 2: Algebraic Datatypes and Type Inference

Abstract

Given the following type and expression:

tree1 :: (Int,[a])
tree1 = (0,[(1,[]),(2,[(3,[])]),(4,[(5,[(6,[])])])])

(i) Type checking this code gives a type error. What is the reason for the type error?

Answer

The type variable ‘a’ can only be bound to one concrete type. The types of [],[(3,[])],[(5,[(6,[])])] are not the same.

(ii) Create an algebraic datatype Tree1 with constructor T1 such that, when applying the type constructor T1 to the expression bound to tree1, tree1 is of type Tree1. You can assume that the integers are of type Int. The type Tree1 is not polymorphic.

data Tree1 = T1 (Int, [( Int , [(Int, [(Int, [Int] )] )] )] )

Answer

data Tree1 = T1 (Int,[(Int,[(Int,[(Int,[Int])])])])

(iii) Write an expression res = ... that computes the sum of all values stored in tree1.

Answer

res = let (v0,[(v1,[]),(v2,[(v3,[])]),(v4,[(v5,[(v6,[])])])]) = tree1 in v0+v1+v2+v3+v4+v5+v6

res = let (v0,[(v1,[]),(v2,[(v3,[])]),(v4,[(v5,[(v6,[])])])]) = tree1 in 
		v0+v1+v2+v3+v4+v5+v6

(iv) What does res evaluate to?

Answer

21

(v) What is the type of res?

Answer

Int

2b)

(b) Given the following code:

makeTree0 = foldl' (\acc elt -> (elt,[acc])) (0,[]) [1 .. ]

(i) What is the type-level problem with this code?

Answer

The initial accumulator is of type (Int,[t]). The folding function function must have type b -> a -> b which is (Int,[t])-> Int -> (Int,[t]). However, its return type is (a,[b]) which is (Int,[(Int,[t])).

(ii) Propose a recursive, non-polymorphic algebraic datatype Tree2 with constructor T2 such that the following code is correct:

makeTree1 = foldl' (\acc elt -> T2 (elt,[acc])) (T2 (0,[])) [1 .. ]

Answer

data Tree2 = T2 (Int,[Tree2])

(iii) What happens when you print makeTree1 and why?

Answer

It hangs because we attempt to strictly left-fold an infinite list and constructing that list never finishes.

Suppose we modify the code to use foldr:

makeTree2 = foldr (\acc elt -> T2 (elt,[acc])) (T2 (0,[])) [1 .. ]

(iv) What is wrong with this code?

Answer

Arguments acc and elt need to be swapped

(v) Provide the correct code for makeTree2 (i.e. the minimal change to the expression to fix the type error, while still using foldr)

Answer

makeTree2 = foldr (\elt acc -> T2 (elt,[acc])) (T2 (0,[])) [1 .. ]

(vi) What happens when you print makeTree2 and why?

Answer

It prints forever because of the lazy evaluation of the foldr and because each iteration applies f to the next value and the result of the fold on the rest of the list. So on every iteration, the type constructor and the integer value are known and will be printed; the content of the list is iteratively printed.

Question 3: Monads

3a)

Abstract

A monad consists of a type m a, the functions return and bind (also written >>=), and the optional >> operator. Given the following type:

data This a = This a

(i) Complete the implementation of return.

return = ...

Answer

return = This

(ii) Complete the implementation of >>=.

(>>=) (This x) f = ...

Answer

(>>=) (This x) f = f x

(iii) With the given implementation of >>=, and assuming the definition for f is:

f = This . id

What is the type of f?

f :: a -> ...

Answer

f :: a -> This a

3b)

Abstract

(b) A monad must also satisfy the three monad laws. Assume return and >>= are defined as above.

(i) Complete the expression so that the 1st monad law (left identity) holds:

\x -> (This x >>= return) ≡ ...

Answer

\x -> (This x >>= return) ≡ This x

(ii) Complete the expression so that the 2nd monad law (right identity) holds:

return x >>= ... ≡ This x

Answer

return x >>= This ≡ This x

(iii) Complete the expression so that the 3rd monad law (associativity) holds:

(This x >>= This) >>= This ≡ ... >>= (\x ... This x ... This)

Answer

(This x >>= This) >>= This ≡ This x >>= (\x -> This x >>= This)

3c)

Given following type:

data CouldBe a = Really a | Only a | None

(i) Complete the implementations of return and >>= so that the three monad laws are satisfied.

return = ...
None >>= f = ...
(Really ...) >>= f = ... x
(... x) >>= f ... f x

This is a drag and drop question with possible answers from [CouldBe, Really, Only, None, f, x, a, =, >>= ]

Answer

return = Really
None >>= f = None
(Really x) >>= f = f x
(Only x) >>= f = f x

(ii) Explain your reasoning

Answer

CouldBe is a straightforward generalisation of Maybe, which is a monad. The only difference is the definition of (>>=) which has an additional case.

3d)

Abstract

Given following code which defines a type UMaybe and makes it an instance of the Monad typeclass with the given definitions of return and >>=. We define a function uLookup which takes a string and returns values of type UMaybe. In the function uCheck we use do-notation to combine calls to this function.

data UMaybe a = UJust a | UUnknown | UNothing deriving Show
instance Monad UMaybe where
  return = UJust
  (>>=) UNothing f = UNothing
  (>>=) UUnknown f = UUnknown
  (>>=) (UJust x) f = f x
 
uLookup :: String -> UMaybe Int
uLookup "1" = UJust 2
uLookup "2" = UUnknown
uLookup "3" = UJust 4
uLookup "4" = UJust 5
uLookup _ = UNothing
 
uCheck v0 = do
  v1 <- uLookup v0
  v2 <- uLookup (show v1)
  v3 <- uLookup (show v2)
  return (v1,v2,v3)
 
main :: IO ()
main = print $ uCheck "1"

(i) What is the value of v1?

Answer

v1 = 2

(ii) What is the return value of uLookup (show v1)?

Answer

uLookup (show v1) = UUnknown

(iii) What is the return value of uCheck "1"?

Answer

`uCheck “1” = UUnknown¦

(iv) What is the type of uCheck?

Answer

uCheck :: String -> UMaybe (Int,Int,Int)

(v) Explain your answers to (i) .. (iv)

Answer

Because v0 is “1”, uLookup returns 2, so v1 = 2.

uLookup (show v1) = uLookup "2" = Unknown

Because of the definition of bind, UUnknown will be passed through to the end of the computation. So uCheck “1” returns UUnknown.

The final return desugars to UUnknown >>= \v3 -> return (v1,v2,v3) and so the final result is also UUnknown.

The return type of uCheck is UMaybe (Int,Int,Int): if all calls to uLookup would succeed, v1, v2 and v3 would be Int.