尾递归组合

Question

我有这样的代码：

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 

它看起来尾递归，但我不断收到堆栈溢出。任何想法如何使其工作？

Answer 1

combinations是尾递归。您的问题在于@运营商。用它附加一个列表迭代整个列表，所以当你的acc变大时，你会得到一个SO。

你可以看到here，即@运算符不是尾递归。未经优化的版本如下所示：let rec (@) x y = match x with [] -> y | (h::t) -> h :: (t @ y)。

为了解决这个问题，有两个选项：

1. 如果你不关心顺序，你可以写一个尾递归方法预先设置的结果是这样的：

   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. 如果您关心的是订单，您可以编写一个方法来首先反转列表，然后添加它。当然，这样做的缺点是它需要两倍的内存，因为你正在分配一个额外的列表来保存原始列表的反转版本。您可以重新使用以前的函数写是这样的：

   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]