Standard ML
マージソートのアルゴリズムについては、当該記事を参照されたい。ここではマージソートを3つの関数 split、merge、MergeSort で実装している。
関数 split は、追加の引数を持つ局所関数 split_iter を使って実装している。これは末尾再帰の実装に便利な手法である。この関数はSMLのパターンマッチング構文を使っており、リストが空でないケース ('x::xs') と空のケース ('[]') を定義している。
local-in-end という構文を let-in-end という構文に置き換えると、等価な定義が得られる。
split と同様、merge も局所関数 merge_iter を使って効率化する。merge_iter ではいくつかのケース(渡されたリストがどちらも空でない場合、一方が空の場合、両方が空の場合)を定義している。'_' はワイルドカード・パターンを表している。
この関数は2つの昇順のリストを1つの降順のリストにマージする。逆転するのはSMLにおけるリストの構造によるものである。SMLではリストを非平衡2分木で実装しているため、要素を先頭に付与するのは容易だが、最後尾に付与するのは非効率的である。
最後に、MergeSort 関数を以下に示す。
なお、見ての通りこのコードでは要素の型を規定していない。そのため、順序関数 lt さえあれば、どんな型の要素でもソートできる。型推論により、コンパイラは lt 関数のような複雑な型も含め、あらゆる変数の型を推論できる。
SMLの処理系の多くは対話型のトップレベルを備えており、それに入力することで、コード断片は容易に実行できる。これは、入力された式の型を推論し評価する。例えば、SML/NJ では、次のように起動する。
コードは "-" のプロンプトの位置に入力する。例えば 1+2*3 を計算する場合、次のようになる。
トップレベルは式の型が "int" であると推論し、その値 "7" を表示している。
Standard ML には高度なモジュールシステムがあり、プログラムを論理的に関連する型と値の宣言の structure による階層に分解することができる。SMLモジュールは単に名前空間を制御するだけでなく、抽象化の役割も持っており、プログラマはこれを使って抽象データ型を定義できる。
主に3つの構文要素でSMLモジュールシステムが構成される。signature と structure と functor である。structure はモジュールそのものである。型、式、値、structure (substructure) の集合体であり、それらを1つの論理単位にパッケージ化している。signature はインタフェースであり、一般にその structure の型として認識される。その structure が提供する全ての実体の名前を指定し、型要素のアリティ、値要素の型、substructure の signature も指定する。型要素の定義はエクスポートする場合もしない場合もある。定義を隠蔽した型要素を「抽象型 (abstract type)」と呼ぶ。functor は structure から structure への関数である。すなわち、functor は1つ以上の引数を受け付け(通常、signature で指定した structure)、結果として structure を生成する。