尾遞歸歸併排序OCaml中

Question

我想實現在OCaml的一個尾遞歸列表排序功能，我想出了下面的代碼：

let tailrec_merge_sort l = 
    let split l = 
    let rec _split source left right = 
     match source with 
     | [] -> (left, right) 
     | head :: tail -> _split tail right (head :: left) 
    in _split l [] [] 
    in 

    let merge l1 l2 = 
    let rec _merge l1 l2 result = 
     match l1, l2 with 
     | [], [] -> result 
     | [], h :: t | h :: t, [] -> _merge [] t (h :: result) 
     | h1 :: t1, h2 :: t2 -> 
      if h1 < h2 then _merge t1 l2 (h1 :: result) 
      else   _merge l1 t2 (h2 :: result) 
    in List.rev (_merge l1 l2 []) 
    in 

    let rec sort = function 
    | [] -> [] 
    | [a] -> [a] 
    | list -> let left, right = split list in merge (sort left) (sort right) 
    in sort l 
;; 

但它似乎實際上並不是尾遞歸的，因爲我遇到了「評估期間堆棧溢出（循環遞歸？）」的錯誤。

你能幫我看看這段代碼中的非尾遞歸調用嗎？我搜索了很多，沒有找到它。 Cout它是在sort函數中的let綁定？

Answer 1

表達

merge (sort left) (sort right) 

不是尾遞歸;它在遞歸調用（合併）中剩餘的工作時遞歸地調用（排序左）和（排序右）。

我想你可以用額外的延續參數修正：

let rec sort l k = 
    match l with 
    | [] -> k [] 
    | [a] -> k [a] 
    | list -> let left, right = split list in sort left (fun leftR -> sort right (fun rightR -> k (merge leftR rightR))) 
    in sort l (fun x -> x) 

Answer 2

合併排序本身是不是尾遞歸。一個排序需要兩個遞歸調用，並在任何執行任何函數，最多一個動態調用可以在尾部位置。 （split也從非尾位置調用，但是因爲它應該使用恆定的堆棧空間，所以應該可以）。

確保您使用的是最新版本的OCaml。在版本3.08及更高版本中，List.rev可能會堆棧。此問題在版本3.10中得到解決。使用版本3.10.2，我可以使用您的代碼對千萬個元素列表進行排序。這需要幾分鐘的時間，但我不會把堆棧炸開。所以我希望你的問題只是你有一箇舊版本的OCaml。

如果不是這樣，一個良好的下一步將設置可變

OCAMLRUNPARAM=b=1 

環境時，你吹的堆棧，這將給堆棧跟蹤。

我也想知道你正在排序的數組的長度;雖然合併排序不能是尾遞歸的，但它的非尾性質應該會讓你花費對數堆棧空間。

如果你需要排序超過1000萬個元素，也許你應該看看不同的算法？或者，如果你願意，你可以手動將CPS轉換爲mergesort，這將產生一個尾遞歸版本，其代價是在堆上分配contiuations。但我的猜測是，這不是必要的。