2010-03-27 124 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