— CPSC 312 2021 – Midterm #2 Practice Questions
— Question 1
— (\f g x -> f x (g x)) (\ x y -> 2*x) (\x y -> x*x) 5
— returns 10
— (\f g x -> f x (g x)) (\ x y -> y) (\x y -> x*x) 5
— returns (\y -> 25)
— try:
— (\f g x -> f x (g x)) (\ x y -> y) (\x y -> x*x) 5 999
— Reduction:
— (\f g x -> f x (g x)) (\ x y -> 2*x) (\x y -> x*x) 5
— (\ x y -> 2*x) 5 ((\x y -> x*x) 5)
— 2*5
— 10
— Question 2
— This needs to allow for the case where there is no l2 such that l1++l2=l3. That is why we need to return a Maybe.
app2 :: Eq a => [a] -> [a] -> Maybe [a]
app2 [] lst = Just lst
app2 _ [] = Nothing
app2 (h1:t1) (h2:t2)
| h1 == h2 = app2 t1 t2
| otherwise = Nothing
— Try:
–app2 [1,2] [1,2,3,4,5]
–app2 [1,2] [4,5,7,8]
— iappend l = [(l1,l2)] where l1 appended to l2 gives l
— returns list of all answers
iappend :: [t] -> [([t],[t])]
iappend [] = [([],[])]
iappend (h:t) = ([],(h:t)) : [(h:l1,l2) | (l1,l2) <- iappend t]
-- try:
-- iappend [1,2,3,4]
shuffle :: [t] -> [t] -> [[t]] — list of all shuffles
shuffle l1 [] = [l1]
shuffle [] l2 = [l2]
shuffle (h1:t1) (h2:t2) =
[h1:e | e <- shuffle t1 (h2:t2)] ++ [h2:e | e <- shuffle (h1:t1) t2]
-- sumn lst = (sum lst, lenght lst)
sumn :: [Int] -> (Int,Int) — (sum,length)
sumn [e] = (e,1)
sumn (h:t) =
let (s,n) = sumn t
in (s+h, n+1)
ave lst =
let (s,n) = sumn lst
in s `div` n
— Question 3
data BSTree k v = Empty
| Node k v (BSTree k v) (BSTree k v)
deriving (Eq, Show, Read)
{-
(a) BSTree is a paramtrized type, k is a type
(b) Node is a function that takes 4 arguments, the first is of type k, the second is of type v and the 3rd and 4th arguments are of type (BSTree k v). It also is a deconstructor of trees that are not empty; it can be used on the left side of =.
(c) Here are two examples
Node 3 ‘a’ Empty Empty
Node 3 ‘a’ (Node 1 ‘b’ Empty Empty) Empty
These can both be of type: BSTree Integer Char
(d)
-}
lefttree :: BSTree k v -> Maybe (BSTree k v)
lefttree Empty = Nothing
lefttree (Node _ _ lt _) = Just lt
— try
— lefttree (Node 3 ‘a’ (Node 1 ‘b’ Empty Empty) Empty)
{-
(e) This defines the function “show” for Trees and declares that BSTree k v in the Show class (as long as types k and v implement show).
Showing a tree shows the pairs of elements produced by tolist, separated by a newline.
Question 4
These both work. Intuitively, the difference is whether argmax is computed before f (in the original) or f is computed before argmax (in the new version).
[This is a question to test whether you can read and understand the code; the answer should be simple and obvious if you understand what is going on.]
-}
— sum_mem f lst mem = (sum [f e | e <- lst],mem1) but threads mem through f
-- so f can have side effects reflected in mem
sum_mem :: Num v => (e -> m -> (v,m)) -> [e] -> m -> (v,m)
sum_mem f [] mem = (0,mem)
sum_mem f (h:t) mem
= (fh+st,mem2)
where
(st,mem1) = sum_mem f t mem
(fh,mem2) = f h mem1
— Try (think about what it should return first):
— sum_mem (\ e m ->( e*2 ,(e^2:m))) [1,3,5,7,9] []
{-
Question 5
The answers are in the article!
-}