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.

Answer

-- record style declaration worth 3 marks
data Tower = Tower { height :: Int, width :: Int, top :: Char }
-- simple ADT declaration only worth 2 marks
-- (without implicit accessors)
data Tower = Tower Int Int Char

Also accept different names for value constructor. Partial marks for partial solutions:

• 1 mark for data Tower on left
• up to 2 marks for definition on right hand side

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

Answer

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

Answer

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 '^'   ^
                                       | |
                                       | |
                                       | |
                                       | |

Answer

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.

Answer

(Discussion, open-ended reflection. Not covered in lecture notes. 1 mark for each sensible point, up to a max of 3 marks.)

Composition of datatypes is the way to achieve inheritance. Inheritance is only possible in type classes (cf. interfaces in Java) - so we can inherit APIs but not fields or behaviors.

Code reuse in Haskell is less straightforward than in OO languages - need to access Tower fields from LeaningTower - function composition required. Also tight coupling.

Typeclasses might ameliorate this problem somewhat.

1f)

What is property-based testing?

Answer

QuickCheck tool does property-based testing. Express properties as functional assertions (predicates) and test these functions on arbitrary (randomly generated) input values of appropriate types. (1 mark)

1g)

Suppose you are given a function with the following type: willFallOver :: LeaningTower -> Bool. You know that towers with zero height or zero lean will never fall over. Construct a function propZero to express this property, such that propZero could be provided as an input to QuickCheck, assuming that the QuickCheck tool knows how to generate arbitrary LeaningTower values.

Answer

Example solution below. Award marks for alternatives.

propZero = \t ->
  if (height.tower) t == 0 || lean t == 0
  then fallsOver t
  else True

• 1 mark for single-parameter predicate
• 0.5 marks for each ==0 check (x2)
• 0.5 marks for then fallsOver t
• 0.5 marks for else True

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

Answer

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.

Answer

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.

Answer

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

Answer

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?

Answer

• talk about using state monad to capture quiz results from previous rounds (1 mark)
• talk about need for IO, for user interaction (1 mark)
• talk about using monad transformers to combine state and IO (1 mark)
• Accept other reasonable solutions…

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?

Answer

The Functor typeclass allows us to apply a function to the contents of a type constructor (for example, a data structure such as a tree or a list, or an IO computation) (1 mark) in a structure-preserving way (1 mark).

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.

Answer

This is not a sensible Functor instance (1 mark) since it violates the functor laws (1 mark). Although it typechecks and applies the function to the contents of the data structure, the fmap implementation is not structure-preserving (1 mark).

As an example, consider the functor law fmap id = id. If we were to apply fmap id (One 5), we would obtain Many [5] instead of One 5 (1 mark).

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

Answer

fmapM f m = m >>= \x -> return (f x)

(1 mark for the left-hand-side of the equation fmapM f m or appropriate anonymous arguments, 1 mark for m >>= \x -> ..., 1 mark for return (f x)).

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.

Answer

Given a type constructor with two type arguments (1 mark), the Bifunctor typeclass allows us to apply two functions to its contents in a structure-preserving way (1 mark).

An example could be applying a function to the Either a b type, where either a function is applied to the contents of the Left type constructor, or a function is applied to the contents of the Right type constructor (1 mark for an example; one could be the BiBucketTree above).

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

Answer

reverseBuckets :: BiBucketTree a b -> BiBucketTree a b
reverseBuckets Leaf = Leaf
reverseBuckets (LeftNode xs bt1 bt2) =
  (LeftNode (reverse xs)
    (reverseBuckets bt1) (reverseBuckets bt2))
reverseBuckets (RightNode xs bt1 bt2) =
  (RightNode (reverse xs)
    (reverseBuckets bt1) (reverseBuckets bt2))

(3 marks for correct implementation; 2 for minor mistakes; 1 if there is an attempt at case splitting.)

Question

(iii) Write a Bifunctor instance for BiBucketTree.

Answer

There are a few possible solutions. The most compact is:

instance Bifunctor BiBucketTree where
  bimap f g Leaf = Leaf
  bimap f g (LeftNode xs bt1 bt2) =
    LeftNode (map f xs)
    (bimap f g bt1) (bimap f g bt2)
  bimap f g (RightNode xs bt1 bt2) =
    RightNode (map g xs)
    (bimap f g bt1) (bimap f g bt2)
  first f = bimap f id
  second g = bimap id g

Alternatively it is possible to implement bimap in terms of first and second:

instance Bifunctor BiBucketTree where
  first f Leaf = Leaf
  first f (LeftNode xs bt1 bt2) =
    LeftNode (map f xs) (first f bt1) (first f bt2)
  first f (RightNode xs bt1 bt2) =
    RightNode xs (first f bt1) (first f bt2)
  second f Leaf = Leaf
  second f (LeftNode xs bt1 bt2) =
    LeftNode xs (second f bt1) (second f bt2)
  second f (RightNode xs bt1 bt2) =
    RightNode
    (map f xs) (second f bt1) (second f bt2)
  bimap f g = first f . second g

It would also be acceptable to implement all functions explicitly.

• 1 mark for defining an instance with stubs for all methods.
• 1 mark for case-splitting within the function definitions.
• 1 mark for correct recursive calls on sub-structures.
• 1 mark for ensuring map f xs is applied to each bucket.
• 1 mark for correct implementations of all functions (either bimap in terms of left, right; or left, right in terms of bimap; or all explicitly)