Stream#reduceが分かる記事
こんにちは。
これは、JavaのStream APIのreduceをよく分かりたいという趣旨の記事です。
reduceはStream APIの中でも最も難解な関数のひとつだと思います。mapやfilterは使っているうちに慣れたという人でも、reduceをバリバリ使う人はあまりいないのではないでしょうか。
そして、そろそろreduceとかも知っておこうかな……と思ってドキュメントを読んでみたものの、見慣れない単語ににぎょっとして結局あまり使っていないという人は多いのではないでしょうか。
reduceにはいくつかのオーバーロードがありますので、それぞれの日本語の説明を引用してみます。
- 結合的累積関数を使用して、このストリームの要素に対してリダクションを実行し、リダクションされた値を記述するOptionalを返します(ある場合)。
- 指定された単位元の値と結合的な累積関数を使ってこのストリームの要素に対してリダクションを実行し、リデュースされた値を返します。
- 指定された単位元、累積関数、および結合的関数を使用して、このストリームの要素に対してリダクションを実行します。
これを読んでなるほどとなる人、関数のシグネチャが想像つく人はLGTMを押してブラウザバックです。あなたにこの記事は必要ありません。
なんとなく分かる気がするけどよく読むと単語一つ一つがなんかよく分からん、という人はこの記事の読者です。今のうちにストックを押しておくといいでしょう。
キーワードは「単位元」「結合的な関数」「累積関数」です。
Javaプログラマのためのモノイド
さっそく新しい単語が出てきて申し訳ないのですが、「結合的な関数」と「単位元」を持つ構造を「モノイド」と呼びます。
結合的な関数
ある関数が結合的であるとは、その二項関数が次のような性質を満たすことを言います。
(a \times b) \times c = a \times (b \times c)
$ \times $という演算が右結合でも左結合でも計算結果が変わらないよ、ということです。
Javaで書くと、次のような感じです。
次のようなクラスAとそのメソッドfがあったとして、
class A {
public A f(A a);
}
関数fが結合的であるとき、次を満たすことが期待できます。
@Test
void testAssociativity(A a, A b, A c) {
assertEquals(a.f(b).f(c), a.f(b.f(c)));
}
staticメソッドを使うともっと分かりやすいかもしれません。
次のようなクラスAと静的なメソッドfがあったとして、
class A {
public static A f(A a, A b);
}
結合的な関数fは次を満たします。
@Test
void testAssociativity(A a, A b, A c) {
assertEquals(f(f(a, b), c), f(a, f(b, c));
}
結合則は足し算や掛け算では当たり前の性質ですが、Javaコードで見るとずいぶん特殊な性質に見えますね。
単位元
ある二項関数 $\times$ における単位元とは、次のような等式を満たす元 $ e $ のことを言います。
a \times e = e \times a = a
Java風に書くと、次のような感じです。
次のような関数fと単位元eがあって、
class A {
public static A e = new A();
public A f(A a);
}
eがfの単位元であるとき、次を満たすことが期待できます。
@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があって、
class A {
public static A e = new A();
public static A f(A a, A b);
}
eがfの単位元であるとき、次が成り立ちます。
@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はまさに一般化された"畳み込み"そのものというわけですね。
畳み込み処理は下のような形で表現されます。
a_1 \times (a_2 \times (a_3 \times (\dots \times (a_{n - 1} \times a_n))))
これは$ a_1 $ から $ a_n $ までの値を $ \times $ という累積関数で畳み込んでいる、という風に読みます。
ちなみに上を右畳み込みといい、括弧を付ける順序を変えた下を左畳み込みといいます。
((((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を使いこなせそうなことが分かって頂けたと思います。
そこで最後におまけとしてプログラミングによく現れる色々なモノイドを見ていきましょう。
-
数値の足し算
まずは
int,+,0の組です。これは直観的に分かりますね。(m + n) + l = m + (n + l) // associativity n + 0 = 0 + n = n // identityreduceに入れてあげると、合計を計算するsumを実装できます。上の例で出した通り、
int,*,1でも同じようにモノイドになります。 -
リストの結合
次に、
ArrayList,ArrayList#addAll,new ArrayList()の組もモノイドを構成します。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に入れてあげると、全てのリストを結合させた一つのリストを作ることができます。 -
min
次は
int,Math.min,Integer.MAX_VALUEを見ていきましょう。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もモノイドを形成します。 -
論理AND (
&&)まだまだあります。
boolean,&&,trueもまたモノイドを形成します。(m && n) + && = m && (n && l) // associativity n && true = true && n = n // identity言われてみればそりゃそうですよね。
reduceに入れてあげると、Streamの中の全ての値がtrueであるかどうかを検証することができます。同様にして
boolean,||,falseもモノイドを形成します。 -
ビットAND (
&)ビットAND自体あまり使わないかもしれませんが、
int,&,~0というビットANDもモノイドを形成します。(m & n) + & = m & (n & l) // associativity n & (~0) = (~0) & n = n // identityreduceに入れてあげると、Streamの中の全ての値のビットANDを取ることができます。同様にして
int,|,0もモノイドを形成します。 -
エルビス演算子 (
?:) または null合体演算子 (??)エルビス演算子はJavaにはありませんが、GroovyやKotlinにはある便利なやつです。
C# ではnull合体演算子と呼ばれますね。
これは左辺がnullだった場合に右辺を返すという演算子なのですが、面白いことにT,?:,nullという組がモノイドを形成します。(a ?: b) ?: c = a ?: (b ?: c) // associativity null ?: a = a ?: null = a // identityこのエルビス演算子は、Javaで書くとちょうど次のような関数です。
public static <T> T elvis(T a, T b) { return a != null ? a : b }少し変わり種ですが、面白いですよね。
reduceに入れてあげると、Streamの中の最初の非nullの値を取ることができます。 -
関数合成 (
Function#andThen)もう一つ変わり種で、
Function,Function#andThen,Function.identity()はモノイドを形成します。f.andThen(g).andThen(h) = a.andThen(g.andThen(h)) // associativity f.andThen(Function.identity()) = Function.identity().andThen(f) // identityFunction.identity()は何もしない関数です。reduceに入れてあげると、全ての関数を実行する一つの関数を取得できます。 -
アプリケーション設定
最後は自作の型でモノイドを作って
reduceしてみましょう。
ある程度実用的な例として、何かしらのアプリケーションの設定をモノイドにしてみます。このアプリケーションは設定を1. 設定ファイル 2. 環境変数 3. コマンドライン引数 で指定でき、さらに設定は1 < 2 < 3の順序で優先するような、よくある仕様とします。
アプリケーション設定を次のようなクラスで表現します。
class ApplicationConfig { private String field1; // 他にもたくさんのフィールド... public Applicationconfig(String field1, ...) { this.field1 = field1; ... } public String getField1() { return this.field1; } ... }まず、2つのアプリケーション設定を合成するような関数と、その合成の単位元を定義します。
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すれば期待する設定を得ることができます。ApplicationConfig config = Stream.of( loadConfigFromCommandLine(), loadConfigFromEnvironmentVariables(), loadConfigFromFiles() ).reduce(ApplicationConfig.identity, ApplicationConfigUtils::compose);
終わりに
モノイドを勉強することで、Stream#reduceが分かった。