CPS合并排序会导致堆栈溢出。

Question

由于非尾递归导致堆栈溢出问题，所以我使用了连续排序，从而使大列表的排序成为可能。

我以这种方式实现了排序(您可以在这里看到整个代码：http://paste.ubuntu.com/13481004/)

let merge_sort l =
    let rec merge_sort' l cont =
        match l with
        | [] -> cont []
        | [x] -> cont [x]
        | _ ->
            let (a,b) = split l
            in
                merge_sort' a
                    (fun leftRes -> merge_sort' b
 (* OVERFLOW HERE *)                (fun rightRes -> cont (merge leftRes rightRes) )
                    )
    in merge_sort' l (fun x -> x)

尽管如此，我还是会在指定的行中看到堆栈溢出。我做错了什么？

Answer 1

OCaml标准库的(@)不是尾递归的。代码中的merge函数http://paste.ubuntu.com/13481004/使用(@)，这是堆栈溢出的原因。

list.mli说：

val append : 'a list -> 'a list -> 'a list
(** Catenate two lists.  Same function as the infix operator [@].
   Not tail-recursive (length of the first argument).  The [@]
   operator is not tail-recursive either. *)

但不幸的是，这一事实并不是在pervasives.mli中编写的，因为(@)是真正声明的：

val ( @ ) : 'a list -> 'a list -> 'a list
(** List concatenation. *)

这是不好的:-(我已经在OCaml开发页面上提出了一个问题。

我将(@)重新定义为fun x y -> rev_append (rev x) y，然后代码运行w/o堆栈溢出。更优雅的是，您可以用rev_append a l替换像rev_append a l这样的代码。

在下一个版本的(@)中，pervasives.mli中的P.S. OCaml将被注释为“非尾递归”。