OCaml中的尾递归合并排序

I’m trying to implement a tail-recursive list-sorting function in OCaml, and I’ve come up with the following code:

我正在尝试在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
;;

Yet it seems that it is not actually tail-recursive, since I encounter a "Stack overflow during evaluation (looping recursion?)" error.

然而它似乎实际上并不是尾递归，因为我遇到了“评估期间的堆栈溢出（循环递归？）”错误。

Could you please help me spot the non tail-recursive call in this code? I've searched quite a lot, without finding it. Cout it be the let binding in the sort function?

你能帮我看看这段代码中的非尾递归调用吗？我没有找到它，搜索了很多。 Cout它是sort函数中的let绑定？

2 个解决方案

#1

The expression

表达方式

merge (sort left) (sort right)

is not tail-recursive; it calls both (sort left) and (sort right) recursively while there is remaining work in the call (merge).

不是尾递归的;当调用（合并）中有剩余工作时，它会递归调用（sort left）和（sort right）。

I think you can fix it with an extra continuation parameter:

我认为您可以使用额外的延续参数来修复它：

  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)

#2

Merge sort is inherently not tail-recursive. A sort requires two recursive calls, and in any execution of any function, at most one dynamic call can be in tail position. (split is also called from non-tail position, but since it should use constant stack space that should be OK).

合并排序本质上不是尾递归。排序需要两个递归调用，并且在任何函数的任何执行中，最多一个动态调用可以处于尾部位置。（也可以从非尾部位置调用split，但因为它应该使用常量堆栈空间，应该没问题）。

Be sure you are using a recent version of OCaml. In versions 3.08 and older, List.rev could blow the stack. This problem is fixed in version 3.10. Using version 3.10.2, I can sort a list of ten million elements using your code. It takes a couple of minutes, but I don't blow the stack. So I'm hoping your problem is simply that you have an old version of OCaml.

请确保您使用的是最新版本的OCaml。在版本3.08及更早版本中，List.rev可能会破坏堆栈。此问题已在3.10版中得到修复。使用版本3.10.2，我可以使用您的代码对包含一千万个元素的列表进行排序。这需要几分钟，但我不会吹嘘。所以我希望你的问题只是你有一个旧版本的OCaml。

If not, a good next step would be to set the environment variable

如果没有，下一步是设置环境变量

OCAMLRUNPARAM=b=1

which will give a stack trace when you blow the stack.

当你吹掉堆栈时会给出堆栈跟踪。

I'd also like to know the length of the arrays you are sorting; although merge sort cannot be tail-recursive, its non-tail nature should cost you logarithmic stack space.

我还想知道你要排序的数组的长度;虽然合并排序不能是尾递归，但它的非尾部性质应该花费你对数堆栈空间。

If you need to sort more than 10 million elements, maybe you should be looking at a different algorithm? Or if you want, you could CPS-convert mergesort by hand, which will yield a tail-recursive version at the cost of allocating contiuations on the heap. But my guess is that it won't be necessary.

如果你需要排序超过1000万个元素，也许你应该看一个不同的算法？或者如果你愿意，你可以手动CPS转换mergesort，这将产生一个尾递归版本，代价是在堆上分配contiuations。但我的猜测是没有必要。

#1