OCaml中的尾递归归并排序

Question

OCaml中的尾递归归并排序

8

我正在尝试在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绑定吗？

- Clément

2个回答

7

表达式

merge (sort left) (sort right)

这个函数不是尾递归的，因为在调用(merge)时，它同时递归调用(sort left)和(sort right)，直到调用中还有剩余的工作。

我认为你可以通过添加一个额外的continuation参数来解决这个问题：

  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)

- Brian

哦，我想我理解了，谢谢！但那么，我如何使我的函数成为递归的呢？ - Clément

2

你能否解释一下，为什么续延实际上可以使函数成为尾递归？或者它们只是将捕获栈帧的过程从（可能溢出的）堆栈移动到生成的闭包中？ - Dario

嗯，我猜这应该可以工作，但我不太明白k函数是做什么的。你能否解释一下？非常感谢！虽然我已经测试过了，但它并没有解决溢出问题... 有什么想法吗？ - Clément

我没有测试过代码，所以可能犯了错误。 :) 最好的续航策略解释在这里：http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!170.entry - Brian

这可能是Caml中尾递归优化的一个错误。无论如何，文档非常好，非常感谢！ - Clément

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Norman Ramsey · Accepted Answer

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

请确保您正在使用最新版本的OCaml。在3.08及更早版本中，List.rev可能会导致堆栈溢出。这个问题在3.10版本中得到了解决。使用3.10.2版本，我可以使用您的代码对包含一千万元素的列表进行排序。这需要几分钟时间，但我没有堆栈溢出。因此，我希望您的问题只是您使用的是旧版本的OCaml。

如果不是，请考虑设置环境变量。

OCAMLRUNPARAM=b=1

当堆栈溢出时，它将提供一个堆栈跟踪。

我也想知道您要排序的数组长度; 尽管合并排序无法是尾递归的，但其非尾递归性质应该会耗费您的对数级别的堆栈空间。

如果您需要排序超过1000万个元素，也许您应该考虑使用不同的算法？或者，如果您愿意的话，您可以手动进行CPS转换，这将产生一个尾递归版本，但代价是在堆上分配控制流。但我猜这是不必要的。