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.

(i) f 1 + 1

Answer

3 (because function application binds tighter than plus)

(ii) f (1+1)

Answer

4 (evaluate expr in parentheses first)

(iii) f $ 1+1

Answer

4 (evaluate rhs of dollar first)

(iv) (f 1)+ 1

Answer

3 (evaluate parens first)

(v) (+)(f 1)$ f 1 + 1

Answer

5 (== plus 2 (2+1))

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.

(i) g (f 1)

Answer

[Int]

(ii) f (g 1)

Answer

[Int]

(iii) (h.f)42

Answer

Int

(iv) h (g (f 1))

Answer

Int

(v) g h

Answer

[a] -> a

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.

(i) [2^x|x<-[3,1,4]]

Answer

[8,2,16]

(ii) map (\x->2^x)[1..3]

Answer

[2,4,8]

(iii) foldl (\x y -> x^y)1 [2,3]

Answer

1

(iv) foldr (\x y -> x^y)1 [2,3]

Answer

8

(v) foldr (\x y -> (2^x):y)[] [1,2,3]

Answer

[2,4,8]

1d)

(i) Outline two differences between lists and tuples in Haskell.

Answer

Any two of:

• syntax - square versus round brackets
• shape - lists can have any number of elements, tuples have fixed number
• type - list elements have uniform type, tuple elements can be different
• polymorphic list functions generalise over all lists, whereas n-tuple functions (fst, etc) are specialized for particular n

(ii) Define a function allpairs :: [a] -> [b] -> [(a,b)] that computes the Cartesian product of two lists, i.e. the list of all pairs of elements. For instance, allPairs "hi"[1,2,3] should evaluate to [('h', 1), ('h', 2), ('h', 3), ('i', 1), ('i',2), ('i', 3)].

Answer

-- 3 marks for list comps
allpairs xs ys = [(x,y) | x<-xs, y<-ys]
-- alternatively accept a
-- verbose recursive soln
-- perhaps something like
allpairs [] _ = []
allpairs (x:xs) ys =
  (map (\y->(x,y)) ys) ++
  (allpairs xs ys)

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.

Answer

eats :: Food a => (Dragon a) -> a -> (Dragon a)
eats (LiveDragon xs) x =  -- 1
  if (poisonous x)  -- 1
  then DeadDragon  -- 1
  else (LiveDragon (xs++[x]))  -- 1
eats DeadDragon _ = DeadDragon  --1

2b)

Question

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

Answer

instance Food Int where  -- 2
  poisonous x = (x==13)  -- 1

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.

Answer

The only code required is a type class instance spec for Dragon:

instance Food Dragon where  -- 2
  poisonous DeadDragon = True  -- 1
  poisonous _ = False  -- 1

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?

Answer

stretch question Yes, it’s possible (1) … but recursive data values are complex to navigate and process (1)

2e)

Question

What is the motivation for the Functor type class?

Answer

Like a Mappable interface in an OO language (1) it is used to process values stored in container data structures (1)

2f)

Question

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

Answer

Full marks for source code. Partial marks for a textual explanation of fmap without source code.

instance Functor Dragon where  -- 1
  fmap f DeadDragon = DeadDragon  -- 1
  fmap f (LiveDragon xs) = LiveDragon (fmap f xs)  --2

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]

(i) Explain why head and tail are considered unsafe.

Answer

• 1 mark Both head and tail are partial functions and require that the input lists are non-empty.
• 1 mark Calling each list during runtime with empty lists will result in a runtime error.

(ii) Rewrite head and tail so that they are considered safe.

Answer

Recall 1.5 marks per function

• 0.5 marks for correct type signature
• 1 mark for correct function body

Possible solution:

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

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.

Answer

Application

• 1 mark for reasonable representation of an alphanumeric digit.
• 1 mark for a reasonable representation of the old format using a five element tuple, or data constructor with five parameters.
• 3 marks for a reasonable representation of the new format, distributed as:
  • 1 mark for representing locality of registration.
  • 1 mark for representing years and months.
  • 1 mark for representing random sequence.

Possible solution:

data AlphaNumeric = Digit Int | Letter Char
  deriving (Eq, Show)
 
data State = North | South | East | West | Capital
  deriving (Eq, Show)
 
data CarReg = 
    OldFormat AlphaNumeric AlphaNumeric AlphaNumeric AlphaNumeric AlphaNumeric
  | NewFormat State Int Int Int [AlphaNumeric]
  deriving (Eq, Show)

(ii) Discuss how robust your definition of CarReg is from incorrect registration numbers in both the old and new car registration formats. Further, describe how you would use Haskell's module and type system to ensure only correct registrations can be constructed and incorrect registrations reported.

Answer

Synthesis/Recall:

• 1 mark for discusson of how robust the old format is.
• 2 mark for discussing how robust the new format representation is.
• 1 mark for describing how the module system can be used to encapsulate implementation details, and use smart constructors to control how car registrations are implemented.
• 1 mark for describing the use of Haskell’s Maybe or Either types to capture error.

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]

(i) Demonstrate how you would use the QuickCheck library to determine if the append function was working as intended.

Answer

Recall/Application

• 1 mark for a valid QuickCheck specification.
• 1 mark for a specification that tests appending of lists.

Possible solution:

prop_append_length :: [Int] -> [Int] -> Bool
prop_append_length xs ys = length (append xs ys) == length xs + length ys
 
-- Test with QuickCheck
test = quickCheck prop_append_length

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

Answer

Synthesis:

• 1 mark replacing the list definition with a list type indexed by the length of the list.
• 1 mark length of the list is encoded using a peano representation.
• 1 mark generating an invariant that the resulting list is the same length as the two input lists.

Possible solution:

-- With dependent types, we could define:
data Vec :: Nat -> * -> * where
  Nil :: Vec Zero a
  Cons :: a -> Vec n a -> Vec (Succ n) a
 
take :: (n <= length xs) => SNat n -> Vec m a -> Vec n a