Week 7: tail recursion

We first recapped what tail recursion is.

Then we recapped how to do sum tail-recursively, namely by writing a function sum' that accumulates the “sum so far”: sum' xs n = n + sum xs.

Then we recapped how to do rev tail-recursively, namely by writing a function revap that accumulates the “rev so far”: revap xs ys = rev xs @ ys.

Then we did duplicates.

Dan wrote this on Facebook:

A follow-on to Bram’s tutorial where he started to discuss the dup function (which duplicates all elements in a list as in dup [1;2;3] = [1;1;2;2;3;3]) and its tail-recursive implementation. Note that in a tail-recursive implementation the ‘accumulator’ where you store the result will grow to the left and the ‘obvious’ implementation of dup will end up with the list in reverse order:

let rec dup' xxs = function
| [] -> xxs
| x :: xs -> dup' (x :: x :: xxs) xs
    # dup' [] [1;2;3] ;;
- : int list = [3; 3; 2; 2; 1; 1]

The obvious solution is to simply reverse the list produced by dup’:

let dup xs = xs |> dup' [] |> List.rev
# dup [1;2;3;4] ;;
- : int list = [1; 1; 2; 2; 3; 3; 4; 4]

This may seem like wasteful and inefficient but remember that reversing a list, also a tail-recursive operation, is in fact very fast and dup will be quite efficient. Not as efficient as the non-tail-recursive implementation:

let rec dupn = function
    | [] -> []
| x :: xs -> x :: x :: dupn xs

But in the same ballpark, with the advantage of tail recursion!

(* benchmarking *)
let rec mkrlist xs = function
| 0 -> xs
| n -> mkrlist (Random.bits () :: xs) (n-1)
let bm f n =
let l = mkrlist [] n in
let t0 = Sys.time () in
let _ = f l in
let t1 = Sys.time () in
print_float (t1 -. t0); print_newline ()
# bm dupn 100000;;
0.028933
- : unit = ()
# bm dup 100000;;
0.037415
- : unit = ()
# bm dupn 1000000;;
Stack overflow during evaluation (looping recursion?).
# bm dup 1000000;;
0.299246
- : unit = ()

Bram added:

Great explanation, thanks!

To do it equation-style, dup' is doing

dup' xxs ys = rev (dup ys) @ xxs

and an example equation we have is

dup' [1; 2; 3] [4; 5; 6]
= rev (dup [4; 5; 6]) @ [1; 2; 3]
= rev (4 :: 4 :: dup [5; 6]) @ [1; 2; 3]
= rev ([4; 4] @ dup [5; 6]) @ [1; 2; 3]
= rev (dup [5; 6]) @ [4; 4] @ [1; 2; 3]
= rev (dup [5; 6]) @ [4; 4; 1; 2; 3]
= rev (dup [5; 6]) @ (4 :: 4 :: [1; 2; 3])
= dup' (4 :: 4 :: [1; 2; 3]) [5; 6]

so we know

dup' xxs (y::ys) = dup' (y :: y :: xxs) ys

and this is how Dan made the tail-recursive implementation of dup'. To find dup xs for any xs, just compute rev (dup xs) @ [] which is just rev (dup xs), and re-reverse the result.

As with sum and rev in the tutorial, we first make a more complicated version (sum', revap, dup') so we can make an efficient version of the simple thing (sum, rev, dup).

Note: the arguments are in a different order than in the actual tutorial, I think.