# 機能設計書 34-Set型

## 概要

本ドキュメントは、F#コアライブラリにおける不変の集合（Set）型およびその操作関数群の機能設計を記述する。Set型は重複のない要素を効率的に格納・検索するための平衡二分木（AVL木）ベースのデータ構造である。

### 本機能の処理概要

**業務上の目的・背景**：アプリケーション開発において、重複のないデータ集合を管理する必要は頻繁にある。従来の可変集合（HashSet）は並行処理時の競合状態やデータの一貫性維持に課題があった。Set型は不変（イミュータブル）なデータ構造として、スレッドセーフな操作と関数型プログラミングパラダイムに適合した宣言的なコード記述を可能にする。数学的な集合演算（和集合、積集合、差集合）を直接サポートする。

**機能の利用シーン**：ユニークなIDの管理、タグやカテゴリの重複除去、アクセス許可リストの管理、グラフアルゴリズムにおける訪問済みノードの追跡、フィルタリング条件の組み合わせなど。

**主要な処理内容**：
1. 要素の追加・削除・検索操作（add、remove、contains、minElement、maxElement）の提供
2. 集合演算（union、intersect、difference、isSubset、isSuperset、isProperSubset、isProperSuperset）の提供
3. 関数型プログラミングのためのコンビネータ関数（map、filter、fold、iter、exists、forall、partition）の提供
4. Set型とシーケンス/リスト/配列間の変換関数（ofSeq、ofList、ofArray、toSeq、toList、toArray）の提供

**関連システム・外部連携**：.NETのICollection<T>インターフェースを実装し、C#コードとの相互運用性を提供。IEnumerable<'T>としても列挙可能。

**権限による制御**：本機能はライブラリ型であり、権限による制御は行わない。

## 関連画面

該当なし（コアライブラリ機能であり、画面は持たない）

## 機能種別

データ構造 / 集合演算 / 計算処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| set | Set<'T> | Yes | 操作対象のSet | - |
| value/element | 'T | Yes | 追加・削除・検索対象の要素 | 'T型はcomparison制約必須 |
| set2 | Set<'T> | No | 集合演算の対象Set | - |
| mapping | 'T -> 'U | No | 変換関数 | - |
| predicate | 'T -> bool | No | 述語関数 | - |
| folder | 'State -> 'T -> 'State | No | 畳み込み関数 | - |
| action | 'T -> unit | No | 副作用関数 | - |

### 入力データソース

F#プログラム内で生成されるSet型の値、シーケンス、リスト、配列からの変換。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 結果 | Set<'T> / bool / int / 'T / 'T list / Set<'T> * Set<'T> | 各関数に応じた戻り値 |

### 出力先

関数の戻り値としてプログラムに返却。

## 処理フロー

### 処理シーケンス

```
1. Set値の受け取り
   └─ 内部のAVL木構造にアクセス
2. 各操作に応じた処理実行
   └─ 検索: 二分探索でO(log n)
   └─ 追加: 新しいノードを挿入し再平衡化
   └─ 集合演算: 両方の木を走査して結果を構築
3. 結果の返却
   └─ 新しいSet（不変操作）、検索結果、または集約結果
```

### フローチャート

```mermaid
flowchart TD
    A[Set操作を開始] --> B{操作種別}
    B -->|contains| C[要素で二分探索]
    C --> D{要素が存在?}
    D -->|Yes| E[trueを返却]
    D -->|No| F[falseを返却]
    B -->|add| G[AVL木に挿入]
    G --> H[再平衡化]
    H --> I[新しいSetを返却]
    B -->|union| J[両方のSetを走査]
    J --> K[マージして新Set構築]
    K --> I
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-34-1 | 要素制約 | 要素型は比較可能（comparison制約）でなければならない | Set生成時 |
| BR-34-2 | 不変性 | add/remove操作は新しいSetを返し、元のSetは変更しない | 常に |
| BR-34-3 | 重複排除 | 同じ要素を追加しても重複は発生しない | add操作時 |
| BR-34-4 | 空Set例外 | minElement/maxElementは空Setに対してArgumentExceptionを投げる | 空Set時 |

### 計算ロジック

- 検索・追加・削除: O(log n)の時間計算量
- union: O(m + n)の時間計算量（両方のSetのサイズ）
- intersect: O(min(m,n) * log(max(m,n)))の時間計算量
- 列挙: O(n)の時間計算量

## データベース操作仕様

該当なし（メモリ上のデータ操作のみ）

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| ArgumentException | 実行時例外 | minElement/maxElementを空Setに対して呼び出した場合 | isEmpty確認またはtryMinElement/tryMaxElementを使用 |
| NotSupportedException | 実行時例外 | ICollection.Add等の可変操作を呼び出した場合 | add関数を使用 |

### リトライ仕様

該当なし（単純な同期操作のため）

## トランザクション仕様

該当なし（不変データ構造のため、ロールバック不要）

## パフォーマンス要件

- 検索・追加・削除: O(log n)の時間計算量
- 空間計算量: O(n)
- AVL木の平衡係数（tolerance）は2
- シリアライゼーション対応（OnSerializing/OnDeserialized属性）

## セキュリティ考慮事項

特になし（純粋なデータ構造）

## 備考

- Set型は不変であるため、並行処理において安全に共有可能
- 構造共有により、変更時のメモリコピーを最小化
- デバッガ表示用のプロキシ（SetDebugView）が実装されている
- IComparableインターフェースを実装し、Set同士の比較が可能

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

Set型の内部はAVL木（平衡二分木）で実装されている。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | set.fs | `src/FSharp.Core/set.fs` | SetTree型の定義（16-29行目）- 内部AVL木構造 |

**読解のコツ**:
- `SetTree<'T>`は単一ノードを表し、KeyとHeightを保持
- `SetTreeNode<'T>`は子ノード（Left/Right）を持つ内部ノード
- AVL木の平衡は`tolerance = 2`で維持される（101行目）

#### Step 2: 内部モジュールを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | set.fs | `src/FSharp.Core/set.fs` | SetTreeモジュール（32-586行目）- 内部操作関数群 |

**主要処理フロー**:
1. **97-109行目**: `mk`関数 - 新しいノードを作成し高さを計算
2. **111-134行目**: `rebalance`関数 - AVL木の再平衡化（回転操作）
3. **136-148行目**: `add`関数 - 要素の追加と再平衡化
4. **166-188行目**: `remove`関数 - 要素削除と再平衡化
5. **208-214行目**: `mem`関数 - 要素の存在確認（contains）
6. **262-292行目**: `union`関数 - 和集合の計算
7. **294-314行目**: `intersectionAux`関数 - 積集合の計算

#### Step 3: 公開型Setを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | set.fs | `src/FSharp.Core/set.fs` | Set<'T>型（588-916行目） |

**主要処理フロー**:
- **610-612行目**: Emptyプロパティ - 空のSetを取得
- **654-660行目**: Add関数 - 要素を追加して新しいSetを返す
- **678-684行目**: Contains関数 - 要素の存在確認
- **686-696行目**: MinimumElement/MaximumElement - 最小/最大要素の取得
- **700-714行目**: IsSubsetOf/IsSupersetOf/IsProperSubsetOf/IsProperSupersetOf - 部分集合判定

#### Step 4: Setモジュールを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | set.fs | `src/FSharp.Core/set.fs` | Setモジュール（1026-1182行目） |

**主要処理フロー**:
- **1030-1032行目**: isEmpty関数
- **1034-1036行目**: add関数
- **1038-1040行目**: contains関数
- **1058-1060行目**: union関数
- **1062-1064行目**: intersect関数
- **1066-1068行目**: difference関数

### プログラム呼び出し階層図

```
ユーザーコード
    │
    ├─ Set.add value set
    │      └─ Set.Add(value)
    │             └─ SetTree.add comparer value tree
    │                    └─ rebalance (再平衡化)
    │
    ├─ Set.contains value set
    │      └─ set.Contains value
    │             └─ SetTree.mem comparer value tree
    │                    └─ 二分探索 → true or false
    │
    ├─ Set.union set1 set2
    │      └─ Set(SetTree.union comparer tree1 tree2)
    │             └─ 両方の木をマージ
    │
    └─ Set.intersect set1 set2
           └─ Set(SetTree.intersection comparer tree1 tree2)
                  └─ 共通要素のみ抽出
```

### データフロー図

```
[入力]                        [処理]                              [出力]

'T seq ───────────────▶ SetTree.ofSeq ─────────────────▶ Set<'T>
                              │
                              └──▶ 各要素をaddで追加
                                     │
                                     └──▶ AVL木に挿入・再平衡化

Set<'T> + Set<'T> ────▶ SetTree.union ─────────────────▶ Set<'T>
                              │
                              └──▶ 両方の木を走査・マージ

Set<'T> + Set<'T> ────▶ SetTree.intersection ──────────▶ Set<'T>
                              │
                              └──▶ 共通要素のみ抽出

Set<'T> ──────────────▶ SetTree.toSeq ─────────────────▶ 'T seq
                              │
                              └──▶ 中間順走査（昇順）
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| set.fs | `src/FSharp.Core/set.fs` | ソース | Set型およびSetモジュールの実装 |
| set.fsi | `src/FSharp.Core/set.fsi` | シグネチャ | Set型およびSetモジュールのシグネチャ定義 |
