Week 8: tail recursion

There are three common types of function you can easily make tail-recursive.

1. As you go through an input list, you generate a list from the right. Example: reverse, because

   reverse [1; ...] = [...; 1]
   

2. As you go through an input list, you generate something else. Example: length, because

   length [1; ...] = 1 + length [...]
   

   This works because + is commutative, associative, and has a unit: x + y = y + x and x + (y + z) = (x + y) + z and 0 + x = x + x + 0.

3. As you go through an input list, you generate a list from the left. Example: duplicates, because

   duplicates [1; ...] = [1; 1; ...]
   

For all cases, we use an accumulator, which means a subresult variable. For reverse, the accumulator will be appended to the end; for length, it will be added, and for duplicates, it will be prepended in reverse. The accumulator variable is often spelled acc.

Let’s look at each case again.

Generate a list from the right

Our specification:

revap xs acc = rev xs @ acc

Example equations:

revap [1; 2; 3] [4; 5; 6]
= [3; 2; 1; 4; 5; 6]
= revap [2; 3] [1; 4; 5; 6]

revap [] [4; 5; 6] = rev [] @ [4; 5; 6] = [4; 5; 6]

You can implement revap tail-recursively yourself from these examples. Note that

revap [1; 2; 3] [] = rev [1; 2; 3]

so you can define rev in terms of revap:

let rev xs = revap xs []

Symmetric and commutative operator with a unit, such as +

Our specification:

length' xs acc = length xs + acc

Example equations:

length' [1; 2; 3] acc
= 3 + acc
= length' [2; 3] (1 + acc)

length' [] acc
= 0 + acc
= acc

You can implement length' tail-recursively yourself from these examples. Note that

length' [1; 2; 3] 0 = length [1; 2; 3]

so you can define length in terms of length':

let length xs = length' xs 0

Generate a list from the left

This one is a tad more complicated, but very useful in practice. Remember that dup [1; 2; 3] should be [1; 1; 2; 2; 3; 3]; a simple implementation is:

let rec dup xs = match xs with
  | [] -> []
  | x::xs' -> x :: x :: dup xs' ;;

Our specification:

dupprep xs acc = (rev acc) @ dup xs

dupprep stands for “duplicate-prepend”. (Note the rev!)

Example equations:

dupprep [1; 2; 3] [4; 5; 6]
= [6; 5; 4; 1; 1; 2; 2; 3; 3]
= dupprep [2; 3] [1; 1; 4; 5; 6]

dupprep [] [4; 5; 6] = [6; 5; 4] = rev [4; 5; 6]

You can implement dupprep tail-recursively yourself from these examples. Note that

dupprep [1; 2; 3] [] = dup [1; 2; 3]

so you can define dup in terms of dupprep:

let dup xs = dupprep xs []

Note

Sometimes, the normal functions don’t have one list argument, but many functions of various types. That doesn’t matter. You can use these schemes to make your tail recursion, no matter the number of arguments or their types. For instance, the tail-recursive version of sim_dif takes xs, ys, and an accumulator parameter. (See the sample solution for 7-3a.)

Examples

We have three schemes:

1. Generating a list from the right
2. Generating a sum starting from 0, or a product starting from 1, or ...
3. Generating a list from the left

Scheme A makes these functions tail-recursive: setify, rev, mklist (if you reorder the output), dif (if you reorder the output)

Scheme B makes these functions tail-recursive: sum, product, length, number of elements matching something, product of all elements matching something

Scheme C makes these functions tail-recursive: append, dif, sim_dif (the fast version), zip

Appendix

Find all the functions in the OCaml standard library here:

http://caml.inria.fr/pub/docs/manual-ocaml/stdlib.html

(go to www.ocaml.org → manual → Part IV → the standard library.)