SML NJ中的insertSorted比较函数

Question

我以前也发布过类似的问题，但我认为我需要重新表述我所问的问题。早些时候，我在想完成的事情上得到了一些很大的帮助。

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

我希望能够运行

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

哪个会返回

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

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

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

哪个会返回

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行：如果xcompy，则y：：x：：ys，否则y：：insertSorted(x，ys(；

Answer 1

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

我认为(a(是有道理的，尽管它有点脆弱，而

如果允许您假设您的输入已经排序，那么您的函数是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(，因此在中没有实点，然后插入一个额外的O(n(，除非我们被允许假设输入是"0"；几乎"；排序，在这种情况下，一些排序算法比其他算法更好。

假设"；未排序的"；与"；排序"；，由于您使用带有排序功能的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编译器中的排序函数，请参阅以下答案。