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 a) @ l 之类的代码替换为 rev_append a l.

P.S。 pervasives.mli 中的 (@) 将在下一版本的 OCaml 中注释为 "not tail recursive"。

CPS归并排序导致栈溢出

CPS merge sort causes a stack overflow

ocaml

functional-programming