OCaml 中的尾递归合并排序

Question

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

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

您能帮我找出这段代码中的非尾递归调用吗？我找了很多，没有找到。难道是

sort

函数中的 let 绑定？

Answer 1

归并排序本质上不是尾递归。排序需要两次递归调用，并且在任何函数的任何执行中，最多一个动态调用可以位于尾部位置。 （

split

也可以从非尾部位置调用，但由于它应该使用恒定的堆栈空间，所以应该没问题）。

确保您使用的是最新版本的 OCaml。 在 3.08 及更早版本中，

List.rev

可能会破坏堆栈。该问题已在 3.10 版本中修复。使用版本 3.10.2，我可以使用您的代码对一千万个元素的列表进行排序。这需要几分钟，但我不会破坏堆栈。所以我希望您的问题只是因为您使用的是旧版本的 OCaml。

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

OCAMLRUNPARAM=b=1

当你销毁堆栈时，它将给出堆栈跟踪。

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

如果您需要对超过 1000 万个元素进行排序，也许您应该考虑不同的算法？或者，如果您愿意，您可以手动进行 CPS 转换合并排序，这将产生尾递归版本，但代价是在堆上分配连续性。但我的猜测是没有必要。

Answer 2

表情

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)