For each of the following Haskell expressions, write down the result of evaluation.
(i) map (\x->'.')"xyz"
Answer
”…”
(ii) map (\x->[])][]
Answer
[]
(iii) map (\x->[])"abc"
Answer
[[],[],[]] — more tricky than previous case! Don’t accept single empty list here.
(iv) map (\x -> (x,x))"abc"
Answer
[('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')
Answer
(1,a) — since f is polymorphic, and late-bound, although students don’t need to state this explicitly.
1b)
For each of the following Haskell fold expressions, write down the result of evaluation.
(i) foldl (+)0 [1,2,3]
Answer
6
(ii) foldr (+)0 [1,2,3]
Answer
Answer: 6 (same as previous)
(iii) foldl (-)0 [1,2,3]
Answer
Answer: ((0-1)-2)-3 == -6 (calculation not required, just result)
(iv) foldr (-)0 [1,2,3]
Answer
Answer: 1-(2-((3-0))) == 2 (calculation not required, just result)
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?
Answer
Students might comment that foldl (+) and foldr (+) have the same results, but foldl (-) and foldr (-) don’t. [0.5] Students might say that op a b must be the same as op b a — not quite, but worth [0.5]. op is associative [2], or (a ‘op’ (b ‘op’ c))== ((a ‘op’ b)‘op’ c) [2]. (max 2)
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.
Answer
concat :: [[a]] -> [a] -- can omit type since givenconcat [] = [] -- [1]concat (x:xs) = x ++ (concat xs) -- [2]
1e)
Question
(e) Write a point-free definition for the concat function.
Answer
concat :: [[a]] -> [a] -- can omit type since givenconcat = foldr (++) [] -- could be foldl instead [3]-- one mark for fold, one for (++), one for []
Question 2: Monads and Pirate Ships
2a)
Question
What is the type of the monadic bind operator (>>=) in Haskell?
Answer
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.
(i) Encode addTreasure as a Haskell function, including its type signature.
Answer
-- [1] for type signatureaddTreasure :: PirateShip -> Maybe PirateShipaddTreasure (PirateShip n) = if n<3 then Just (PirateShip (n+1)) else Nothing-- [1] for each line of function
(ii) Write another function called removeTreasure, which takes a PirateShip as its input parameter. If there is no treasure on the input PirateShip then the result should be a (PirateShip 0) wrapped in a Just instance. If the input PirateShip does have treasure, then the result should be a PirateShip with one less treasure chest on board, wrapped up in a Just instance.
Answer
-- [1] for typeremoveTreasure :: PirateShip -> Maybe PirateShipremoveTreasure (PirateShip n) = Just (PirateShip (if n>1 then (n-1) else 0))-- [3] for function definition
(iii) Now a voyage of a PirateShip can be denoted as a sequence of addTreasure and removeTreasure function calls. Show how you would encode such a sequence in Haskell, using the monadic bind operator.
Answer
Start with an empty pirate ship, wrapped in a Just. i.e. Just (PirateShip 0). [1] Then use bind to sequence [1] addTreasure and removeTreasure calls. e.g. [1]
Just (PirateShip 0) >>= addTreasure >>= addTreasure >>= removeTreasure
(iv) What is the value of such a sequence if more than three consecutive addTreasure calls appear in the sequence?
Answer
Nothing. [2]
(v) Suggest an alternative higher-level syntactic construct in Haskell to encode the voyage of a PirateShip.
Answer
Ideally the do construct [1] which is syntactic sugar [1] for a sequence of binds. Give an example [1] like
do x <- Just (PirateShip 0) y <- addTreasure x z <- removeTreasure y return z
I would give appropriate credit for other solutions, like using forM_ or sequence_ from the Control.Monad library.
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.
Answer
countNodes :: Tree a -> Int -- could miss out type since givencountNodes Leaf = 0 -- base case [1]countNodes (Node _ t1 t2) = 1 + countNodes t1 + countNodes t2-- [1] for pattern match-- [1] for recursion-- [1] for correct addition
3b)
Question
Write a function mirror :: Tree a -> Tree a that returns the mirror image of a binary tree.
Answer
mirror :: Tree a -> Tree a -- can omit type, since givenmirror Leaf = Leaf -- [1]mirror (Node x t1 t2) = Node x (mirror t2) (mirror t1)-- [1] for pattern match, [1] for recursive call-- [1] for correctness
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
(i) Now express that Tree a is an instance of the Twistable typeclass, with reference to the countNodes and mirror functions you have already defined.
Answer
instance Twistable (Tree a) where twist = mirror size = countNodes-- 1 mark per line
is an instance of the Twistable typeclass.
Answer
instance Twistable ([a]) where twist = reverse size = length-- 1 mark per line
(iii) Here are the properties that twist must satisfy:
If the data to be twisted has size 0, then the twisted data has the same value as the original data.
The twisted data always has the same size as the original data.
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.
Answer:
-- 1.quickCheck((\x-> if (size x) == 0 then (twist x)==x else True)::(Eq a)=>[a]->Bool)-- 2.quickCheck((\x-> if (size x) > 0 then size(twist x)==(size x) else True)::[a]-> Bool)-- 3.quickCheck((\x-> twist(twist x)==x)::(Eq a)=>[a]->Bool)-- [2] marks per spec. Partial marks for nearly correct solutions