F# 合并排序尾递归

Question

我尝试编写一个尾递归的归并排序代码。这个代码编译和运行都没问题。但是，输出结果是错误的，只输出一个整数。请问我应该如何修改这个代码，以便对整数列表进行排序并输出正确结果。

let rec merge L L2 P = 
  match L, L2 with
  | [], [] -> P
  | [], _  -> L2
  | _,  [] -> L
  | hd::t1, hd2::t2 ->
    if hd <= hd2 then
       merge t1 L2 (P @ [hd])
    else
       merge L t2 (P @ [hd2])


//
// mergesort:
//
let rec ms L  = 
  match L with
  | []    -> []
  | e::[] -> L
  | _     -> 
    let mid = List.length L / 2
    let (L, L2) = List.splitAt mid L
    merge (ms L) (ms L2) []

- Shiro Pie

---

“merge” 对我来说有点可疑 - 当且仅当一个列表为空时，P 不会影响输出。 - kvb

Answer 1

您的问题出在merge函数中：想象一下您对列表[2;1]进行排序。它变成了merge [2] [1] []，然后变成merge [] [2] [1]，最后match的第二个情况得到了[2]。match的第二个和第三个情况必须以某种方式考虑P。

实际上，在merge中您完全不需要操纵3个列表，如果我们将其重构为两个列表，则足矣：

let rec merge l1 l2 =
    match (l1,l2) with
    | (x,[]) -> x
    | ([],y) -> y
    | (x::tx,y::ty) ->
        if x <= y then x::merge tx l2
        else y::merge l1 ty 

将ms的最后一行改为merge(ms L)(ms L2)，这个变量的确按预期工作：

ms List<int>.Empty 返回 []

ms [2;1] 返回 [1;2]

等等

更新：正如@kvb指出的那样，上面的merge函数不是尾递归的。这是正确的，重构成尾递归版本需要更多涉及，需要引入一个累加器acc，通过continuation函数来填充它：

let merge l1 l2 =
  let rec mergeAux continuation l1 l2 = 
    match l1, l2 with
    | l1, [] -> continuation l1
    | [], l2 -> continuation l2
    | x::tx, y::ty ->
      if x <= y then mergeAux (fun acc -> continuation(x::acc)) tx l2
      else mergeAux (fun acc -> continuation(y::acc)) l1 ty
  mergeAux id l1 l2

现在的实现是尾递归的，可以通过以下方式轻松检查：

let rand = System.Random() in
    List.init 1000000 (fun _ -> rand.Next(-10000,10000)) |> ms
>
val it : int list =
  [-10000; -10000; -10000; -10000; -10000; -10000; -10000; ...

- Gene Belitski

---

请注意，您的merge版本不再是尾递归。 - kvb

好的发现，@kvb，已更新答案。谢谢你，Keith！ - Gene Belitski

Answer 2

即使对接受的答案进行了更改，您仍然没有尾递归合并排序。 归并排序的最后一行 merge (ms L) (ms L2) 调用了 ms 两次，然后调用了 merge。 为使函数成为尾递归函数，该函数必须以最多一次递归调用本身结束。 这种情况需要使用延续。 通过传递延续，您可以执行一次对 ms 的调用，并将其传递给一个延续，该延续使第二次对 ms 的调用并将该第二次调用传递给另一个延续，该延续使调用 merge。 实际上，我会从 merge 函数中删除延续，因为它是不必要的，而且使用累加器参数实现它比阅读代码更容易。 最后，为了方便外部调用，我会将 merge 函数以及 ms 函数嵌套在一个只带有一个列表参数的 mergeSort 函数中，不需要向调用者公开其余详细信息。 我在 F# 中实现的完全尾递归合并排序如下：

let mergeSort ls =
    let rec merge l1 l2 res = 
        match l1, l2 with
        | [], [] -> res |> List.rev
        | x::xs, [] -> merge xs [] (x::res)
        | [], y::ys -> merge [] ys (y::res)
        | x::xs, y::ys when x < y -> merge xs (y::ys) (x::res)
        | xs, y::ys -> merge xs ys (y::res)

    let rec ms ls cont =
        match ls with
        | [] -> cont []
        | [x] -> cont [x]
        | xs ->
            let ys, zs = List.splitAt ((List.length xs) / 2) xs
            ms ys (fun ys' -> ms zs (fun zs' -> cont (merge ys' zs' [])))
    ms ls id

请注意，有一些更有效地使用内存的方法，这可能也会因为较少的内存分配而提高速度，但由于这超出了此问题的范围，我不打算在答案中讨论这个问题。

- Jesse