尾遞歸組合

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]