# 機能設計書 33-Map型

## 概要

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

### 本機能の処理概要

**業務上の目的・背景**：アプリケーション開発において、キーから値への高速なルックアップが必要な場面は多い。従来の可変辞書（Dictionary）は並行処理時の競合状態やデータの一貫性維持に課題があった。Map型は不変（イミュータブル）なデータ構造として、スレッドセーフな操作と関数型プログラミングパラダイムに適合した宣言的なコード記述を可能にする。また、変更があった場合も構造を共有することで、メモリ効率と変更の追跡性を両立する。

**機能の利用シーン**：設定値のキー・バリュー管理、ユーザーIDからユーザー情報へのマッピング、キャッシュの実装、状態管理における不変データ構造の利用、頻繁にルックアップを行うがデータ変更は稀な場面など。

**主要な処理内容**：
1. キー・値ペアの追加・削除・検索操作（add、remove、find、tryFind、containsKey）の提供
2. 関数型プログラミングのためのコンビネータ関数（map、filter、fold、iter、exists、forall）の提供
3. Map型とシーケンス/リスト/配列間の変換関数（ofSeq、ofList、ofArray、toSeq、toList、toArray）の提供
4. キーコレクション・値コレクションの取得（keys、values）
5. 最小キー・最大キーの取得（minKeyValue、maxKeyValue）

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

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

## 関連画面

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

## 機能種別

データ構造 / CRUD操作 / 計算処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| table/map | Map<'Key, 'Value> | Yes | 操作対象のMap | - |
| key | 'Key | Yes | 検索・追加・削除対象のキー | 'Key型はcomparison制約必須 |
| value | 'Value | No | 追加する値 | - |
| mapping | 'Key -> 'Value -> 'T | No | 変換関数 | - |
| predicate | 'Key -> 'Value -> bool | No | 述語関数 | - |
| folder | 'State -> 'Key -> 'Value -> 'State | No | 畳み込み関数 | - |
| action | 'Key -> 'Value -> unit | No | 副作用関数 | - |

### 入力データソース

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

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 結果 | Map<'Key, 'Value> / 'Value option / bool / int / ('Key * 'Value) list / ICollection<'Key> / ICollection<'Value> | 各関数に応じた戻り値 |

### 出力先

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

## 処理フロー

### 処理シーケンス

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

### フローチャート

```mermaid
flowchart TD
    A[Map操作を開始] --> B{操作種別}
    B -->|find/tryFind| C[キーで二分探索]
    C --> D{キーが存在?}
    D -->|Yes| E[値を返却]
    D -->|No| F[例外/None]
    B -->|add| G[AVL木に挿入]
    G --> H[再平衡化]
    H --> I[新しいMapを返却]
    B -->|remove| J[AVL木から削除]
    J --> H
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-33-1 | キー制約 | キー型は比較可能（comparison制約）でなければならない | Map生成時 |
| BR-33-2 | 不変性 | add/remove操作は新しいMapを返し、元のMapは変更しない | 常に |
| BR-33-3 | キー重複 | 同じキーで追加した場合、値は上書きされる | add操作時 |
| BR-33-4 | find例外 | find関数はキーが存在しない場合KeyNotFoundExceptionを投げる | キー不在時 |

### 計算ロジック

- 検索・追加・削除: O(log n)の時間計算量（AVL木の特性）
- 列挙: O(n)の時間計算量

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| KeyNotFoundException | 実行時例外 | find/Item[]でキーが存在しない場合 | tryFindを使用するかcontainsKeyで事前確認 |
| NotSupportedException | 実行時例外 | IDictionary.Add等の可変操作を呼び出した場合 | add関数を使用 |

### リトライ仕様

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

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

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

## パフォーマンス要件

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

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

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

## 備考

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

---

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

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

### 推奨読解順序

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

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

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

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

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

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

**主要処理フロー**:
1. **101-115行目**: `mk`関数 - 新しいノードを作成し高さを計算
2. **117-139行目**: `rebalance`関数 - AVL木の再平衡化（回転操作）
3. **141-162行目**: `add`関数 - キー・値ペアの追加と再平衡化
4. **164-177行目**: `tryGetValue`関数 - 値の検索（byref出力パラメータ）
5. **192-198行目**: `tryFind`関数 - Option型で値を返す検索
6. **263-285行目**: `remove`関数 - ノード削除と再平衡化

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | map.fs | `src/FSharp.Core/map.fs` | Map<'Key, 'Value>型（677-1033行目） |

**主要処理フロー**:
- **700-702行目**: Emptyプロパティ - 空のMapを取得
- **742-753行目**: Add関数 - キー・値ペアを追加して新しいMapを返す
- **761-768行目**: Item（インデクサ） - キーで値を取得
- **801-812行目**: Count/Count関数 - 要素数を返す
- **831-836行目**: Keys/Values - キー/値のコレクションを取得

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

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

**主要処理フロー**:
- **1152-1154行目**: isEmpty関数
- **1156-1158行目**: add関数
- **1164-1166行目**: find関数
- **1168-1170行目**: tryFind関数
- **1248-1259行目**: ofList/ofSeq/ofArray関数

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

```
ユーザーコード
    │
    ├─ Map.add key value map
    │      └─ Map.Add(key, value)
    │             └─ MapTree.add comparer key value tree
    │                    └─ rebalance (再平衡化)
    │
    ├─ Map.find key map
    │      └─ map.[key]
    │             └─ MapTree.find comparer key tree
    │                    └─ 二分探索 → 値 or KeyNotFoundException
    │
    └─ Map.tryFind key map
           └─ map.TryFind key
                  └─ MapTree.tryFind comparer key tree
                         └─ 二分探索 → Some value or None
```

### データフロー図

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

('Key * 'Value) seq ──▶ MapTree.ofSeq ─────────────────▶ Map<'Key,'Value>
                              │
                              └──▶ 各ペアをaddで追加
                                     │
                                     └──▶ AVL木に挿入・再平衡化

Map<'Key,'Value> ─────▶ MapTree.add ───────────────────▶ Map<'Key,'Value>
+ (key, value)               │
                              ├──▶ キー比較で挿入位置決定
                              │
                              └──▶ 再平衡化（必要に応じて回転）

Map<'Key,'Value> ─────▶ MapTree.find ──────────────────▶ 'Value
+ key                        │
                              └──▶ 二分探索でO(log n)検索
```

### 関連ファイル一覧

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