Chapter 12. 関数的な集合と写像

Table of Contents
関数的な集合
関数的な写像

(有限) 集合と (有限) 写像は一般的に使われるデータ構造です。 関数的な集合と写像は、それらを生成した後では不変です。 関数的な集合/写像への挿入や削除は、元の構造を変更せずに、新しい集合/写像をコンストラクトして返します。 一般に、新しくコンストラクトされた集合/写像とその元は、中身の多くを共有しています。 関数的な集合/写像は安全に明示的な解放をすることはできず、その表現におけるメモリの回収にはガベージコレクション (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]

関数的な集合を用いたプログラミングを単純化するためのラッパーである HATS ファイルは オンライン から入手できます。 シンボル compare をオーバーロードする型 elt_t の値に対する比較関数があることを、ここでは仮定していることに注意してください。 存在しない場合、そのような関数を実装する必要があります。

elt_tint であると仮定します。 コードの次の行では、要素を含まない (整数の) 関数的な集合を生成しています:

val myset = myfunset_nil()

与えられた集合に要素を挿入する関数には次の型が割り当てられます:

// fun myfunset_insert(xs: &myset >> _, x0: elt): bool //

ドット表記 .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 //

上記コードの最初の行は謎めいて見えるかもしれません: その唯一の目的は、myfunset_insert への最初の引数として渡される左辺値を生成することです。 デバッグのために、与えられた集合中の値を印字したいと思うかもしれません:

// val () = fprintln! (stdout_ref, "myset = ", myset) //

このとき、シンボル fprintfprint_myset でオーバーロードされています。 与えられた集合から要素を削除する関数には次の型が割り当てられます:

// fun myfunset_remove(xs: &myset >> _, x0: elt): bool //

ドット表記 .remove は関数 myfunset_remove でオーバーロードされています。 myfunset_remove の最初の引数は参照呼び出しであることに注意してください。 与えられた集合から与えられた要素を削除する場合、新しく生成された集合が参照呼び出しの引数に保管され、true が返ります。 そうでない場合、false が返ります。 次の数行のコードは、関数的な集合に対する削除操作を示しています:

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 に見つかります。 これらの操作に割り当てられた型を見れば、それらをどのように呼び出すべきなのか理解するのは難しくないでしょう。 この章で紹介したコード全体は オンライン から入手できます。