Is this F# function tail-recursive where the recursive function is called several times inside the function?

Question

There are a couple of questions about tail-recursive function e.g. this and this but could not find anything similar to the following.

My understanding is that a tail-call optimised function should return an accumulated value in its last call without any further evaluation. It's quite easy to understand using factorial function, for example, which get optimized into loops 2. But it not always obvious to tell in other cases e.g. in the following, what is that last call? There are many of them as the function is called recursively more than once in the body.

Brian suggests a way of finding out but I am not sure how to make it tail-call optimised. I can pass the --tailcalls flag to the compiler to do it automatically but does it always succeed?

f and g returns the same type.

type T = T of int * T list

let rec myfunc f (T (x,xs)) =
    if (List.isEmpty xs) then f x
    else 
        List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

Any help to tail-call optimise the above code would be much appreciated.

Answer 1

My understanding is that a tail-call optimised function should return an accumulated value in its last call...

Almost. Tail recursion is when recursive calls all appear in tail position. Tail position means the caller returns the result from its callee directly.

in the following, what is that last call?

There are two calls in tail position. First, the call to f. Second, the call to List.fold. The recursive call is not in tail position because its return value is not returned directly by its caller.

if (List.isEmpty xs) then f x

Also, use pattern matching instead of isEmpty and friends.

Any help to tail-call optimise the above code would be much appreciated.

You'll have to post working code or at least a specification before anyone will be able to help you write a tail recursive version. In general, the simplest solutions are either to write in continuation passing style or imperative style.

Answer 2

As Jon already said, your function is not tail-recursive. The basic problem is that it needs to call itself recursively multiple times (once for every element in the xs list, which is done in the lambda function passed to List.map).

In case when you actually need to make multiple recursive calls, using the continuation passing style or i.e. imperative stack are probably the only options. The idea behind continuations is that every function will take another function (as the last argument) that should be executed when the result is available.

The following example shows normal version (on the left) and continuation based (on the right)

let res = foo a b                          fooCont a b (fun res ->
printfn "Result: %d" res                     printfn "Result: %d" res)

To write your function in a continuation passing style, you'll need to use a continuation-based fold function too. You can first avoid using map by moving the operation done in map into the lambda function of fold:

List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

Becomes:

List.fold (fun state xxs -> g state (myfunc f xxs)) acc xs

Then you can rewrite the code as follows (Note that both f and g that you did not show in your question are now continuation-based functions, so they take additional argument, which represents the continuation):

// The additional parameter 'cont' is the continuation to be called 
// when the final result of myfunc is computed
let rec myfunc' f (T (x,xs)) cont = 
  if (List.isEmpty xs) then 
    // Call the 'f' function to process the last element and give it the
    // current continuation (it will be called when 'f' calculates the result)
    f x cont
  else  
    // Using the continuation-based version of fold - the lambda now takes current
    // element 'xxs', the accumulated state and a continuation to call
    // when it finishes calculating 
    List.foldCont (fun xxs state cont -> 
      // Call 'myfunc' recursively - note, this is tail-call position now!
      myfunc' f xxs (fun res -> 
        // In the continuation, we perform the aggregation using 'g'
        // and the result is reported to the continuation that resumes
        // folding the remaining elements of the list.
        g state res cont)) acc xs cont

The List.foldCont function is a continuation-based version of fold and can be written as follows:

module List = 
  let rec foldCont f (state:'TState) (list:'T list) cont =
    match list with
    | [] -> cont state
    | x::xs -> foldCont f state xs (fun state ->
        f x state cont)

Since you did not post a complete working example, I could not really test the code, but I think it should work.