Some worked examples for G6021 Comparative Programming
1 Accumulating Parameters
For material about accumulating parameters, see Part 3 of the lecture notes. The aim is to convert a Haskell function into a tail recursive function: a function that does not have to do anything after a recursive call. To illustrate the idea, look at the usual definition of factorial:
fact n = if n==0 then 1 else n*fact(n-1)
After the recursive call (fact(n-1)) we still have to multiply by n. In fact we could see a trace of
the computation as something like this:
fact 3
3*(fact 2)
3*(2*(fact 1))
3*(2*(1*(fact 0))
3*(2*(1*1))
3*(2*1)
3*2
6
To make a version with an accumulating parameter, we accumulate the result:
factacc n acc = if n==0 then acc else factacc (n-1) (n*acc)
Here we multiply the accumulator by n¡ªimportant to start with the correct initial value of the accumulator, in this case 1. Note the type of the accumulating parameter version is not the same as the original function. Here is the trace of this version:
factacc 3 1
factacc 2 3
factacc 1 6
factacc 0 6
6
It¡¯s always worth testing to see if your new version gives the correct result!
Here are some exercises with solutions to practice this technique. Note that additional argu-
ments can be added in two different ways (cf. currying). Find tail recursive versions of the following functions:
1. len [] = 0
len (h:t) = 1+len(t)
Solution:
lenacc [] acc = acc
lenacc (h:t) acc = lenacc t (acc+1)
1
The starting value for acc should be 0.
2. power(x,y) = if y==0 then 1 else x*power(x,y-1)
Solution:
power(x,y,acc) = if y==0 then acc else power(x,y-1,x*acc) The starting value for acc should be 1.
3. positives nil = nil
positives (h:t) = if h<0 then positives t else h:positives t
Solution:
positives [] acc = acc
positives (h:t) acc = if h<0 then positives t acc else positives t (acc++[h])
The starting value for acc should be nil. Note the use of append in the accumulating parameter¡ªif we are not interested in the order of the elements, then we could write h:acc, which is much more efficient.
4. product [] = 1
product (h:t) = h*product(t)
Solution:
product [] acc = acc
product (h:t) acc = product t (h*acc)
The starting value for acc should be 1.
The above examples work with numbers and lists, but of course this technique can be applied to all recursive functions and work with all different data types. Try to write a function to add all the elements of a binary tree of numbers for example to get the flavour of this approach.
2