f# - f Sharp 的合并排序

Question

这是我的代码，当我输入一个非常大的数字时，我得到堆栈溢出错误有人知道为什么吗？当我输入一个非常大的数字时，我得到了那个错误，我不确定是什么原因造成的，只有大数字才能正常工作.....

//
// merge two sorted lists into one:
//
let rec merge L1 L2 = 
  if L1 = [] && L2 = [] then
    []
  else if L1 = [] then
    L2
  else if L2 = [] then
    L1
  else if L1.Head <= L2.Head then
    L1.Head :: merge L1.Tail L2
  else
    L2.Head :: merge L1 L2.Tail

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

Answer 1

在您的两个函数中，您都遇到了问题，您采取的最后一步不是递归调用，而是其他一些事情:

• 在merge中是::操作
• 在 mergesort 中是 merge

所以你必须达到最后一件事就是递归调用的地步!

在你有多个递归调用的情况下，一种可能性是使用 continuations - 这个想法是传递一个函数，应该使用当前步骤的结果调用该函数，然后从那里继续计算。

这是 尾递归 版本的 mergesort 使用这种技术:

let mergesort xs = 
    let rec msort xs cont = 
        match xs with
        | []    -> cont []
        | [x]   -> cont xs
        | _     -> 
            let mid = List.length xs / 2
            let (xs', xs'') = List.splitAt mid xs
            msort xs' (fun ys' -> msort xs'' (fun ys'' -> cont (merge ys' ys'')))
    msort xs id

正如你所看到的，这个想法并不难——而不是首先调用两个递归路径，它只从一半开始，但添加了一个延续，基本上说:

once I have the result of mergesort xs' I take the result ys' and continue by mergesorting xs'' and then merge those

当然第二步也是一样的(把merge插入continuation)

第一个延续通常是你在最后一行看到的标识；)

---

你的 merge 也有类似的东西:

let merge xs ys = 
    let rec mrg xs ys cont =
        match (xs, ys) with
        | ([], ys) -> cont ys
        | (xs, []) -> cont xs
        | (x::xs', y::ys') ->
            if x < y 
            then mrg xs' ys (fun rs -> cont (x::rs))
            else mrg xs ys' (fun rs -> cont (y::rs))
    mrg xs ys id

---

这些当然会在堆上占用尽可能多的空间(可能更多)——但这通常没问题——你的堆栈应该没问题；)