— CPSC 312 Midterm 2 2019
— You may have to do
— cabal install hashable –lib
import Data.Hashable
mtr a b c = 100*a + 10*b +c
{– Question 1
Prelude> :type flip
flip :: (a -> b -> c) -> b -> a -> c
Prelude> mtr (flip 2 4) 6
Error because 2 is not a function
Prelude> flip mtr 2 4 6
426
Prelude> flip (mtr 2) 4 6
264
–}
{– Question 2
(a)
regularize a:b:r means
(regularize a):b:r
Fix:
regularize (a:b:r)
(b)
regularize b:r
means
(regularize b):r
Fix
regularize (b:r)
(c) regularize is stated to work for all types, but / is only defined for Fractional types
Fix: regularize :: Fractional t => [t] -> [t]
(d) It can get a runtime error if given a list of one argumment
Fix: add
regularize [a] = [a]
–}
data Tree t = Leaf t | Node (Tree t) (Tree t)
mytree = Node (Leaf 1) (Node (Leaf 3) (Node (Leaf 5) (Leaf 2)))
— foo is foldr for trees
foo f v (Leaf l) = f l v
foo f v (Node t1 t2) = foo f (foo f v t2) t1
{-
*Main> :type foo
foo :: (t -> p -> p) -> p -> Tree t -> p
*Main> foo (+) 0 mytree
11
*Main> foo (:) [] mytree
[1,3,5,2]
-}
— Question 4
data Set t = SEmpty
| SNode t (Set t) (Set t)
deriving (Read, Show)
— t is the type of the elements of the set
— Eq t is needed because we test elements with ==
— Hashable t is needed because we call hash on elements of the list
member _ SEmpty = False
member v (SNode e lt ut)
| v==e = True
| hash v <= hash e = member v lt
| otherwise = member v ut
insert :: (Eq t, Hashable t) => t -> Set t -> Set t
insert e SEmpty = SNode e SEmpty SEmpty
insert e (SNode r lt rt)
| e==r = (SNode r lt rt)
| hash e <= hash r = SNode r (insert e lt) rt
| otherwise = SNode r lt (insert e rt)