(有限) 集合と (有限) 写像は一般的に使われるデータ構造です。 関数的な集合と写像は、それらを生成した後では不変です。 関数的な集合/写像への挿入や削除は、元の構造を変更せずに、新しい集合/写像をコンストラクトして返します。 一般に、新しくコンストラクトされた集合/写像とその元は、中身の多くを共有しています。 関数的な集合/写像は安全に明示的な解放をすることはできず、その表現におけるメモリの回収にはガベージコレクション (GC) を使うしかないことに注意してください。
型 elt_t の値を収集したいとしましょう。 次のコードは、ATSLIB/libats での平衡木を用いた集合に対する生成と操作を表わすインターフェイスを本質的に作っています:
local // typedef elt = elt_t // staload FS = "libats/ML/SATS/funset.sats" implement $FS.compare_elt_elt<elt>(x, y) = compare(x, y) // in (* in-of-local *) #include "libats/ML/HATS/myfunset.hats" end // end of [local]
elt_t が int であると仮定します。 コードの次の行では、要素を含まない (整数の) 関数的な集合を生成しています:
与えられた集合に要素を挿入する関数には次の型が割り当てられます: ドット表記 .insert は関数 myfunset_insert でオーバーロードされています。 myfunset_insert の最初の引数が参照呼び出しであることに注意してください。 与えられた要素が与えられた集合に挿入される場合、新しく生成された集合が参照呼び出しの引数に保管され、(エラーが発生していないことを表わす) false が返ります。 そうでない場合、(失敗を表わす) true が返ります。 次の数行のコードは、関数的な集合に対する挿入操作を示しています:// var myset = myset // val-false = myset.insert(0) // inserted val-(true) = myset.insert(0) // not actually inserted val-false = myset.insert(1) // inserted val-(true) = myset.insert(1) // not actually inserted //
val-true = myset.remove(0) // removed val-false = myset.remove(0) // not actually removed val-true = myset.remove(1) // removed val-false = myset.remove(1) // not actually removed
一般的な各種の集合操作は libats/ML/HATS/myfunset.hats に見つかります。 これらの操作に割り当てられた型を見れば、それらをどのように呼び出すべきなのか理解するのは難しくないでしょう。 この章で紹介したコード全体は オンライン から入手できます。