points
bigger two three
∗
Ô⇒
∗
Ô⇒
S (S (S E))
bigger three two
S (S (S E))
Please write the following recursive functions on the Numb type:
(1) a. times :: Numb -> Numb -> Numb which computes the product of two
numbers using the existing add function.
Example usage:
times two three Ô⇒∗ S (S (S (S (S (S E))))) times E three Ô⇒∗ E
b. equal :: Numb -> Numb -> Bool which returns True if the two numbers
given are equal and False otherwise.
Example usage: equal two three Ô⇒∗ False equal two two Ô⇒∗ True
c. bigger :: Numb -> Numb -> Numb which takes two numbers and returns
the larger one.
Example usage:
15 points
Please write the following recursive functions on lists:
(2) a. count :: (a -> Bool) -> [a] -> Numb which returns the number of el-
ements in the given list for which the given function returns True.
Example usage:
count (\x -> x > 3) [2,5,8,11,14]
∗
Ô⇒
S (S (S (S E)))
count isOne [one, one, two, three]
∗
Ô⇒
S (S E)
count not [True, False, True, True] Ô⇒∗ S E
b. remove :: (a -> Bool) -> [a] -> [a] such that remove f l returns a list which is just like l but with those elements removed for which f returns True.
Example usage: remove (\x -> x > 3) [2,5,8,11,14] Ô⇒∗ [2]
remove isOne [one, one, two, three] Ô⇒∗ [S (S E), S (S (S E))] remove not [True, False, True, True] Ô⇒∗ [True ,True ,True]
c. prefix :: Numb -> [a] -> [a] such that prefix n list returns the
list containing the first n elements of list; or if n is greater than the length of list, returns list as is. (Hint: The function will need to work
recursively on both arguments.)
Example usage: prefix one [2,5,8] Ô⇒∗ [2] prefix two [2,5,8] Ô⇒∗ [2,5] prefix four [2,5,8] Ô⇒∗ [2,5,8]
3 10 points
The structure of WFF expressions from the previous assignment can be represented as tree structures, as illustrated below:
(3) Conj Neg
T F
T F
Please write a function depth :: WFF -> Numb which returns the length of the longest root-to-leaf sequence of nodes in the tree for the given WFF, i.e. the depth of the most deeply-embedded leaf of the tree. The bigger function that you wrote above will be useful here.
For example, with the WFF trees in (3), depth should return two, three, and four respectively (as Numb expressions).
