SML中的标准排序功能？

Question

SML中是否有标准排序功能？互联网上的文件非常稀缺,我找不到任何文件.

Answer 1

雷切尔只是部分正确.确实,SML基础库中没有定义排序功能,但是大多数实现扩展了基础库并添加了额外的功能.

因此,MosML同时具有ArraySort和Listsort模块,并且SML/NJ具有带有ListMergeSort实现的LIST_SORT签名.它还在阵列上具有一些其他排序功能,如MosML.有关完整列表,请参阅SML/NJ库手册的toc.

Answer 2

正如 Jesper Reenberg 指出的那样，标准 ML 编译器都有自己的（非标准的，具有讽刺意味的）排序库。由于这些文档缺少示例，以下是如何使用各种模块按升序对字符串列表进行排序：

1. 在 SML/NJ 和 MLton 中，使用ListMergeSort.sort函数：

   - fun sortStrings ss = ListMergeSort.sort (fn (s : string, t) => s > t) ss;
   [autoloading]
   [library $SMLNJ-LIB/Util/smlnj-lib.cm is stable]
   [autoloading done]
   val sortStrings = fn : string list -> string list
   - sortStrings ["World","Hello"];
   val it = ["Hello","World"] : string list
   

   这个库函数的怪癖是它需要一个“大于”布尔谓词。由于标准 ML 的>运算符已重载，但默认为int，因此我必须以某种方式明确注释我正在比较strings。

2. 在莫斯科 ML 中，使用该Listsort.sort函数：

   - load "Listsort";
   > val it = () : unit
   - fun sortStrings ss = Listsort.sort String.compare ss;
   > val sortStrings = fn : string list -> string list
   - sortStrings ["World", "Hello"];
   > val it = ["Hello", "World"] : string list
   

   这个库的怪癖是莫斯科 ML 的交互式 REPL 不会自动加载Listsort. load "Listsort";只有在交互式 REPL 中才需要打字；编译程序时，load不使用。

3. 在 Poly/ML 中，没有用于排序的库，因此您必须定义自己的排序函数。

如果这些排序函数都不够用，这里有一些用 Standard ML 编写的其他排序函数：

1. 标准 ML 中的 True QuickSort将朴素的 QuickSort（不是真正的 QuickSort）与John Coleman的Hoare 算法实现进行了比较。

2. 标准 ML 中的 Rosetta Code 的 MergeSort：

   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