# 機能設計書 21-リダクション演算

## 概要

本ドキュメントは、Julia Base ライブラリが提供するリダクション演算機能の設計について記述する。リダクション演算とは、コレクション（配列・イテレータ等）の要素を二項演算子で逐次的に畳み込み、単一のスカラー値に集約する処理群である。

### 本機能の処理概要

リダクション演算は、`reduce` / `mapreduce` / `foldl` / `foldr` などの汎用畳み込み関数と、`sum` / `prod` / `maximum` / `minimum` / `any` / `all` / `extrema` / `count` などの特化型集約関数を提供する。多次元配列に対しては `dims` キーワード引数により特定次元に沿ったリダクションも可能である。

**業務上の目的・背景**：科学計算・データ分析において、大量のデータを集約して統計量や要約値を得ることは最も基本的かつ頻繁に行われる処理である。リダクション演算は、配列の合計・積・最大値・最小値・論理演算結果などを効率的に計算するための基盤を提供する。数値安定性を考慮したペアワイズ加算アルゴリズムや、小さな整数型の自動昇格など、実用的な配慮が組み込まれている。

**機能の利用シーン**：データセットの合計値・平均値の算出、配列要素の最大値・最小値の取得、論理条件の全称・存在判定、カスタム二項演算による畳み込み処理、次元ごとの集約処理（行方向・列方向の合計など）で利用される。

**主要な処理内容**：
1. `reduce(op, itr)` / `mapreduce(f, op, itr)` による汎用リダクション
2. `foldl(op, itr)` / `foldr(op, itr)` による結合順序保証付きリダクション
3. `sum` / `prod` による数値集約（型昇格付き）
4. `maximum` / `minimum` / `extrema` による極値計算
5. `any` / `all` による論理リダクション
6. `count` による条件カウント
7. 多次元配列での次元指定リダクション（`sum(A; dims=1)` 等）
8. ペアワイズアルゴリズムによる数値安定な加算

**関連システム・外部連携**：なし。Base モジュール内で完結する機能である。

**権限による制御**：なし。すべてのユーザーが利用可能である。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 画面関連なし（ライブラリ関数） |

## 機能種別

計算処理

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| op | Function | Yes | 二項演算子（+, *, min, max 等） | 呼び出し可能であること |
| f | Function | No | 各要素に適用するマッピング関数 | 呼び出し可能であること |
| itr | Any (iterable) | Yes | リダクション対象のコレクション | iterateプロトコルを実装していること |
| init | Any | No | 初期値（空コレクション対応に必要） | opの中立元であること（推奨） |
| dims | Integer / Tuple | No | リダクションを行う次元 | 1以上の整数であること |

### 入力データソース

Julia プログラム内のコレクション（Array、Range、Tuple、Generator、その他イテラブルオブジェクト）。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | Any | リダクション結果のスカラー値（sumならInt/Float64等、anyならBool等） |
| result_array | AbstractArray | dims指定時は次元が縮退した配列 |

### 出力先

呼び出し元への戻り値。

## 処理フロー

### 処理シーケンス

```
1. reduce(op, itr) が呼ばれる
   └─ mapreduce(identity, op, itr) へ委譲
2. mapreduce(f, op, itr) が呼ばれる
   └─ 配列の場合: _mapreduce(f, op, IndexStyle(A), A) へ分岐
   └─ その他: mapfoldl(f, op, itr) へ委譲
3. _mapreduce（IndexLinear の場合）
   └─ 長さ0: mapreduce_empty_iter で空コレクション処理
   └─ 長さ1: mapreduce_first で単一要素処理
   └─ 長さ<16: インライン逐次処理（コンパイル最適化）
   └─ 長さ>=16: mapreduce_impl でペアワイズ分割統治法
4. mapreduce_impl（ペアワイズ）
   └─ ブロックサイズ未満: 逐次処理（@simd付き）
   └─ ブロックサイズ以上: 中間点で分割し再帰的に処理
5. 結果を返す
```

### フローチャート

```mermaid
flowchart TD
    A[reduce/mapreduce 呼び出し] --> B{入力の型}
    B -->|AbstractArray + IndexLinear| C{配列長}
    B -->|その他イテラブル| D[mapfoldl_impl]
    C -->|n == 0| E[mapreduce_empty_iter]
    C -->|n == 1| F[mapreduce_first]
    C -->|n < 16| G[インライン逐次処理]
    C -->|n >= 16| H[mapreduce_impl ペアワイズ]
    H --> I{ブロックサイズ比較}
    I -->|小| J[逐次処理 + @simd]
    I -->|大| K[分割統治法で再帰]
    K --> I
    D --> L[_foldl_impl]
    L --> M[iterate でループ]
    E --> N[結果返却]
    F --> N
    G --> N
    J --> N
    M --> N
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 空コレクション処理 | 空コレクションに対するリダクションは、init指定がない場合はArgumentErrorを投げる。ただし +, *, &, \| などの演算子ではゼロ元/単位元を返す | コレクションが空の場合 |
| BR-02 | 小整数型の昇格 | Bool, Int8, Int16等の小さい整数型はsum/prodでInt/UIntに昇格される | add_sum/mul_prod使用時 |
| BR-03 | 結合順序 | reduce/mapreduceは結合順序が未規定。foldlは左結合、foldrは右結合を保証 | 常時 |
| BR-04 | ペアワイズ加算 | 配列の加算ではペアワイズアルゴリズムにより数値安定性を向上させる | 配列に対するsum等 |

### 計算ロジック

- `add_sum(x, y)`: 小整数型をInt/UIntに昇格してから加算
- `mul_prod(x, y)`: 小整数型をInt/UIntに昇格してから乗算
- ペアワイズ分割統治: ブロックサイズ1024（abs2+の場合4096）で分割し、再帰的に中間結果をマージ

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

### 操作別データベース影響一覧

該当なし（インメモリ計算のみ）。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | ArgumentError | 空コレクションにinit未指定でreduce | init引数を指定する |
| - | ArgumentError | dimsに0以下の値を指定 | 1以上の整数を指定する |
| - | MethodError | 要素型にopが適用不可 | 適切な演算子を選択する |

### リトライ仕様

リトライは不要（純粋な計算処理のため）。

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

該当なし。

## パフォーマンス要件

- ペアワイズアルゴリズムにより O(n) 時間で処理
- @simd アノテーションにより SIMD ベクトル化を促進
- 短い配列（16要素未満）ではインライン処理でコンパイルオーバーヘッドを回避
- `_mapreduce` は IndexLinear と IndexCartesian で異なるパスを使用し、メモリアクセスパターンを最適化

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

特になし。

## 備考

- `mapreduce` は複数イテレータに対応（Julia 1.2以降）
- Transducer パターン（`_xfadjoint`）により、`Generator` / `Filter` / `Flatten` のイテレータ変換をリダクション関数の変換に変換し、中間配列の生成を回避する

---

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

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

### 推奨読解順序

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

リダクションの内部で使用される特殊な型と Reducing Function の構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | reduce.jl | `base/reduce.jl` | BottomRF, MappingRF, FilteringRF, FlatteningRF の各構造体の役割を理解する |

**読解のコツ**: Julia では構造体に `(op::BottomRF)(acc, x)` のように呼び出し演算子を定義でき、これにより構造体がファンクタ（呼び出し可能オブジェクト）として振る舞う。リダクション関数の合成パターンを理解するために重要。

- **70行目**: `_InitialValue` 構造体 - 初期値未指定を表すセンチネル型
- **79-84行目**: `BottomRF` - 最初の要素を `reduce_first` で処理するラッパー
- **91-98行目**: `MappingRF` - マッピング+リダクションの合成
- **105-110行目**: `FilteringRF` - フィルタリング+リダクションの合成
- **118-125行目**: `FlatteningRF` - フラット化+リダクションの合成

#### Step 2: エントリーポイントを理解する

ユーザーが呼び出す公開関数の定義を確認する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | reduce.jl | `base/reduce.jl` | reduce, mapreduce, foldl, foldr, sum, prod, any, all などの公開API定義 |

**主要処理フロー**:
1. **173行目**: `mapfoldl` - 左畳み込みのエントリーポイント
2. **196行目**: `foldl` - `mapfoldl(identity, op, itr)` への委譲
3. **305行目**: `mapreduce` - `mapfoldl` への委譲（配列以外）
4. **489行目**: `reduce` - `mapreduce(identity, op, itr)` への委譲
5. **498行目以降**: `sum`, `prod`, `maximum`, `minimum` 等の特化関数

#### Step 3: 配列リダクションの最適化パスを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | reduce.jl | `base/reduce.jl` | _mapreduce, mapreduce_impl のペアワイズアルゴリズム |

**主要処理フロー**:
- **251-273行目**: `mapreduce_impl` - ペアワイズ分割統治法の実装
- **427-448行目**: `_mapreduce(f, op, ::IndexLinear, A)` - 配列長に応じた分岐処理

#### Step 4: 次元リダクションを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | reducedim.jl | `base/reducedim.jl` | 多次元配列の次元指定リダクション |

**主要処理フロー**:
- **6-7行目**: `reduced_index` - リダクション後の軸サイズ計算
- **20-28行目**: `reduced_indices` / `reduced_indices0` - リダクション後のインデックス空間計算
- **69-86行目**: `reducedim_init` - 次元リダクションの初期配列生成

#### Step 5: Transducer パターンを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | reduce.jl | `base/reduce.jl` | _xfadjoint によるイテレータ変換のリダクション関数変換への変換 |

**主要処理フロー**:
- **146-164行目**: `_xfadjoint` と `_xfadjoint_unwrap` - Generator/Filter/Flatten を MappingRF/FilteringRF/FlatteningRF に変換

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

```
sum(A) / reduce(op, itr)
    |
    +-- mapreduce(identity/f, add_sum/op, itr)
    |       |
    |       +-- [配列] _mapreduce(f, op, IndexStyle(A), A)
    |       |       |
    |       |       +-- [IndexLinear]
    |       |       |       +-- [n==0] mapreduce_empty_iter
    |       |       |       +-- [n==1] mapreduce_first
    |       |       |       +-- [n<16] インライン逐次処理
    |       |       |       +-- [n>=16] mapreduce_impl (ペアワイズ)
    |       |       |
    |       |       +-- [IndexCartesian] mapfoldl
    |       |
    |       +-- [イテラブル] mapfoldl_impl
    |               |
    |               +-- _xfadjoint (Transducer変換)
    |               +-- foldl_impl
    |                       +-- _foldl_impl (iterateループ)
    |
    +-- [dims指定] sum(A; dims=d)
            +-- _sum(A, dims)
                +-- mapreduce(identity, add_sum, A; dims=d)
                    +-- mapreducedim!(f, op, R, A)
```

### データフロー図

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

itr (iterable)   ---->  mapreduce(f, op, ...)
                        |
                        +-- _xfadjoint: イテレータ変換を    ---->  スカラー値
                        |   RF合成に変換                            (sum結果、
                        +-- _foldl_impl / mapreduce_impl:          prod結果、
                            iterate + op で畳み込み                 max/min等)

A (AbstractArray) --->  _mapreduce(f, op, IndexStyle, A)
  + dims          --->  mapreducedim!(f, op, R, A)       ---->  縮退配列
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| reduce.jl | `base/reduce.jl` | ソース | 汎用リダクション関数（reduce, mapreduce, foldl, foldr, sum, prod, any, all等）の定義 |
| reducedim.jl | `base/reducedim.jl` | ソース | 多次元配列の次元指定リダクション（mapreducedim!, reducedim_init等）の定義 |
| abstractarray.jl | `base/abstractarray.jl` | ソース | AbstractArray の基本インタフェース定義 |
| iterators.jl | `base/iterators.jl` | ソース | Generator, Filter, Flatten 等のイテレータ型定義（Transducerパターンの入力） |
| simdloop.jl | `base/simdloop.jl` | ソース | @simd マクロの定義 |
