Stream#reduceが分かる記事

# Stream#reduceが分かる記事

　こんにちは。
　これは、JavaのStream APIの`reduce`をよく分かりたいという趣旨の記事です。

　`reduce`はStream APIの中でも最も難解な関数のひとつだと思います。`map`や`filter`は使っているうちに慣れたという人でも、`reduce`をバリバリ使う人はあまりいないのではないでしょうか。
　そして、そろそろ`reduce`とかも知っておこうかな……と思って[ドキュメント](https://docs.oracle.com/javase/jp/11/docs/api/java.base/java/util/stream/Stream.html#reduce(java.util.function.BinaryOperator))を読んでみたものの、見慣れない単語ににぎょっとして結局あまり使っていないという人は多いのではないでしょうか。
　`reduce`にはいくつかのオーバーロードがありますので、それぞれの日本語の説明を引用してみます。

> - 結合的累積関数を使用して、このストリームの要素に対してリダクションを実行し、リダクションされた値を記述するOptionalを返します(ある場合)。
> - 指定された単位元の値と結合的な累積関数を使ってこのストリームの要素に対してリダクションを実行し、リデュースされた値を返します。
> - 指定された単位元、累積関数、および結合的関数を使用して、このストリームの要素に対してリダクションを実行します。

　これを読んでなるほどとなる人、関数のシグネチャが想像つく人はLGTMを押してブラウザバックです。あなたにこの記事は必要ありません。
　なんとなく分かる気がするけどよく読むと単語一つ一つがなんかよく分からん、という人はこの記事の読者です。今のうちにストックを押しておくといいでしょう。

　キーワードは「単位元」「結合的な関数」「累積関数」です。

## Javaプログラマのためのモノイド

　さっそく新しい単語が出てきて申し訳ないのですが、「結合的な関数」と「単位元」を持つ構造を「モノイド」と呼びます。

### 結合的な関数

　ある関数が結合的であるとは、その二項関数が次のような性質を満たすことを言います。

```math
(a \times b) \times c = a \times (b \times c)
```

　$ \times $という演算が右結合でも左結合でも計算結果が変わらないよ、ということです。

　Javaで書くと、次のような感じです。
　次のようなクラス`A`とそのメソッド`f`があったとして、

```java
class A {
    public A f(A a);
}
```

　関数`f`が結合的であるとき、次を満たすことが期待できます。

```java
@Test
void testAssociativity(A a, A b, A c) {
    assertEquals(a.f(b).f(c), a.f(b.f(c)));
}
```

　`static`メソッドを使うともっと分かりやすいかもしれません。
　次のようなクラス`A`と静的なメソッド`f`があったとして、

```java
class A {
    public static A f(A a, A b);
}
```

　結合的な関数`f`は次を満たします。

```java
@Test
void testAssociativity(A a, A b, A c) {
    assertEquals(f(f(a, b), c), f(a, f(b, c));
}
```

　結合則は足し算や掛け算では当たり前の性質ですが、Javaコードで見るとずいぶん特殊な性質に見えますね。

### 単位元

　ある二項関数 $\times$ における単位元とは、次のような等式を満たす元 $ e $ のことを言います。

```math
a \times e = e \times a = a
```

　Java風に書くと、次のような感じです。
　次のような関数`f`と単位元`e`があって、

```java
class A {
    public static A e = new A();
    public A f(A a);
}
```

　`e`が`f`の単位元であるとき、次を満たすことが期待できます。

```java
@Test
void testLeftIdentity(A a) {
    A actual = A.e.f(a);
    assertEquals(a, actual);
}

@Test
void testRightIdentity(A a) {
    A actual = a.f(A.e);
    assertEquals(a, actual);
}
```

　結合則のとき同様に、`static`な`f`でも書いてみましょうか。
　次のような静的な関数`f`と単位元`e`があって、

```java
class A {
    public static A e = new A();
    public static A f(A a, A b);
}
```

　`e`が`f`の単位元であるとき、次が成り立ちます。

```java
@Test
void testLeftIdentity(A a) {
    A actual = A.f(a, A.e);
    assertEquals(a, actual);
}

@Test
void testRightIdentity(A a) {
    A actual = A.f(A.e, a);
    assertEquals(a, actual);
}
```

　足し算における $0$, 掛け算における $1$ が単位元ですね。

## Javaプログラマのための畳み込み

　ようやく本題ですね。
　Javaでは「リダクション」「リデュース」などと呼ばれるものは、一般には畳み込み処理と呼ばれます。
　畳み込み処理とは、簡単に言えば複数の値を一つの値にする処理のことで、例えば合計を取る`IntStream#sum`や長さを取る`List#size`は代表的な畳み込み処理だといえます。

　つまり、`Stream#reduce`はまさに一般化された"畳み込み"そのものというわけですね。

　畳み込み処理は下のような形で表現されます。

```math
a_1 \times (a_2 \times (a_3 \times (\dots \times (a_{n - 1} \times a_n))))
```

　これは$ a_1 $ から $ a_n $ までの値を $ \times $ という**累積関数**で畳み込んでいる、という風に読みます。
　ちなみに上を右畳み込みといい、括弧を付ける順序を変えた下を左畳み込みといいます。

```math
((((a_1 \times a_2) \times a_3) \times \dots) \times a_{n - 1}) \times a_n
```

　ここで、累積関数 $ \times $ が[結合的](#結合的な関数)だった場合、右畳み込みと左畳み込みの結果が変わらないことが分かります。この性質は、並列Streamを処理するときに特に役に立ちます。
　さらに[単位元](#単位元)を要素数`0`のときの値とすることで、結果が`Optional`にならない`reduce`を作ることができます。

　このように、モノイドと畳み込み処理は非常に相性が良いのです。

### `reduce` 3種類のまとめ

　以上を踏まえて3種類ある`reduce`のオーバーロードの型に説明を付けていきましょう。

- `Optional<T> reduce​(BinaryOperator<T> accumulator)`
    - 結合的な累積関数`accumulator`を用いて、Streamを畳み込む
    - Streamの長さが`0`の場合は`Optional.empty`が返る
- `T reduce​(T identity, BinaryOperator<T> accumulator)`
    - 結合的な累積関数`accumulator`を用いて、Streamを畳み込む
    - Streamの長さが`0`の場合は`identity`が返る
- `<U> U reduce​(U identity, BiFunction<U,​? super T,​U> accumulator, BinaryOperator<U> combiner)`
    - `T`からモノイド`U`への変換機能と累積関数を兼ねた少し特殊な`accumulator`を使って畳み込む
    - 並列Streamの場合は畳み込み結果が複数生まれるので、それを`combiner`を使ってもう一度畳み込む

　前とは違って、この説明が読めるようになっていれば`reduce`を分かったことになります。
　また、うっかり`BinaryOperator`を結合的ではない実装にしてしまい、並列Streamの時だけ挙動が変という厄介な`reduce`を書いてしまう心配もありません。

### 付録：プログラミングに表れる色々なモノイド

　さて、モノイドを知ると`reduce`を使いこなせそうなことが分かって頂けたと思います。
　そこで最後におまけとしてプログラミングによく現れる色々なモノイドを見ていきましょう。

1. 数値の足し算

    　まずは`int`, `+`, `0`の組です。これは直観的に分かりますね。

    ```java
    (m + n) + l = m + (n + l) // associativity
    n + 0 = 0 + n = n         // identity
    ```

    　`reduce`に入れてあげると、合計を計算する`sum`を実装できます。

    　上の例で出した通り、`int`, `*`, `1`でも同じようにモノイドになります。

2. リストの結合

    　次に、`ArrayList`, `ArrayList#addAll`, `new ArrayList()`の組もモノイドを構成します。

    ```java
    list1.addAll(list2.addAll(list3)) = list1.addAll(list2).addAll(list3) // associativity
    (new ArrayList()).addAll(list) = list.addAll(new ArrayList()) = list  // identity
    ```

    　通常、空のリストには`Collection.emptyList()`を使いますが、ここでは`addAll`を使う関係で`new ArrayList()`としています。
    　また必ずしも`ArrayList`である必要はなく、Listライクな構造であれば何でもモノイドを作れそうです。例えば`String`, `+`, `""`でもリストのモノイドの例になりそうです。

    　`reduce`に入れてあげると、全てのリストを結合させた一つのリストを作ることができます。

3. min

    　次は`int`, `Math.min`, `Integer.MAX_VALUE`を見ていきましょう。

    ```java
    Math.min(Math.min(m, n), l) = Math.min(m, Math.min(n, l))            // associativity
    Math.min(n, Integer.MAX_VALUE) = Math.min(Integer.MAX_VALUE, n) = n  // identity
    ```

    　引数のうちより小さい方の値を返す`Math.min`関数は、その型の最大値とモノイドを形成します。
    　結合則は比較順序に拘わらず3つの数のうちの最小値を取れることを示していますね。

    　`reduce`に入れてあげると、Streamの中の最小値を取得することができます。

    　同様にして、`int`, `Math.max`, `Integer.MIN_VALUE`もモノイドを形成します。

4. 論理AND (`&&`)

    　まだまだあります。`boolean`, `&&`, `true`もまたモノイドを形成します。

    ```java
    (m && n) + && = m && (n && l) // associativity
    n && true = true && n = n     // identity
    ```

    　言われてみればそりゃそうですよね。

    　`reduce`に入れてあげると、Streamの中の全ての値が`true`であるかどうかを検証することができます。

    　同様にして `boolean`, `||`, `false`もモノイドを形成します。

5. ビットAND (`&`)

    　ビットAND自体あまり使わないかもしれませんが、`int`, `&`, `~0`というビットANDもモノイドを形成します。

    ```java
    (m & n) + & = m & (n & l) // associativity
    n & (~0) = (~0) & n = n   // identity
    ```

    　`reduce`に入れてあげると、Streamの中の全ての値のビットANDを取ることができます。

    　同様にして `int`, `|`, `0`もモノイドを形成します。

6. エルビス演算子 (`?:`) または null合体演算子 (`??`)

    　エルビス演算子はJavaにはありませんが、GroovyやKotlinにはある便利なやつです。
    　C# ではnull合体演算子と呼ばれますね。
    　これは左辺が`null`だった場合に右辺を返すという演算子なのですが、面白いことに`T`, `?:`, `null`という組がモノイドを形成します。

    ```kotlin
    (a ?: b) ?: c = a ?: (b ?: c) // associativity
    null ?: a = a ?: null = a     // identity
    ```

    　このエルビス演算子は、Javaで書くとちょうど次のような関数です。

    ```java
    public static <T> T elvis(T a, T b) {
        return a != null ? a : b
    }
    ```

    　少し変わり種ですが、面白いですよね。
    　`reduce`に入れてあげると、Streamの中の最初の非`null`の値を取ることができます。

7. 関数合成 (`Function#andThen`)

    　もう一つ変わり種で、`Function`, `Function#andThen`, `Function.identity()`はモノイドを形成します。

    ```java
    f.andThen(g).andThen(h) = a.andThen(g.andThen(h))               // associativity
    f.andThen(Function.identity()) = Function.identity().andThen(f) // identity
    ```

    　`Function.identity()`は何もしない関数です。

    　`reduce`に入れてあげると、全ての関数を実行する一つの関数を取得できます。

8. アプリケーション設定

    　最後は自作の型でモノイドを作って`reduce`してみましょう。
    　ある程度実用的な例として、何かしらのアプリケーションの設定をモノイドにしてみます。

    　このアプリケーションは設定を1. 設定ファイル 2. 環境変数 3. コマンドライン引数 で指定でき、さらに設定は1 < 2 < 3の順序で優先するような、よくある仕様とします。

    　アプリケーション設定を次のようなクラスで表現します。

    ```java
    class ApplicationConfig {
        private String field1;
        // 他にもたくさんのフィールド...
        public Applicationconfig(String field1, ...) {
            this.field1 = field1;
            ...
        }
        public String getField1() {
            return this.field1;
        }
        ...
    }
    ```

    　まず、2つのアプリケーション設定を合成するような関数と、その合成の単位元を定義します。

    ```java
    final class ApplicationConfigUtils {
        // 単位元。フィールド全てにnullを指定する
        public static ApplicationConfig identity = new ApplicationConfig(null, ...);

        // 結合的な二項演算
        public static ApplicationConfig compose(ApplicationConfig a, ApplicationConfig b) {
            return new ApplicationConfig(
                a.getField1() != null ? a.getField1() : b.getField1(),
                ...
            );
        }
    }
    ```

    　前準備はこれだけです。
    　各パラメータを読み込む関数を作り、`Stream.of`に並べて`reduce`すれば期待する設定を得ることができます。

    ```java
    ApplicationConfig config = Stream.of(
            loadConfigFromCommandLine(),
            loadConfigFromEnvironmentVariables(),
            loadConfigFromFiles()
    ).reduce(ApplicationConfig.identity, ApplicationConfigUtils::compose);
    ```

## 終わりに

　モノイドを勉強することで、`Stream#reduce`が分かった。