为什么这个 SML mergeSort 函数不是 return 排序列表？

Question

它最终什么也没返回。此外，当运行时，它表示它是：

- val merge_sort = fn : ('a * 'a -> bool) -> 'b list -> 'a list

当我知道应该是这样的：

- val merge_sort = fn : ('a * 'a -> bool) -> 'a list -> 'a list

函数：

fun merge_sort f = 
    let
        fun merge(nil, ylist) = ylist
        |   merge(xlist, nil) = xlist
        |   merge(x::xend, y::yend) =
        if f (x,y) then
            x::merge(xend, y::yend)
        else
            y::merge(x::xend, yend)

        fun split nil = (nil, nil) 
        |   split [x] = ([x], nil)
        |   split (x::y::xy) = 
            let 
                val (low, up) = split xy
            in 
                (x::low, y::up)
            end

    in
        let
            fun real nil = nil
            | real L = 
                let
                    val (list1,list2) = split L
                in
                    merge (real list1,real list2)
            end
        in
             fn last => real last
        end
    end;

 merge_sort (op >) [0, 5, 1, ~4, 9, 11]

Answer 1

由于这是一个调试问题，下面是我可能会如何查找问题：

首先，我运行程序并意识到它抛出 Out_of_memory 异常。所以我知道正在进行一些无限递归。在某个地方，递归调用应该会遇到基本情况，但事实并非如此，而是它会调用自身，直到最终运行内存不足。

该函数由多个辅助函数组成。看看它们是否都按预期工作。

因为merge是作为merge_sort的内部函数嵌入的，所以很难单独测试，因为你不能直接引用它，如果你把它移出来，它会失败进行编译，因为它需要来自其父作用域的比较函数 f。因此，出于可测试性目的，我将稍微更改 merge。

split函数不需要类似的修改，而real函数似乎没有必要，因为它只是合并排序函数； let 中的 let 似乎也没有必要，但由于我将所有辅助函数移出，因此无论如何都会将其删除。所以我要删除 real 并将其命名为 mergeSort.

结果（将 nil 额外重命名为 [] 等等，这只是我的偏好）：

fun merge p ([], ys) = ys
  | merge p (xs, []) = xs
  | merge p (x::xs, y::ys) =
      if p (x,y) then
        x::merge p (xs, y::ys)
      else
        y::merge p (x::xs, ys)

fun split [] = ([], [])
  | split [x] = ([x], [])
  | split (x::y::xys) =
    let
      val (lo, hi) = split xys
    in
      (x::lo, y::hi)
    end

fun mergeSort p [] = []
  | mergeSort p zs =
    let
      val (xs, ys) = split zs
    in
      merge p (mergeSort p xs, mergeSort p ys)
    end

对此进行测试，它仍然会抛出 Out_of_memory 错误，所以我实际上并没有修复任何东西。

让我们尝试运行手动输入少量数据；

下面以 = 开头的每一行都表示一个术语重写，我用它的定义替换了前一个表达式的某些部分。例如，作为起点的 mergeSort (op >) [1,2,3] 在模式匹配 [1,2,3].

mergeSort

以 `- 开头的每一行都是我尝试扩展表达式的子部分，而不将其包含在上述表达式的全部重写中——否则可能会有点乱。

  mergeSort (op >) [1,2,3]
= let val (xs, ys) = split [1,2,3] in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
   `-   split [1,2,3]
      = let val (lo, hi) = split [3] in (1::lo, 2::hi) end
      = let val (lo, hi) = ([3], []) in (1::lo, 2::hi) end
      = (1::[3], 2::[])
      = ([1,3], [2])
= let val (xs, ys) = ([1,3], [2]) in merge (op >) (mergeSort p xs, mergeSort p ys) end
= merge (op >) (mergeSort (op >) [1,3], mergeSort (op >) [2])
   `-   mergeSort (op >) [1,3]
      = let val (xs, ys) = split [1,3] in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
         `-   split [1,3]
            = let val (lo, hi) = split [] in (1::lo, 3::hi) end
            = let val (lo, hi) = ([], []) in (1::lo, 3::hi) end
            = (1::[], 3::hi)
            = ([1], [3])
      = let val (xs, ys) = ([1], [3]) in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
      = merge (op >) (mergeSort (op >) [1], mergeSort (op >) [3])
         `-   mergeSort (op >) [1]
            = let val (xs, ys) = split [1] in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
            = let val (xs, ys) = ([1], []) in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
            = merge (op >) (mergeSort (op >) [1], mergeSort (op >) [])
               `- OOPS!

我不知道你是否注意到，但在我尝试计算 mergeSort (op >) [1] 时，我很快被要求计算 mergeSort (op >) [1] 作为其结果的一部分。但是这样做我很快就会一次又一次地这样做。因此，从运行手动调用函数看来，无限递归位于我所说的 mergeSort 和您的代码所称的 real.

中

这是算法中的一个错误，可以通过说明有关单例列表排序的一些内容来修复。

附带说明一下，我可能会完全重写此函数：

fun merge cmp ([], ys) = ys
  | merge cmp (xs, []) = xs
  | merge cmp (xs as x::xs', ys as y::ys') =
      case cmp (x, y) of
           GREATER => y :: merge cmp (xs, ys')
         | _       => x :: merge cmp (xs', ys)

fun sort cmp [] = []
  | sort cmp [x] = [x]
  | sort cmp xs =
    let
      val ys = List.take (xs, length xs div 2)
      val zs = List.drop (xs, length xs div 2)
    in
      merge cmp (sort cmp ys, sort cmp zs)
    end

fun down LESS = GREATER
  | down GREATER = LESS
  | down EQUAL = EQUAL

（我已经保留了这个错误。）

整数排序现在是：

sort (fn (x,y) => down (Int.compare (x,y))) [1,2,3]

Answer 2

有趣的类型实际上与使您的函数永远不会终止的错误有些相关。

删除自定义比较并分离助手（并折叠 merge_sort 和 real）：

fun split nil = (nil, nil) 
  | split [x] = ([x], nil)
  | split (x::y::xy) = 
    let 
        val (low, up) = split xy
    in 
        (x::low, y::up)
    end;

fun merge (nil, ylist) = ylist
  | merge (xlist, nil) = xlist
  | merge (x::xend, y::yend) =
    if x < y then
        x::merge (xend, y::yend)
    else
        y::merge (x::xend, yend);


fun merge_sort nil = nil
  | merge_sort L =
    let
        val (list1,list2) = split L
    in
        merge (merge_sort list1, merge_sort list2)
    end;

我们得到这些类型：

val split = fn : 'a list -> 'a list * 'a list
val merge = fn : int list * int list -> int list
val merge_sort = fn : 'a list -> int list

和 merge_sort 获取任何内容的列表并生成 int list.
真奇怪。
让我们看看这是如何得出的。

fun merge_sort nil = nil

nil 可以是任何内容的列表，因此给出 'a list -> 'a list.

| merge_sort L =
  let
      val (list1,list2) = split L
  in
      merge (merge_sort list1, merge_sort list2)
  end;

现在，结果必须是int list，因为这是merge产生的结果，并且也与merge的参数一致。
但是仍然没有办法从 merge_sort 的参数中推断出更具体的类型——它只是传回给 merge_sort，而 'a list 是我们已经得到的，所以我们结束达到 'a list -> int list.

看看对单例列表进行排序时会发生什么：

    merge-sort [1]
--> let val (list1, list2) = split [1] in merge (merge_sort list1, merge_sort list2)
--> merge (merge_sort [1], merge_sort [])

并且我们有一个不会终止的递归。

您需要一个单独的单例列表基本案例：

| merge_sort [x] = [x]

当你添加它时，类型就是它们应该的类型。

为什么这个 SML mergeSort 函数不是 return 排序列表？

Why does this SML mergeSort function not return a sorted list?

mergesort

sml