Tail Recursive Combinations
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?
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 (@) xy = match x with [] -> y | (h::t) -> h :: (t @ y) let rec (@) xy = match x with [] -> y | (h::t) -> h :: (t @ y) .
To get around this problem, there are a couple of options:
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]
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]
上一篇: 尾递归究竟如何工作？
下一篇: 尾递归组合