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.
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.
(i) Why is the return value wrapped as a Maybe instance?
Answer:
Input list may not have precisely two items, so we can’t always return a pair
Need to return an error value for some inputs - Nothing
(ii) Give the Haskell definition for the listToPair function
Answer:
listToPair [x,y] = Just (x,y)listToPair _ = Nothing
(iii) Briefly describe a refinement to the type system that would enable a programmer to specify that the listToPair function will only handle lists with two elements.
Answer:
Dependent types, which would allow us to do simple integer arithmetic on list lengths statically.
1c)
Question
In some ways, listToPair and pairToList are dual functions. Write a simple QuickCheck boolean property to specify this duality.
Answer:
prop_dual x = (listToPair (pairToList x)) == (Just x)
1d)
Question
Study the Haskell expression below. Explain what it means, and what the resulting value will be.
(fmap.fmap) (+1) (Just (1,2))
Answer:
(+1) is the increment function
Just (1,2) is a pair of numbers wrapped in a Maybe instance
The double fmap allows us to apply the increment function inside the nested structure (a nested functor - tuple inside Maybe)
The result is Just (1,3) (not Just (2,3))
1e)
Question
Suppose a Haskell program contains the following definitions:
n = 3 + nxs = [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.
Answer:
The value of n is bottom (undefined) because the addition requires the value of n, and this cannot be computed before the addition is performed. Thus n has a circular definition that cannot be computed. The list xs has the value [0, 1, 2, bot, 4, 5]; thus the list itself is not bottom, but one of its elements is bottom. The value of k is 6, which is defined because the length function only examines the list structure and does not need to use any of the values in the list.
1f)
ABSTRACT
Consider a list posInts:: [Int] 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
(ii) Explain how lazy evaluation makes it possible to define infinite data structures like posInts.
Answer:
Without lazy evaluation, the expression f 1 would never return a value; it would go into an infinite loop filling up memory with the list. Lazy evaluation causes a closure to be returned, which is a representation of how to compute more of the result when needed. Only as much of the list will be constructed as actually needed by the program.
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
Answer:
func :: Num a => [a] -> [a]
with 1 mark for [a]→[a] and 1 mark for Num constraint. The following will get
only 1 mark:
func :: [Int] -> [Int]
2b)
Question
func x = do
let n = x * 2
let xs = replicate n ’*’
putStrLn xs
Answer:
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)
Answer:
func :: Show a => (a -> Bool) -> [a] -> [String]
• 1 mark: f is a function that returns a Bool, from the type of filter.
• 1 mark: the second argument is a list
• 1 mark: for recognising that show implies use of the Show typeclass and that
also means the function return type includes a String.
• 1 mark: for recognizing that the map means the function return value is a list of
Strings
2d)
Question
func f g x =
let res = g x
in
case res of
Left e → Left (f e)
Right r → Right r
Answer:
func :: (a -> b) -> (s -> Either a r) -> s -> Either b r
We are looking for:
• 0.5 mark: if there are five arrows in the type
• 0.5 mark: if there are three top-level parameters and one result
• 1 mark: The function f::a->b converts the error returned by g to one returned
by f.
• 2 marks: The function g maps the type of x to an Either type
• 1 mark: there is a correspondence between the return type of g and the overall
return type, with the appropriate Left component type changed according to the
mapping in f
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
Answer:
func :: [[a]] -> [[b]] -> [Maybe (a,b)]
Where:
• 1 mark: Both xs and ys are lists of lists with different polymorphic types.
• 2 marks: The function f dictates the element type of the result of zipWith
i.e. a list of Maybe pairs of elements from xs and ys. Here f is a red herring,
Maybe is a monad!
• 1 mark: The type of zipWith means we are returning a list.
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.
Answer
• 1 mark for a reasonably described advantage, for example, sometimes you don’t
know the type
• 1 mark for a reasonably described disadvantage, for example, gap between
mental model and actual model
Question 3:
Abstract
Acme University has the following percentage/grade/point mappings for student assessments:
Percentage
Letter Grade
Grade Point
100− 85
A
5
84− 74
B
4
73− 63
C
3
62− 52
D
2
51− 41
E
1
40− 0
F
0
3a)
Question
Write a suitable Haskell data type, called LetterGrade, to represent letter grades A–F
inclusive.
Answer
Ideally we are looking for an enumerated types such as:
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.
Answer
Solution: We are looking for a simple function that uses pattern matching of
LetterGrade data constructors to a grade point, encoded as an Int.
• 1 mark: for type signature LetterGrade → Int
• 1 mark: for pattern matching
• 1 mark: for correctness
3c)
Question
Define a Haskell function, including type signature, that calculates a LetterGrade value
from an integer percentage.
Answer
• 2 marks: Suitable type signature that encapsulates possible error: Either or
Maybe.
• 1 mark for use of guards or similar construct for catching the ranges of percent-
ages.
• 1 mark for appropriate error handling.
• 1 mark: correctness.
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.
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.
Answer
1 mark: need to define conversion functions between the various mark represent-
ations, like the letter grade to point conversion function above
• 1 mark: have a canonical representation (perhaps grade points?) and convert each mark into this canonical representation when processing.
• 1 mark: The typeclass will specify a toGradePoint function
• 1 mark:Sensible definition e.g. class Mark a where toGradePoint :: a -> Int
• 2 marks: Using a canonical representation means we can do all calculations in
this form, reducing number of functions and cases to consider … conversion
functions mean we do implicit conversions to avoid excess duplicated conversion
code.
• max 4 marks