G6021: Comparative Programming
Exam Practice
1. Consider the ¦Ë-term t = (¦Ëx.xx)(II), where I = ¦Ëx.x. (a) Give the definition of a ¦Â-reduction graph.
Answer: A graph showing all the possible reductions starting from the initial term.
(b) Draw the ¦Â-reduction graph of the term t.
Answer:
(¦Ëx.xx)(II)
c
(¦Ëx.xx)I
E (II)(II) I(II)
E II c
(II)I
I
(c) Which reduction strategy gives the shortest reduction sequence for reducing t to normal
form?
Answer: Call-by-value (or right-most reduction).
2. Give the types of the following:
(a) f(x) = if x>0 then True else False
(b) f(g,x) = g(g x)
(c) inf = inf+1
(d) \(x,y,z) -> x (y z)
Answer:
(a) Integer -> Bool (or (Num a) => a -> Bool) (b) (a -> a,a) -> a
(c) Integer
(d) (t1 -> t2, t -> t1, t) -> t2
3. Using list comprehension, write a Haskell expression that will generate Pythagorean triples (triple of numbers that satisfy Pythagoras¡¯ theorem: a2 + b2 = c2) for numbers up to 100.
Answer: A number of slight variants possible (for example (3,4,5) and (4,3,5) may be considered as the same triple). Full marks will be awarded in either case for a correct solution.
[(x,y,z) | x <-[1..100], y <-[1..100],
z <-[1..100], x^2+y^2 == z^2]
4. Using map and a one-off function (written using Haskell¡¯s lambda notation), write a function that will swap all pairs of a list of pairs of numbers. I.e. write a function f such that f [(1,2),(3,4)] = [(2,1),(4,3)].
1
'
'
2
E
E
Answer:
map (\(x,y) -> (y,x))
5. Convert the following function to accumulating parameter style. Include in your answer the type of the converted function.
fact (n) = if n<1 then 1 else n*(fact (n-1))
Answer:
fact2 (n,acc) = if n<1 then acc else fact2(n-1,n*acc) The type of fact2 is (Integer, Integer) -> Integer
6. Convert the following function to accumulating parameter style. Include in your answer the type of the converted function.
power(x,y) = if y==0 then 1 else x*power(x,y-1)
Answer:
power(x,y,acc) = if y==0 then acc else power(x,y-1,x*acc)
power :: (Integer, Integer, Integer) -> Integer
7. * Define add in PCF (a function that takes two arguments, and computes the sum of the arguments).
Answer: A starting point would be to write:
add x y = cond(iszero x) y (succ(add (pred x) y))
We can then write:
add = ¦Ëxy.cond(iszero x) y (succ(add (pred x) y))
Then let A = ¦Ëfxy.cond(iszero x) y (succ(f (pred x) y))
Now, since A add = add, we want a fixpoint of A, so the answer is fix A.
2