SML：递归调用快速排序时出现值限制错误

Question

我正在为练习编写一个快速排序函数。我已经知道 5 行功能快速排序；但我想通过让它扫描一次列表和 return 一对将原始列表分成两半的列表来改进分区。所以我写道：

fun partition nil = (nil, nil)
  | partition (pivot :: rest) =
  let
    fun part (lst, pivot, (lesseq, greater)) =
      case lst of
           [] => (lesseq, greater)
         | (h::t) =>
             if h <= pivot then part (t, pivot, (h :: lesseq, greater))
             else part (t, pivot, (lesseq, h :: greater))
  in
    part (rest, pivot, ([pivot], []))
  end;

这个分区够用了。它给了我一个签名val partition = fn : int list -> int list * int list。它运行符合预期。

当我使用下面的快速排序时，事情就开始崩溃了。

fun quicksort_2 nil = nil
  | quicksort_2 lst = 
let
  val (lesseq, greater) = partition lst
in
  quicksort_2 lesseq @ quicksort_2 greater
end;

如果我消除对 quicksort_2 的递归调用，我可以运行上面的函数；但如果我把它们放回去（真正去整理东西），它就会停止运行。签名也会不正确，给我 val quicksort_2 = fn : int list -> 'a list。当我调用列表中的函数时收到的警告是：

Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...)

这里有什么问题？我没有使用任何 ref 变量；我尝试过的类型注释似乎没有帮助...

Answer 1

主要问题是您的快速排序函数缺少单例列表基本案例。应该是

fun quicksort [ ] = [ ]
  | quicksort [x] = [x]
  | quicksort xs  = 
      let
        val (l, r) = partition xs
      in
        quicksort l @ quicksort r
      end

根据您的 partition 的类型，它应该具有 int list -> int list 类型。我们必须添加这种情况，否则您将永远不会遇到基本情况，而是无限期地递归。

有关您为什么看到您遇到的问题的更多详细信息：

The signature will be incorrect as well, giving me val quicksort_2 = fn : int list -> 'a list

这是因为您的函数的代码域从未被限制为不如 'a list 通用。查看原始实现中可能的分支，我们可以看到在 nil 分支中 return nil （最通用的类型 'a list）和递归情况你得到两个 'a lists（根据我们到目前为止的假设）并附加它们，导致 'a list--- 这很好，所以你的类型没有进一步限制。

[Value Restriction Warning] What is the problem here? I'm not using any ref variables

值限制与 refs 没有真正的关系（尽管在使用它们时经常会出现）。相反，它禁止任何在顶层的多态性都必须是其语法的值（因此排除了在顶层的类型抽象器后面进行计算的可能性）。这是因为给定 xs : int list 我们（忽略值限制）有 quicksort_2 xs : 'a list---否则它是多态的，但不是语法值。相应的是数值受限。

SML：递归调用快速排序时出现值限制错误

SML: Value restriction error when recursively calling quicksort

functional-programming

sml

smlnj