2010-03-27 23 views
8

我想實現在OCaml的一個尾遞歸列表排序功能,我想出了下面的代碼:尾遞歸歸併排序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綁定?

回答

7

表達

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) 
+0

哦,我想我明白了;謝謝!但是,如何讓我的函數遞歸? – 2010-03-27 14:50:28

+1

你能解釋爲什麼延續實際上使函數尾遞歸?或者他們只是將從棧(可能是溢出的)棧中捕獲棧幀的過程移動到生成的閉包? – Dario 2010-03-27 16:09:51

+0

嗯,我想這應該起作用,但我並不真正瞭解k功能的作用。你能解釋一下嗎?非常感謝! 雖然我已經測試過,但它並沒有解決溢出問題......任何想法爲什麼? – 2010-03-27 16:56:33

9

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

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

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

OCAMLRUNPARAM=b=1 

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

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

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

+0

嗯,由於拆分不在最後位置,它是否算數? (我的意思是,據我瞭解,編譯器應該能夠檢測到尾遞歸函數並將其轉換爲循環;然後,只有最後一次調用會很重要)。此外,使用延續應該使函數尾遞歸,shouldn是嗎? – 2010-03-29 18:17:53

+0

我正在使用OCaml v11.0,並且在10^6元素上運行我的代碼時,我吹出了堆棧。我需要分類500萬到1000萬個元素。 – 2010-03-29 18:19:41

+0

最後,我的問題是,即使使用continuations,我也吹了堆棧。任何想法爲什麼? – 2010-03-29 18:20:03