CPSC 312 2021 – Midterm #2 Practice Questions
You will be given any predefined functions you need (but you will need
to know Haskel’s syntax including lambda, list constructors (: and
[]), tuple constructors, list comprehensions, etc.)
Everything in the exam has been covered in lectures and/or assignments
and/or projects and/or on Piazza.
See the schedule for the sections of Textbook (Haskell: craft of
functional programming) covered. The textbooks contains different
examples than we used in class, but the exam isn’t about these examples.
See the first practice midterms (and the actual midterm) for more practice
questions.
The exam will be worth 50 marks in 50 minutes. This is designed to be a mark per
minute, so 4 marks does *not* mean we expect 4 points. It means you
shouldn’t spend more than 4 minutes on it (until you have done the
other questions).
The most important part is to read and answer the questions
asked. Writing true but irrelevant points will not give you extra
marks. Marks will be deducted if you write false statements, even if
you also gave a full and complete answer.
If you are asked to explain something, explain why it is like
that. (E.g., in the question in the 1st midterm, that asked to explain
something like Num a in
sum :: Num a => [a] -> a
you needed to explain why it was like this, and not just as if it was
sum :: [Num] -> Num
which is not legal Haskell. Particularly as it was worth multiple marks.)
Question 1
What do each of the following return:
(\f g x -> f x (g x)) (\ x y -> 2*x) (\x y -> x*x) 5
(\f g x -> f x (g x)) (\ x y -> y) (\x y -> x*x) 5
Note that these are both legal Haskell expressions.
Question 2
(a) Suppose we want a function (call it app2) that given two lists l1 and l3 gives
the list l2 such that l1++l2 == l3
Give an appropriate function that works for arbitrary lists of the
same type. You need to give both the type and the code.
[Hint: you need to think about the appropriate return type.]
It need to give appropriate answers for
app2 [1,2] [1,2,3,4,5]
app2 [1,2] [4,5,7,8]
(b) Write a function
iappend lst
which returns the list of pairs of lists (l1, l2) such that l1++l2=l3
For example:
*Main> iappend [1,2,3,4]
[([],[1,2,3,4]),([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4]),([1,2,3,4],[])]
(c) Define a function shuffle l1 l2
that returns the list of all interleavings of the elements of lists l1
and l2, where an interleaving consists of some elements of one list
followed by some elements of the other list followed by elements of
the first list and so on. The ordering of the elements in each of l1
and l2 should not be changed. You can use any built-in functions or
constructs you like.
It should have the following behaviour:
*Main> shuffle [1,2] [7,8]
[[1,2,7,8],[1,7,2,8],[1,7,8,2],[7,1,2,8],[7,1,8,2],[7,8,1,2]]
*Main> shuffle [2] [7,8]
[[2,7,8],[7,2,8],[7,8,2]]
(d) Write a function ave that takes a (finite)
sequence of integers and returns the average (to a whole
number) of the elements of the sequence. It should only make one pass
through the list. (The obvious solution:
ave lst = sum lst `div` length lst
makes two passes, one to compute sum and one to compute length)
Question 3
Consider the following declaration:
data BSTree k v = Empty
| Node k v (BSTree k v) (BSTree k v)
deriving (Eq, Show, Read)
(a) What is BSTree?
What is k?
(b) For:
Node k v (BSTree k v) (BSTree k v)
What is Node? Give as much information as is contained in this line.
(c) Give an example of the use of Node where it returns a value. It
must be legal Haskell. Give the type of the result.
(d) Write a function
lefttree :: BSTree k v -> Maybe (BSTree k v)
that returns the left tree if it exists and Nothing otherwise.
(e) Explain what the following does:
instance (Show k, Show v) => Show (BSTree k v) where
show t = “\n”++foldr (\ e r -> (show e) ++ “\n”++ r) “” (tolist t) — list of elements
Question 4
In the definition of argmax_mem in Minimax_mem.hs (see schedule):
— argmax_mem f lst mem = ((e, f e), mem1)
— where e is an element of lst that has a maximal value for f
— updates the memory to mem1. Each call to f can update memory
argmax_mem :: Ord v => (e -> m -> (v,m)) -> [e] -> m -> ((e,v),m)
argmax_mem f [e] mem = ((e, v),mem1)
where (v,mem1) = f e mem
argmax_mem f (h:t) mem
| fh > ft = ((h,fh),mem2)
| otherwise = ((bt, ft),mem2)
where
((bt,ft),mem1) = argmax_mem f t mem
(fh,mem2) = f h mem1
what would happens if the last two lines were replaced with
((bt,ft),mem2) = argmax_mem f t mem1
(fh,mem1) = f h mem
Explain why.
Give the type, and define the function
sum_mem f lst mem
that returns pair (s,mem1)
where s = sum[f e | e <- lst]
but where the memory is threaded through the calls to f,
and mem1 is the updated memory. So f can have side effects reflected in mem.
[It is like argmax_mem but sums. The memory should be a type variable
in the type declaration].
You can test it with (but think about what it should return first):
sum_mem (\ e m ->( e*2 ,(e^2:m))) [1,3,5,7,9] []
Question 5
Based on the posts on Canvas and Piazza on the applications of functional programming
(e.g., https://code.facebook.com/posts/745068642270222/fighting-spam-with-haskell/)
(Read this, and then come back to this question. You will not be
expected to remember any of it, but it provides good evidence for what
you write).
(a) What are the main advantages of strong typing?
(b) What are the main advantages of interactive development?
(c) What are the main advantage of no side effects?
There are many more exercises in the sections of the textbook referred
to in the schedule tab. Practice, practice, practice.