FP 2020 Past Paper

Question 1: Higher-Order Functions

1a)

Question

What are higher-order functions and why are they so common in Haskell?

Answer

A higher-order function takes other functions as parameters (0.5 mark) and/or returns other functions as results (0.5 mark). Higher-order functions are a natural consequence of the functional programming paradigm (0.5 mark) in which functions are first-class citizens (0.5 mark), i.e., functions are values (0.5 mark).

1b)

Question

Give the type signature and an explanation of the behaviour of the foldr higher-order function on lists.

Answer

foldr :: (a -> b -> b) -> b -> [a] -> b

The foldr function takes a binary operation, an initial value, and a list. It applies the binary operation to each element of the list and the result of folding the rest of the list, starting from the right with the initial value.

1c)

Question

Define a Haskell function twice :: (a->a)-> a -> a which applies the function (supplied as first parameter) two times to the subsequent parameter value. For instance, twice (+1) 0 would evaluate to 2.

Answer

twice f x = f (f x)

1d)

Question

Now consider how to generalize the function twice to a function ntimes, which repeatedly applies a function (supplied as a parameter) multiple times. The type signature is: ntimes :: (a->a) -> Int -> a -> a. For example, ntimes (+2) 5 0 evaluates to 10 and ntimes tail 3 [1..4] evaluates to [4]. Write a Haskell definition for this ntimes function. You may assume the supplied integer value is non-negative. If the integer value is 0 then the behaviour is same as the identity function.

Answer

-- base case, identity function
ntimes f 0 x = x
-- recursive case
ntimes f n x = ntimes f (n-1) (f x)

ntimes :: (a->a) -> Int -> a -> a
ntimes f 0 x = x 
ntimes f n x = ntimes f (n-1) (f x)

1e)

Question

Study the blowup function definition below. What happens if we evaluate blowup 42 at the GHCi interactive prompt, and why?

blowup :: Integer -> Integer
blowup n = n + blowup $ n+1

Answer

• The evaluation does not terminate (1 mark)
• It causes infinite recursion - no base case (1 mark)
• Eventually we get a stack/heap overflow error due to recursion, memory exhaustion (1 mark)

1f)

Question

Now suppose we evaluate ntimes blowup 0 42 at the GHCi interactive prompt. Explain why this evaluation terminates immediately with the result 42.

Answer

• ntimes with 0 value is the identity function (1 mark)
• the higher order function ntimes never needs to apply the blowup function to anything - it stays unevaluated (1 mark)
• there is no recursion involved - simple rewrite / base case (1 mark)

Question 2: Maps (Dictionaries) and Types

2a)

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

2b)

Question

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

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, ideally using the function type you defined in part (i) above.

Answer

lookup :: Eq k => [(k,v)] -> k -> Maybe v
lookup [] x = Nothing
lookup ((x,val):rest) y =
  if x == y
  then Just val
  else lookup rest y

(Accept alternative solutions with pattern matching etc)

lookup :: Eq k => [(k,v)] -> k -> Maybe v
lookup myList key =
	if res then Just $ snd $ head res
	else Nothing
	where 
		res = filter (\(k, _) -> k == key) myList
 

2c)

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.

2d)

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 3: Monads

3a)

Question

Give the precise type for the bind function (>>=) in the Comp monad.

Answer

(>>=):: (Comp a)-> (a -> Comp b)-> (Comp b)

1 mark for each subtype in brackets (x3), and 1 mark for correct ‘shape’ with function arrows. Only 1 mark overall for the general bind type (in terms of Monad m rather than Comp).

3b)

Abstract

Suppose you are given two functions: primes :: Int -> Int and fibs :: Int -> Int which compute the nth prime number and nth fibonacci number respectively. These are compute-intensive, long-running functions for large values of n.

(i) Imagine a function funnysum which takes an Int value n then computes the sum of the nth prime and the nth Fibonacci number, returning this sum value in the Comp monad. What is the type signature of the funnysum function?

Answer

funnysum :: Int -> Comp Int

(ii) Write a Haskell definition for the funnysum function using a single do block.

Answer

funnysum n = do
  let a = primes n
  let b = fibs n
  return (a+b)

(iii) How would you map the funnysum function over a list of integers to generate a corresponding list of funnysum result values? Further, what is the type of your result list?

Answer

Several alternatives possible:

• map funnysum gives [Comp Int].
• mapM funnysum gives Comp [Int].
• Either of the above with the appropriately sequenced runComp call(s) gives [Int].

(iv) Suppose we have an Int value in the IO Monad, perhaps the result of user input. How would we provide this IO Int value as input to the funnysum function? You may answer with Haskell source code and/or a general description of your approach.

Answer

• funnysum takes Int but we have IO Int
• we would need to be in IO Monad, e.g. in a do block, when we call funnysum
• multiple monads - we end up in IO (Comp Int) or similar
• perhaps use a monad transformer stack? Would need an CompT transformer to be defined

3c)

Question

Discuss possible motivations for using the Comp monad.

Answer

We might use Comp for long-running computations, perhaps executing them in parallel on different threads. This is like Futures or Promises in other languages.

Comp allows ordering of computations, controlled sequencing. It is precisely a ‘strict identity monad’.