Do the tail-recursive version of the length function saves stack space at run-time?

Question

I am asked to change this F# length function to a tail-recursive one.

let rec len xs = 
  match xs with 
    | [] -> 0 
    | x::xr -> 1 + len xr;;

While this is not a difficult exercise, I wonder whether changing to the tail-recursive version, such as the one below,

let rec leni xs r = 
  match xs with 
    | [] -> r 
    | x::xr -> leni xr r+1;;

indeed saves stack space at run-time compared with the non-tail-recursive one?

Answer 1

Tail-recursive functions are compiled into a loop, they don't use any additional stack dependent on the number of iterations.

Alas, your version is not tail-recursive, as you have the precedence of the operator wrong. The accumulator r is interpreted as belonging to the recursive call, to which it is passed unchanged. Thus the function needs to return to have its return value incremented.

Let's see:

let rec len xs = 
  match xs with 
    | [] -> 0 
    | x::xr -> 1 + len xr;;

let rec leni xs r = 
  match xs with 
    | [] -> r 
    | x::xr -> leni xr r+1;;

[0..10000] |> len     // val it : int = 10001
[0..100000] |> len    // val it : int = 100001
[0..1000000] |> len   // Process is terminated due to StackOverflowException.

([0..1000000], 0) ||> leni   // Process is terminated due to StackOverflowException.

The fix is simply to enclose the new accumulator value in parens, adding 1 to it.

let rec leni' xs r = 
  match xs with 
    | [] -> r 
    | x::xr -> leni' xr (r+1)

([0..1000000], 0) ||> leni'   // val it : int = 1000001

You can go further and use Continuation Passing Style (CPS), replacing the accumulator with composed functions, each adding 1 to its argument. This would also compile into a loop and preserve stack space, at the expense of memory needed for storage of the chain of functions.

Also, you could rethink the order of the arguments: having the accumulator (or continuation) first and the list last allows for use of the function keyword.

let rec lenk k = function
| [] -> k 0 
| x::xr -> lenk (k << (+) 1) xr

[0..1000000] |> lenk id      // val it : int = 1000001