sml - SMLの標準ソート機能?

Question

SML に標準のソート機能はありますか? インターネット上のドキュメントは非常に少なく、見つけることができませんでした。

score 16 · Accepted Answer

レイチェルは部分的に正しいだけです。SMLベーシスライブラリにソート機能が定義されていないことは事実ですが、ほとんどの実装ではベーシスライブラリが拡張され、機能が追加されています。

そのため、MosMLにはArraySortモジュールとListsortモジュールの両方があり、 SML / NJにはListMergeSort実装を備えたLIST_SORT署名があります。また、MosMLなどの配列に関するその他の並べ替え機能も備えています。完全なリストについては、SML/NJライブラリマニュアルの目次を参照してください。

score 5 · Accepted Answer

Jesper Reenberg が指摘しているように、標準 ML コンパイラにはそれぞれ独自の (非標準、皮肉なことに) 並べ替えライブラリがあります。これらのドキュメントには例がないため、さまざまなモジュールを使用して文字列のリストを昇順に並べ替える方法を次に示します。

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を比較していることを明示的に注釈する必要があります。
Moscow 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
```
このライブラリの癖は、Moscow ML の対話型 REPL が自動ロードされないことListsortです。入力load "Listsort";は対話型 REPL でのみ必要です。プログラムをコンパイルするときloadは、使用されません。
Poly/ML にはソート用のライブラリがないため、独自のソート関数を定義する必要があります。

これらの並べ替え関数のどちらも十分でない場合は、標準 ML で記述された他の並べ替え関数を次に示します。

標準 ML の真の QuickSort は、単純な QuickSort (実際には QuickSort ではない) を、 John Coleman によるHoare のアルゴリズムの実装と比較します。

標準 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

score 0 · Accepted Answer

リストのソートにこれはどうですか？逆を取得するには、いつでも逆を使用できます。

- fun sort(L) =
   if L=[] then []
   else if tl(L)=[] then L
   else merge(sort(take(L)), sort(skip(L)));
 val sort = fn : int list -> int list

ここを参照してください。

sml - SMLの標準ソート機能?

5 に答える 5

Related

Reference