SML NJ 中的 insertSorted 比较函数

Question

我之前发布过一个类似的问题，但我想我需要重新表述一下我的问题。对于我想要完成的事情，我早些时候得到了一些很大的帮助。

所以，我现在想知道的是如何在我的代码中传递 comp 函数，以便它可以自定义。

我希望能够运行

insertSorted(5, fn(a, b) => a > b, [8, 6, 3, 1];

哪个会 return

val it = [8, 6, 5, 3, 1]

同时还可以翻转标志并能够运行

insertSorted(5, fn(a, b) => a < b, [8, 6, 3, 1];

哪个会 return

val it = [1, 3, 5, 6, 8]

这是我目前的情况：

* insertSorted *
fun insertSorted (x, comp, nil) = [x]
 |  insertSorted (x, comp, y::ys) = if x comp y then y::x::ys else y :: insertSorted (x,ys);

这是有问题的“comp”：第 2 行：if x comp y then y::x::ys else y :: insertSorted (x,ys);

Answer 1

在我看来，insertSorted 可能是两件事： (a) 一个假设其输入列表按与输入列表相同的关系排序的函数给定，因此插入是 O(n)，或 (b) 一个函数，它首先根据关系对输入列表进行排序，然后插入元素。

我认为 (a) 是有道理的，尽管它有点脆弱，而 (b) 是一个小坏蛋：

如果允许您假设您的输入已经排序，则您的函数是 O(n) 而不是 O(n log n)。您可以将此数据结构称为预排序列表。现在，没有什么能阻止您将未排序的列表提供给 insertSorted，因此这可能会导致错误。您可以通过多种方式克服这一点。但那是另一个话题了。

如果那是你想要的，那么这就是如何做到的：

fun insertSorted (x, comp, y::ys) =
      if comp (x, y)
      then y :: insertSorted (x, comp, ys)
      else x :: y :: ys
  | insertSorted (x, _, []) = [x]

测试这个：

- insertSorted (5, op <, [8,7,6,4,3,2]);
val it = [8,7,6,5,4,3,2] : int list

- insertSorted (5, op >, [2,3,4,6,7,8]);
val it = [2,3,4,5,6,7,8] : int list

如果您不假设您的输入已经排序，那么 insertSorted 是一个非常糟糕的名称：我们不会插入已排序的内容。此外，由于我们无论如何都需要对整个输入进行排序，即 O(n log n)，因此 then 中插入一个额外的 O(n)，除非我们被允许假设输入是“几乎”排序的，在这种情况下一些排序算法比其他算法更好。

假设“unsorted”是“sorted”的反义词，由于你使用的是带有排序功能的SML/NJ，你可以做的是：

fun insertUnsorted (x, comp, ys) =
  ListMergeSort.sort comp (x::ys)

测试这个：

- insertUnsorted (5, op <, [1,9,3,4,6,2]);
val it = [9,6,5,4,3,2,1] : int list

- insertUnsorted (5, op >, [1,9,3,4,6,2]);    
val it = [1,2,3,4,5,6,9] : int list

与sort相比，我认为这个功能不是很有用。

对于 SML/NJ 以外的其他 SML 编译器中的排序函数，请参阅 this answer。

SML NJ 中的 insertSorted 比较函数

insertSorted comparison function in SML NJ

sml

smlnj