CPSC 349 Exercise 3 Solution

gcd (9, 24)
   = gcd (24, 9)
   = gcd (9, 6)
   = gcd (6, 3)
   = gcd (3, 0)
   = 3

For any odd-valued parameter n, the if test will fail, resulting in a recursive call to ftest (2 * n + 1). But since n is odd, then 2n + 1 is also odd (since ∀k, 2k is even), and we encounter yet another recursive call, and so on. Examples would be n = 1, where ftest 1 = ftest 3 = ftest 7 = ...; n = 5, where ftest 5 = ftest 11 = ftest 23 = ...; and so on.
Any even-valued parameter will cause the if test to succeed, and the function will terminate.

(a)


orderit [4, 3, 6, 1]
   = [6] ++ (orderit [4, 3, 1])
   = [6] ++ ([4] ++ (orderit [3, 1]))
   = [6] ++ ([4] ++ ([3] ++ (orderit [1])))
   = [6] ++ ([4] ++ ([3] ++ ([1] ++ (orderit []))))
   = [6] ++ ([4] ++ ([3] ++ ([1] ++[])))
   = [6, 4, 3, 1]

(b)
Since 'c' > 'b' > 'M', then "cat" > "bet" > "Mut" and so by lines {5} and {6}, the maximum element of the list each time through is "cat" followed by "bet" followed by "Mut". Therefore:


orderit ["bet", "cat", "Mut"] = ["cat", "bet", "Mut"]

(c)
We note that the elements of the list 3, "dog" and 2.5 are not of a common type, and cannot be promoted to any one common type, therefore this violates line {1} in the listing for orderit which claims that "orderit :: Ord a => [a] -> [a]" takes a list containing variables of a common type a. We can find no such a that satisfies the given expression.

doit = (\x -> (\y -> (x ^ y)))

(a)


(b)
x: bound everywhere
y: bound everywhere
z: free everywhere