Quartz 4

Functional Programming Past Paper Portal

7 min read

Individual Papers:

FP Uncovered Topic Questions FP Replica Papers

2017:

FP 2017 Past Paper

Question 1: Expressions and Function Evaluation

1a)

For each of the following Haskell expressions, write down the result of evaluation.

[]

[[],[],[]] — more tricky than previous case! Don’t accept single empty list here.

[('a','a'), ('b','b'), ('c', 'c')] — i.e. a list of (Char,Char) pairs

(v) let f = \x->x in f (f 1, f 'a')

(1,a) — since f is polymorphic, and late-bound, although students don’t need to state this explicitly.

1b)

(i) foldl (+)0 [1,2,3]

(ii) foldr (+)0 [1,2,3]

1c)

Question

Consider a function op :: Int->Int->Int. What property must the op function have, so the results of foldl op and foldr op are equal?

1d)

Question

(d) Consider function concat :: [[a]] -> [a] which takes a list of lists of elements and returns a list of elements. For instance, concat [[1], [2], [3,4,5]] evaluates to [1,2,3,4,5] and concat ["hello", "world"] evaluates to `“helloworld”. Write a recursive definition for the concat function that uses pattern matching on the list data structure.

1e)

Question

(e) Write a point-free definition for the concat function.

Question 2: Monads and Pirate Ships

2a)

Question

What is the type of the monadic bind operator (>>=) in Haskell?

Monad m ⇒m a → (a → m b)→ m b — 1 mark for type constraint, then 1 for each value type

2b)

Study the following type declarations.

type Treasure = Int — count num. treasure chests data PirateShip = PirateShip Treasure — e.g. (PirateShip 2) is ship with two treasure chests


Suppose that a PirateShip can carry a maximum cargo of three treasure chests, without sinking. We want to define a function called addTreasure, which takes a PirateShip parameter and evaluates to a Maybe PirateShip result. If a PirateShip value x currently has fewer than three treasure chests, then addTreasure x evaluates to a PirateShip with one more treasure chest, wrapped in a Just instance. However if the input parameter x already has the maximum three treasure chests, then addTreasure x evaluates to Nothing which denotes that the ship has sunk.

Question 3: Binary Trees and Twistable Typeclasses

3a)

Abstract

Here is a definition of a binary tree datatype in Haskell.

data Tree a = Leaf | Node a (Tree a) (Tree a)

Question

Write a function countNodes :: Tree a -> Int that returns the number of Nodes in a binary tree. For instance, countNodes (Node 1 Leaf (Node 1 Leaf Leaf)) evaluates to 2.

3b)

Question

Write a function mirror :: Tree a -> Tree a that returns the mirror image of a binary tree.

3c)

Abstract

Here is a definition of a typeclass in Haskell. We will use this typeclass to characterize finite data structures that we can reverse, in some sense.

class Twistable t where twist :: t→t size :: t→Int

is an instance of the Twistable typeclass.

(iii) Here are the properties that twist must satisfy:

  1. If the data to be twisted has size 0, then the twisted data has the same value as the original data.
  2. The twisted data always has the same size as the original data.
  3. Twist applied twice (i.e. twist (twist x) ) is equal to the identity function. Now express these three properties as quickcheck specifications for arbitrary lists [a], with appropriate type signatures.
Link to original

2018:

FP 2018 Past Paper

Question 1: Expressions and Function Evaluation

1a)

Given this Haskell function definition: 

f :: Int->Int
f x = 2*x

determine the values of the following expressions.

1b)

Assume that f has type Int->[Int], g has polymorphic type a->a, and h has polymorphic type [a]->a. Determine the types of the following expressions.

1c)

Given the integer exponentiation operator ^, i.e. x^y evaluates x raised to the power y, then calculate the values of the following expressions.

1d)

Question 2: Dragons and Type Classes

Examine the following Haskell definitions, which are relevant for this question.

data Dragon a = LiveDragon [a] | DeadDragon — list of a’s is record of food items eaten by dragon class Food f where poisonous :: f → Bool — True means it’s bad to eat

2a)

Question

Define a function eats :: Food a => Dragon a -> a -> Dragon a which, if the first parameter is a LiveDragon, checks whether the second parameter (the food) is poisonous—if it is, then the result is a DeadDragon. > If the food is not poisonous, then the result is a LiveDragon, with the food parameter value appended to the end of the LiveDragon’s list of food. On the other hand, if the first parameter is a DeadDragon, then the result should also be a DeadDragon, whatever food is supplied as the second parameter.

2b)

Question

Declare the Int data type to be an instance of the Food type class. The only poisonous integer value is 13.

2c)

What code should be added to enable a Dragon to eat other Dragons? Assume a LiveDragon may eat a LiveDragon, but if a LiveDragon tries to eat a DeadDragon, it's poisonous, so the LiveDragon itself will become a DeadDragon.

2d)

Question

Given your definition in part (c), is it possible for a Dragon to eat itself? Would this be a sensible feature, in general?

2e)

Question

What is the motivation for the Functor type class?

2f)

Question

Explain, using appropriate source code snippets, how to make the Dragon type an instance of the Functor type class.

Question 3: Safety, Registration, and Types

3a)

Abstract

head and tail are two well-known list functions defined in Haskell’s Prelude. Their type signatures are as follows:

head :: [a] → a tail :: [a] → [a]

3b)

Abstract

You have been given a vague specification: The Republic of Ruritania is migrating its car number plate format from a sequence of five alphanumeric digits to an encoding based on: a) the locality of registration, that is the state and district the car was registered in; b) year and month of registration; and finally c) a random sequence of three alphanumeric digits. Ruritania has five states, North, South, East, West, and Capital with short codes of: N, S, E, W, and C.

Within each state there are twenty districts each known by its number. You can assume that alphanumeric digits are digits that are either numbers in the range zero to nine, or uppercase characters from the English alphabet.

(i) Write some Haskell code to represent both registration formats as a single algebraic data structure called CarReg.

3c)

Given the following type signatures for two functions operating on lists:

— Concatentates two lists together. append :: [a] → [a] → [a] — Takes the first ‘n‘ elements from a list. take :: Int → [a] → [a]

(ii) In the future, Haskell will support Dependent Types, allowing types to depend on values. Discuss how you can improve the definition of take using dependent types to ensure that it works as intended.

Link to original

2019:

FP 2019 Past Paper

Question 1: Type Inference and Functions

1a)

Question

Consider a function pairToList that takes a tuple of two elements with identical types, and returns a list containing the same two elements. Give the full definition of this function in Haskell, including its type signature.

1b)

Question

Now consider a function listToPair :: [a] -> Maybe (a,a) that takes a list of two elements and returns a pair containing the same two elements.

1c)

Question

In some ways, listToPair and pairToList are dual functions. Write a simple QuickCheck boolean property to specify this duality.

1d)

Question

Study the Haskell expression below. Explain what it means, and what the resulting value will be.

(fmap.fmap) (+1) (Just (1,2))

1e)

Question

Suppose a Haskell program contains the following definitions:

n = 3 + n
xs = [if x==3 then n else x | x <- [0..5]
k = length xs

Give the values of n, xs, and k. For any undefined value, write bot (for bottom). If k is bot, explain why; if it is not, explain how its value is computed.

1f)

ABSTRACT

Consider a list posInts:: [Int] with value [1, 2, 3, …] which is infinitely long.

(i) Write a definition of posInts.

(ii) Explain how lazy evaluation makes it possible to define infinite data structures like posInts.

Question 2:

Abstract

Haskell’s type inference allows type signatures of Haskell functions to be calculated automatically from a function definition. For each of the following definitions, provide an appropriate, general type signature for func.

2a)

Question

func xs = map (+1) xs

2b)

Question

func x = do

let n = x * 2 let xs = replicate n ’*’ putStrLn xs

func :: Int -> IO () with 2 marks for IO () and 1 mark for Int →. Deduct 0.5 marks for: func :: Num a => a -> IO () since replicate requires an integer parameter. replicate :: Int -> a -> [a]

2c)

Question

func f xs = map show (filter f xs)

2d)

Question

func f g x = let res = g x in case res of Left e → Left (f e) Right r → Right r

2e)

Question

func xs ys = zipWith f xs ys

where f x y = do x’ ← h x y’ ← h y pure (x’, y’)

h [] = Nothing h (x:_) = Just x

2f)

Question

By default, type signatures are optional in Haskell source code. The GHC compiler has an option -fwarn-missing-signatures that warns programmers if a top-level function body has a missing signature. Give one advantage and one disadvantage of this default behaviour.

Question 3:

Abstract

Acme University has the following percentage/grade/point mappings for student assessments:

PercentageLetter GradeGrade Point
100− 85A5
84− 74B4
73− 63C3
62− 52D2
51− 41E1
40− 0F0

3a)

Question

Write a suitable Haskell data type, called LetterGrade, to represent letter grades A–F inclusive.

data LetterGrade = A | B | C | D | E | F — 1 mark for data keyword — 1 mark for sum type with six values

Award no more than 0.5 marks for a String encoding!

3b)

Question

Define a Haskell function, including type signature, that calculates an integer grade point value from a LetterGrade value.

3c)

Question

Define a Haskell function, including type signature, that calculates a LetterGrade value from an integer percentage.

3d)

Question

A grade point average (GPA) is computed as the average (i.e. arithmetic mean) of a list of grade point scores. Grade point scores are integer values. The GPA is a real number, i.e. a floating-point value. Define a function gpa, including an appropriate type signature, that takes a list of grade point scores and, where possible, returns a GPA value. Pay attention to potential error cases.

gpa :: [Int] → Maybe Float — 1 gpa [] = Nothing — 1 gpa xs = if length (filter (\x → x<0 || x>5) xs) > 0 — 1 then Nothing — 1 else Just ((fromIntegral length xs)) — 2

3e)

Question

Typeclasses provide a means to write parametric code and ensure that polymorphic functions can utilise common functionality. Outline, perhaps using Haskell code fragments, how you might construct a typeclass that allows you to represent marks as any of letter grades, percentages, and grade points. Explain how typeclass definitions can reduce boilerplate code.

Link to original

2020:

FP 2020 Past Paper

Question 1: Higher-Order Functions

1a)

Question

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

1b)

Question

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

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.

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.

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

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.

Question 2: Maps (Dictionaries) and Types

2a)

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?

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

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?

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?

Question 3: Monads

3a)

Question

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

(>>=):: (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?

3c)

Question

Discuss possible motivations for using the Comp monad.

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

Link to original

2021:

FP 2021 Past Paper

Question 1: Parametric Polymorphism and Types

1a)

Question

What is parametric polymorphism and why is it so common in Haskell?

Like generics in Java (0.5 marks) we can use type variables (0.5 marks) in Haskell to represent unconstrained, or arbitrary (0.5 marks) types for values. Effectively type variables are universally quantified (0.5 marks). It allows us to maintain static type safety (0.5 marks) while expressing computation in a generic way (0.5 marks), regardless of actual types (0.5 marks) max of 1.5 marks for the definition.

Due to Haskell’s powerful type inference system (0.5 marks), we can resolve type variables at compile time. The functional nature of Haskell (0.5 marks) and its widespread use of container data structures (0.5 marks) make polymorphism an efficient way to code generically. max of 1.5 marks for the explanation.

1b)

Abstract

Consider the Haskell functions with their type signatures listed below. For each function, give an actual function definition that would conform to the type signature shown. In each case, also give a short documentation-style explanation of the behaviour for the particular function you define.

(i) f :: a -> a

f x = x — identity function

g x y = x — selector, return first of two parameters

(iii) h :: a -> [b]

1c)

Abstract

Now consider this Haskell function:

twice f x = f $ f x — apply f two times to x

(i) Give the Haskell type of the function twice and explain how you have inferred this type. 

 
(a->a)->a->a
 
(a->a) -> (a->a) -> a -> a
(a->a) -> a -> a

Question 2: Lists and Lazy Evaluation

Abstract

This question is about lists in Haskell. Note that, where you are asked to produce source code, minor syntax errors will not be penalised so long as your intention is clear and correct.

2a)

Question

Give a Haskell definition for an infinite list of strings, yn :: [String], where every even indexed element of the list is the String value “yes” and every odd indexed element of the list is the String value “no”. Try to ensure your definition of yn is concise.

2b)

Question

Briefly discuss (in 50 words or fewer) the features of the Haskell language that enable the definition of such an infinite data structure.

2c)

Question

Give a QuickCheck property specification p::Int->Bool that could be used to test that odd indexed elements of list yn are equal to the String value “no”.

2d)

Question

Will a test run of quickCheck p actually terminate? If so, why does it terminate? If not, why not?

Yes it will terminate (1 mark). Even though the list is infinite, QuickCheck only runs a finite number of test cases (1 mark).

2e)

Question

Give the Haskell definition for a function butter :: String -> String which appends the String value " but " onto its argument. For instance butter "head" will evaluate to "head but ".

2f)

Question

Now give the Haskell definition for a function uncertainty :: [String] -> String where the invocation uncertainty yn will evaluate to the String value "yes but no but yes but no but". You should use appropriate functions from the Haskell Prelude, along with the butter function from above.

2g)

Question

Observe that the infinite list yn only contains two distinct values. Is it possible for a Haskell list to contain an infinite number of distinct values? If so, give an example list. If not, explain why not.

Question 3: Email API and Monads

Abstract

This question involves a scenario about sending emails. Some of the APIs are real, whereas others are fictitious. You have encountered the real APIs throughout the course. The question provides you with all the relevant documentation required to make use of the fictitious APIs. Note that developing compilable Haskell code will simply take too long. Minor syntax errors will not be penalised. First, study the data type definition below. This is used to represent email addresses.

data Address = Address { user :: String, domain :: String }

3a)

Question

Write Haskell source code to turn an arbitrary Address value into an appropriate String value, by means of implementing the Show typeclass. The generated String value should concatenate the user and domain values, with an ’@’ character in between them.

 
instance Show Address of
	show (Address user domain) = user ++ "@" ++ domain

3b)

Question

Write Haskell source code, including an appropriate type signature, for getAddressFromUser, which prompts the user for a String value via interactive keyboard input and produces the appropriate Address value, if the input is valid. For the purposes of this question, you may assume that valid user input would be a String including a single ’@’ character, which is neither the first nor the last character. Your code should handle invalid input in a reasonable, idiomatic fashion for Haskell. Note that you may make use of the splitOn API function:

splitOn :: String — String to split on, error if empty → String — Input text → [String] — Result — break input text String into pieces — separated by the first String — argument, consuming the delimiter.

getAddressFromUser:: IO (Maybe Address)
getAddressFromUser = do
	input <- getLine
	parts = splitOn "@" input
	if length parts /= 2 then
		return Nothing
	else
		return $ Just $ Address (parts !! 0) (parts !! 1)

3c)

Question

Now consider the following API functions:

mkMail :: Address — sender email address (from) → Address — recipient email address (to) → String — email subject → String — email body → Email — result sendMail :: String — hostname of smtp server → String — username for login → String — password for login → Email — message to send → IO() — result


Why does the sendMail function have an IO result but the mkMail function does not have an IO result?

3d)

Question

Study the following specification carefully, then write Haskell code to meet this specification.

You may find it helpful to use higher-order list functions like map, mapM, mapM_, or similar. Your task is to produce an implementation of the function sendEmails :: [Address] -> IO (). This function prompts the user for input with a question: ‘what is your email address?’ then receives an answer using getAddressFromUser as defined above. If the input email address is not valid, the function sets the sender address to “noreply@gla.ac.uk”. Now the code should construct an email to send to each of the addresses in the list supplied as the parameter of the sendEmails function. Each of these emails should come from same sender address. Each of these emails should have a subject set to the String value “Hello” and a body set to the String value “I hope your exam is going well.”. The emails should all be sent via the server smtp.gla.ac.uk with username foo and password secret.

There are lots of possible solutions to this exercise. Marks will be awarded for correctness, as well as for idiomatic, elegant functional code.

sendEmails :: [Address] -> IO ()
sendEmails emailList = do
	putStrLn "What is your email address?"
	givenAddress <- getAddressFromUser
	let userAddress =
		case givenAddress of
			Nothing -> (Address "noreply" "gla.ac.uk")
			(Just a) -> a
	let emails = map (\x -> mkEmail givenAddress x "Hello" "I hope your exam is going well") emailList
	mapM_ (\x -> sendMail "smtp.gla.ac.uk" "foo" "secret" x) emails

— 1 for sendMail with args — 2 for point-free, lets, and/or other elegant style

Link to original

2022:

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.

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?

1c)

Question

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

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?

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?

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

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

21

2b)

(b) Given the following code: 

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

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

(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 .. ]

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?

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)

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

(ii) Complete the implementation of >>=. 

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

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

f = This . id

What is the type of f?

f :: 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) ≡ ...

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

return x >>= ... ≡ This x

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

(This x >>= This) >>= This ≡ ... >>= (\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, =, >>= ]

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?

uLookup (show v1) = UUnknown

`uCheck “1” = UUnknown¦

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

Link to original

2023:

FP 2023 Past Paper

Question 1: Algebraic Data Types in Real World Entities

1a)

Question

Write Haskell code to define an algebraic data type called Tower. A Tower value has three components: two integer values to represent height and width and a single character value to depict the shape of the top of the tower.

1b)

Question

(b) A smart constructor constrains the creation of values for user-defined types like Tower. Why might smart constructors be helpful? Give a sensible implementation of a smart constructor for Tower values that satisfies the type specification below: mkTower :: Int -> Int -> Char -> Maybe Tower

A smart constructor enforces constraints on component values supplied to a value constructor, preventing the creation of instances with erroneous, inconsistent or impossible values (1 mark). Give 0.5 marks for a partial answer or a sensible example.

mkTower height width top
| height < 0 || width <=0 = Nothing
| otherwise = Just $ Tower height width top
  • 1 mark for a sensible check
  • 1 mark for a Nothing
  • 1 mark for a value constructor call, wrapped in Just

1c)

Question

Which Haskell type class is associated with the generation of String representations of values?

The Show typeclass

The Show typeclass (1 mark). Only award 0.5 marks if student says show (lower-case) since that is a function.

1d)

Question

Write Haskell code to make it possible for Tower values to be converted to ASCII-art style String values. Your code should include the appropriate type class instantiation and the relevant function definition. Some examples of ASCII-art String values that might represent Tower instances are given below. The description is on the left hand side and the ASCII-art is on the right hand side.

Tower with height 2, width 1, top '*'  *
                                        |
                                        |

Tower with height 1, width 4, top '+'   +
                                       | |

Tower with height 4, width 3, top '^'   ^
                                       | |
                                       | |
                                       | |
                                       | |

Give marks for correctness and style of Haskell, up to max of 5. Example solution below. Accept reasonable alternatives.

instance Show Tower where {- 1 mark -}
  show t = {- 1 mark -}
    let
      w = width t
      h = height t
      section = if w == 1
        then "|" {- 1 mark -}
        else "|" ++ (replicate (w-2) ' ') ++ "|"
      base = concat (replicate h (section ++ "\n"))
      {- ^^^ 1 mark -}
      top_space = (replicate ((w-1) 'div' 2) ' ')
      centred_top =
        top_space ++ [top t] ++ top_space ++ "\n"
    in {- 1 mark -}
      centred_top ++ base

1e)

Question

Now consider a single variant algebraic datatype called LeaningTower, where a LeaningTower value has two components: a Tower and an integer. This represents a tower that is leaning over at an integer angle (in degrees) to the vertical. In some sense, LeaningTower is a special case of Tower. Thinking about the definition for LeaningTower, and based on your experience, comment briefly on facilities for inheritance and code reuse in Haskell.

1f)

1g)

Question 2: Modeling a Gameshow

Abstract

This question is about modelling a gameshow, where a contestant needs to answer a sequence of questions correctly to win a prize. The rules of the game are as follows: • There is a maximum of 10 questions in the game • If a contestant gets a sequence of 10 correct answers, they win £1024 • If a contestant gets a question wrong, the game ends immediately • If the game ends because of an incorrect answer, then if the contestant has a sequence of five or more correct answers before their incorrect answer, they win £32 • If the contestant does not have a sequence of five or more correct answers, then they do not win any prize money

2a)

Question

Suppose the sequence of answers is modelled as a list of Bool values, with the most recent answer at the head of the list. A list element is True if the corresponding answer was correct, and False otherwise. Write Haskell code to calculate the prize for this contestant according to the game rules. Your function should have the following type: prize :: [Bool] -> Int

Up to 5 marks for translating the rules into appropriate Haskell code. Proportional marks for partially correct answer (e.g 2 for correct award of 1024, 2 for correct award of 32, 1 for correct award of 0).

Example solution below, accept reasonable alternatives.

prizeAwarded :: [Bool] -> Int
prizeAwarded answers =
  if and answers && length answers == 10
  then
    -- all 10 correct
    2 ^ 10
  else
    let lastfive = drop (length answers - 5) answers
    in
      if and lastfive && length lastfive == 5
      then 2 ^ 5 -- five right in a row
      else 0 -- loser
prize :: [Bool] -> Int
prize xs
  | fullCorrect  = 2 ^ 10   -- all ten answers correct
  | consolation  = 2 ^ 5    -- last five in a row correct
  | otherwise    = 0        -- no prize
  where
    fullCorrect = length xs == 10 && all id xs
    consolation = length xs >= 5
               && all id (drop (length xs - 5) xs)

2b)

Question

(b) The Haskell action askQuestion :: IO Bool selects a question from a database, asks the question to the contestant, receives the answer from the contestant and checks whether the answer is correct. Discuss why the type of the askQuestion code is appropriate.

This avoids any source code - the student can’t type anything in here - they need to use their imagination and reason carefully.

  • Bool for the result of the question - True if correct answer, False otherwise. (1 mark)
  • Wrapped in IO because of side-effecting operations - database read, then interaction with user - print / getLine / or alternatives… (2 marks)

2c)

Question

A single round of the quiz is modelled with the following function: quizRound :: [Bool] -> IO [Bool] where the parameter of the function is a list of question results before this round, and the result of the function is a list of question results after this round, wrapped in the IO monad. Write an implementation of the quizRound function. Your implementation should invoke askQuestion exactly once. You should use either a monadic bind or the do notation.

(1 mark for the list cons, 1 mark for calling nextQuestion, 2 marks for appropriate sequencing with do or bind).

quizRound :: [Bool] -> IO [Bool]
quizRound answersSoFar =
  askQuestion >>= (\x -> return (x:answersSoFar))
-- OR --
do
  result <- nextQuestion
  return (result:answersSoFar)

2d)

Question

Write Haskell code to model the full gameshow, with a top-level entity game :: IO Int where the integer value is the prize money won by the contestant. You should make use of the functions defined in earlier parts of this question; you may define further auxiliary functions, if required.

Give marks for correctness and style of Haskell, up to max of 5 marks. Example solution below.

quizRound :: [Bool] -> IO [Bool]
quizRound answersSoFar =
  nextQuestion >>= (\x -> return (x:answersSoFar))
 
quiz :: IO [Bool] -> IO Int
quiz state = do
  answers <- state
  -- run this single round
  -- let state' = quizRound answers
  answers' <- quizRound answers
  -- check for end of game
  if (length answers' >= max_answers ||
     not (head answers'))
  then
    -- game over
    return $ prizeAwarded answers'
  else do
    -- another round
    putStrLn "another round"
    quiz (pure answers')
 
game :: IO Int
game = quiz (pure [])

2e)

Question

How might you tackle this modelling problem in a different way, if you were not constrained by the concrete types specified in this question?

Question 3: Functional Abstractions

Abstract

Recall that the Functor typeclass is defined as follows:

class Functor f where fmap :: (a → b) → f a → f b

3a)

Question

What is the purpose of the Functor typeclass?

3b)

Question

(b) Consider the ZeroOneMany data structure, defined as follows: data ZeroOneMany a = Zero | One a | Many [a]. Consider the following Functor instance for ZeroOneMany:

instance Functor ZeroOneMany where
  fmap f Zero = Many []
  fmap f (One x) = Many [f x]
  fmap f (Many xs) = Many (map f xs)

Is this a sensible Functor instance? Justify your answer, referring to the functor laws.

3c)

Question

Recall that the Monad typeclass is defined as follows:

class Monad m where
  return :: a -> m a
  (>>=) :: m a -> (a -> m b) -> m b

Given that type constructor m is an instance of the Monad typeclass, define the function: fmapM :: Monad m => (a -> b) -> m a -> m b in terms of return and >>=.

3d)

Abstract

The Bifunctor typeclass is defined as follows:

class Bifunctor p where
  bimap :: (a -> b) -> (c -> d) -> p a c -> p b d
  first :: (a -> b) -> p a c -> p b c
  second :: (b -> c) -> p a b -> p a c

Further, consider the BiBucketTree data type, defined as follows, which represents a tree which can either contain lists of values of type a or of type b:

data BiBucketTree a b =
  Leaf
  | LeftNode [a] (BiBucketTree a b) (BiBucketTree a b)
  | RightNode [b] (BiBucketTree a b) (BiBucketTree a b)

Question

(i) Based on the type signatures of bimap, first, and second, describe the purpose of the Bifunctor typeclass. Give an example of when you might wish to use a Bifunctor instance.

Question

(ii) Write a function reverseBuckets :: BiBucketTree a b -> BiBucketTree a b which reverses the contents of the list at each node. For example, reverseBuckets (LeftNode [1,2,3] Leaf Leaf) = LeftNode [3,2,1] Leaf Leaf

Question

(iii) Write a Bifunctor instance for BiBucketTree.

Link to original

2011:

FP 2011 Past Paper

Question 1: Types and Functions

with value [1, 2, 3, …] which is infinitely long. (i) Write a definition of posInts.

Answer:

posInts :: [Int]
posInts =
 let f x = x : f (x+1)
 in f 1

Question 2: Embedded Domain Specific Languages

Question 3: Monads and Equational Reasoning

Question 4: Interactive Programming

→ Maybe a, and safeTail :: [a] → Maybe [a].

Answer:

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x
 
safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (x:xs) = Just xs
Link to original

2012:

FP 2012 Past Paper

Question 1: Types and Functions

with value [1, 2, 1, 2, …] which is infinitely long. (i) Write a definition of onetwo. (ii) Give the value of (take 5 (map (3*) onetwo)), and explain how it can be evaluated even though onetwo is an infinite list.

Answer: (i)

onetwo :: [Int]
onetwo = 1 : 2 : onetwo

(ii) [3, 6, 3, 6, 3] This is possible because of lazy evaluation. Onetwo requires only two cells to represent, with a circular pointer. The map defines an infinite list, but only the part that is needed is computed, and take needs only 5 elements. [Requires understanding lazy evaluation.]

Question 2: Domain Specific Languages and Parsec

Question 3: Monads and IO

Question 4: Imperative Style in Haskell

Link to original

Dumped Extra Questions

Question 2: Embedded Domain Specific Languages (EDSLs)

2a)

2b)

2c)

2d)

2e)

Question 3: Monads and Equational Reasoning

3a)

3b)

3c)

Graph View

Backlinks