Tail Recursive Combinations

1
votes

I have this code:

    let rec combinations acc listC = 
        match listC with
        | [] -> acc 
        | h::t ->
            let next = [h]::List.map (fun t ->  h::t) acc @ acc
            combinations next t

It looks tail recursive, but I keep getting stack overflows with it. Any ideas on how to make it work?

1
f#tail-recursion
you get stack-overflows where? FSI?, Mono? - You enabled the TCO? - Random Dev
Can you show IL generated from this code? - Fyodor Soikin
this should be tail-recursive - most likely you either did not enable TCO or the problem is somewhere else - btw: how big is the list you start with? Maybe you should consider switching to seqs - Random Dev
I've used it in two places, one as an .xll with ExcelDNA, and second as server side function in websharper (debug) - Jeremiah Jeschke

1 Answers

4
votes

combinations is tail recursive. Your problem is with the @ operator. Appending a list with it iterates the whole list, so as your acc becomes large, you will get a SO.

You can see here, that the @ operator is not tail recursive. The non-optimized version looks like: let rec (@) x y = match x with [] -> y | (h::t) -> h :: (t @ y).

To get around this problem, there are a couple of options:

  1. If you don't care about order, you could write a tail-recursive method to prepend the result like this:

    let rec prepend lst1 lst2 = match lst1 with | [] -> lst2 | head::tail -> prepend tail (head::lst2)

> prepend [1;2;3;4] [5;6;7;8];; 
val it : int list = [4; 3; 2; 1; 5; 6; 7; 8]

  1. If you care about order, you could write a method to first reverse the list and then prepend it. The drawback of this, of course, is that it will require twice as much memory since you are allocating an additional list to hold the reversed version of the original list. You can reuse the previous function to write something like this:

    let prepend2 lst1 lst2 = prepend (prepend lst1 []) lst2

> prepend2 [1;2;3;4] [5;6;7;8];; 
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8]