std:set — 順序付き集合 (OrderedSet)

標準ライブラリモジュール (index.md)。本書中の裸の §N は本書の節を指す。言語の意味論は ../language-spec.md を参照。

import s := "std:set" は 値を要素にできる順序付き集合 OrderedSet のコンストラクターを slot に持つ namespace object を s に束縛する。要素は Comparable (language-spec.md §9.4) であればよく、重複は持たない。List.contains の O(n) メンバーシップに対し、O(log n) の包含判定と集合演算 (和・積・差) を提供する。

std:fs / std:term と違い I/O を伴わず、純粋・同期 (Future を返さない)。すべてのコンストラクター・メソッドは即値を返す。設計は map.md と対称 (要素は値のみで compare をキー基準とする)。

import s := "std:set"

a := s.of([3, 1, 2, 1])
a.to_list()         #> [1, 2, 3]            (重複除去・compare 昇順)
a.has(2)            #> true
a.length()          #> 3

a.union(s.of([3, 4])).to_list()         #> [1, 2, 3, 4]
a.intersect(s.of([2, 3, 9])).to_list()  #> [2, 3]
a.difference(s.of([2])).to_list()       #> [1, 3]

以下では import s := "std:set" で束縛したものとして s.of 等で記す。

1. 要素の制約 — Comparable と同一性

map.md §2 のキーと同じ規律が要素に適用される。

• 要素は Comparable (language-spec.md §9.4)。非 Comparable を渡すと呼び出し位置で Error (バグ層、language-spec.md §16)。
• 同一性は compare: a.compare(b) == Equal の 2 要素は同一とみなし、集合は一方だけを保持する (== のオーバーロードとは独立)。
• 1 つの集合の要素は相互に比較可能でなければならない。異型混在 (Int と String 等) は compare の異型比較が panic する (language-spec.md §9.4) ため Error。実用上、1 集合は単一の Comparable 型に揃える。
• Float 要素の順序は全順序 (total_cmp 相当)。

List を「重複を許す順序付き列」、OrderedSet を「重複を許さない値の集合」として使い分ける。

OrderedSet はCopyable である (../language-spec.md の複製の節)。不透明型だが不変な値なので、複製は Int を複製するのと同じ意味を持つ。

2. namespace コンストラクター

import s := "std:set" で得られる closed namespace の slot:

本モジュールは効果を1 つも持たない（../language-spec.md §17.9）。each / map / filter / fold は渡したブロックの効果を呼び出し元へ透過させる（EffectConduit）。

OrderedSet 型は std:set の型メンバーとして export され、型注釈に書ける (language-spec.md §13、time.md §1 と対称)。x: s.OrderedSet(Int) と修飾参照するか、import { OrderedSet } := "std:set" で取り出して x: OrderedSet(Int) と書く。不透明型であり内部表現 (平衡木) は露出しない。

要素型 e は型引数である: OrderedSet(e) は List(T) と同じ形の型構築子で、first() は Option(e)、to_list() は List(e) になる (§3.1 のシグネチャ表)。規律は map.md §3.1 と同じ — 型引数は省略できず (x: s.OrderedSet は type-arity-mismatch)、要素型を問わない位置は OrderedSet(Any) と明示で書く。要素型は of の引数から決まり、empty は [] が List(Never) であるのと同じく OrderedSet(Never) で、注釈や最初の insert で確定する。不変な値で要素を差し替える経路が無いので e は共変。

Comparable は型構築子 OrderedSet(e) の境界ではなく、e を取るシグネチャの境界である — of の引数と、has / contains / insert / remove と集合演算の受け手が (e: Comparable) を持ち (§3.1)、確実に非 Comparable な要素型 (List・Tuple・enum のタグ・compare を持たない不透明型) はその位置で type-mismatch になる (static-analysis.md §3.2 の非充足)。record と関数は幅部分型ゆえ静的には「不明」で素通しし、§1 の実行時 Error が backstop になる。実行時の照合は List(T) と同じく要素を走査する。

3. メソッド

OrderedSet 値 a に生えるメソッド。すべて非破壊で、変更系・集合演算は新しい OrderedSet を返す (元の a は不変)。

length / is_empty / first / last / to_list は zero-arg のため a.length! のように ! 形でも書ける。

3.1 静的なシグネチャ

受け手 OrderedSet(e) に対する各メソッドの静的型 (hover に出る形。static-analysis.md §2.2 のとおり実引数の照合はこの型に対して行う)。e は受け手から確定し、f は map のブロックの結果型から確定する。

(e: Comparable) の境界は受け手の型引数にもかかる — e を引数に取るメソッド (has / contains / insert / remove、集合演算、is_subset、compare) は受け手の e が確実に非 Comparable なら type-mismatch: receiver of insert expects OrderedSet((e: Comparable)), got OrderedSet(List(Int)) で落ちる。要素を比べない length / is_empty / first / last / each / map / filter / fold / to_list は鳴らない。

a := s.of [1, 2, 3, 4]

(a.filter { x | x > 2 }).to_list()  #> [3, 4]
(a.map { x | x * 10 }).to_list()  #> [10, 20, 30, 40]
a.fold 0 { acc, x | acc + x }  #> 10
a.is_subset (s.of [1, 2, 3, 4, 5])  #> true

4. 集合演算

• union / intersect / difference / is_subset は両辺 OrderedSet を要求し、非 OrderedSet は Error。
• 演算子 (+ / -) はオーバーロードしない (time.md §1 と同方針 — 不透明値型は演算子を増やさず名前付きメソッドで操作する)。和・積・差はそれぞれ union / intersect / difference メソッドで行う。

a := s.of [1, 2, 3]
b := s.of [3, 4]
(a.union b).to_list()  #> [1, 2, 3, 4]
(a.difference b).to_list()  #> [1, 2]

5. 等価と順序 (== / compare)

OrderedSet は 値等価を持ち、要素同一性を compare で定める (map.md §6 と対称)。

• ==: a == b は要素集合が一致 (compare 同一) するとき true。構築順に依らない。
• compare: 要素を compare 昇順に並べた列の辞書式順序で Ordering を返す。< <= > >= がこれを経由して効き、OrderedSet を別の OrderedSet/SortedMap の要素/キーにネストできる (集合の集合が作れる)。

s.of [1, 2, 3] == s.of [3, 2, 1, 1]  #> true

6. エラーモデル

map.md §7 と同じ 2 層。

1. Option を返す: first / last。空なら None。
2. Error (バグ層、language-spec.md §16):
• 要素が 非 Comparable
• 1 つの集合で 異型要素を混在 (compare の異型比較が panic)
• of に 非 List を渡す
• union / intersect / difference / is_subset の相手が OrderedSet でない

7. 計算量

compare 昇順に保った不変 slice で実装する (コピーオンライト、map.md §8 と対称)。要素数 n に対し:

• has / first / last: O(log n) (二分探索)
• insert / remove: O(n) (不変ゆえ slice をコピー)
• union / intersect / difference / is_subset: O(m log n + (n+m)) 程度 (m は相手の要素数)
• length / each / map / filter / fold / to_list: O(n)

ハッシュではなく順序 (compare) を採る理由は map.md §8 と同じ (compare が既にあり Hashable が無い・反復順が決定的・参考言語の主流)。平衡木への置き換えは内部実装の最適化余地。