Are list comprehensions with for and yield! tail-recursive in F#?

Question

I wrote this little function, I'll repeat it here for ease-of-reference:

/// Take a list of lists, go left-first, and return each combination,
/// then apply a function to the resulting sublists, each length of main list
let rec nestedApply f acc inp =
    match inp with
    | [] -> f acc
    | head::tail -> 
        [
            for x in head do
                yield! nestedApply f (x::acc) tail
        ]

It made me wonder whether using yield! in this context, or in general with list comprehensions, is tail-recursive. I actually think it isn't, which makes that the above function would create a stack-depth equal to the size of the main list.

If it isn't, how can I write this same code in a tail-recursive way? I've tried with List.collect (a rolled out idea is in the referred-to question), but I didn't quite get there.

Answer 1

To simplify things I am going to separate the multiplication of lists from the mapping of the function. So nestedApply will look like this:

let nestedApply f lsts = mult lsts |> List.collect f

Where mult does the multiplication of the lists and returns all the combinations.

I usually find that to do tail recursion is better to start with the simple recursion first:

let rec mult lsts =
    match lsts with
    | [ ]       ->  [[]]
    | h :: rest ->  let acc = mult rest
                    h |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 

So this version of mult does the job but it does not use tail recursion. It does serves as a template to create the tail recursion version and I can check that both return the same value:

let mult lsts =
    let rec multT lsts acc =
        match lsts with
        | h :: rest -> h 
                       |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
                       |> multT rest
        | [ ]       -> acc
    multT (List.rev lsts) [[]]

The tail recursion version multT uses an internal accumulator parameter. To hide it, I nest the recursive part inside the function mult. I also reverse the list because this version works backwards.

Many times when you have a tail recursive function you can eliminate the recursion by using the fold function:

let mult lsts  = 
    List.rev lsts 
    |> List.fold  (fun acc h -> 
           h 
           |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
         ) [[]]

or foldBack:

let mult lsts =
    List.foldBack (fun h acc -> 
        h 
        |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
      ) lsts [[]]

Notice the similarities.

Here is the solution in fiddle:

https://dotnetfiddle.net/sQOI7q

Answer 2

No, it's not tail-recursive, and will in fact blow up the stack:

let lists = 
    [1 .. 10000]
    |> List.map (fun i -> List.replicate 100 i)

nestedApply id [] lists

You could make nestedApply tail-recursive by rewriting it in continuation-passing style, but isn't it just an n-ary cartesian product followed by a map?