Skip to content

Instantly share code, notes, and snippets.

@gakuzzzz
Last active February 26, 2021 11:20
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save gakuzzzz/4a02de328dec6a3348408231685c9fa9 to your computer and use it in GitHub Desktop.
Save gakuzzzz/4a02de328dec6a3348408231685c9fa9 to your computer and use it in GitHub Desktop.
Java Stream API で foldLeft/foldRight

Java8以降の Stream API で畳み込みを行いたい場合は Stream#reduceCollectors.reducing を使用します。

しかし、Stream API は基本的に parallel で動作する事を考慮に入れる必要があるため、Stream#reduce および Collectors.reducing には強い制約があります。 つまり、初期値は必ず単位元である必要があり、演算は結合則を満たす必要があります。

試しにその制約を満たしていない引数を渡すと、結果が定まらない事が見て取れます。 例えば 50 という初期値から 1~100 までの数値を順番に引いていくと -5000 になるはずです。

IntStream.rangeClosed(1, 100).boxed().parallel().reduce(50, (a, b) -> a - b, (a, b) -> a + b); // -3250 になる
IntStream.rangeClosed(1, 100).boxed().reduce(50, (a, b) -> a - b, (a, b) -> a + b);            // -5000 になる

ところが実際に試してみると実行環境によって結果は不定になります。

しかし、実際にはもっとカジュアルに結合則を満たさないような演算で畳み込みしたいケースが多々あります。

そこで foldLeft, foldRight をする Collector を作成してみました。 こちらを利用する事で結合則を満たさない演算でも期待通りに畳み込みをする事ができます。

IntStream.rangeClosed(1, 100).boxed().parallel().collect(foldLeft(50, (a, b) -> a - b));  // -5000 になる
IntStream.rangeClosed(1, 100).boxed().collect(foldLeft(50, (a, b) -> a - b));             // -5000 になる

めでたしめでたし。

MIT License にしとくので適当にコピペして使ってください。

(注意)ちなみにこの実装は素朴な実装のため、巨大なStreamで使用すると StackOverflow します。 StackOverflow しない実装については読者への宿題とします。

/*
* foldLeft/foldRight Collector
*
* Copyright(c) gakuzzzz
*
* This software is released under the MIT License.
* http://opensource.org/licenses/mit-license.php
*/
package jp.t2v.lab;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.stream.Collector;
import static java.util.stream.Collectors.collectingAndThen;
import static java.util.stream.Collectors.reducing;
public class Collectors2 {
public static <A, B> Collector<A, ?, B> foldRight(final B init, final BiFunction<? super A, ? super B, ? extends B> f) {
return collectingAndThen(
reducing(Function.<B>identity(), a -> b -> f.apply(a, b), Function::compose),
endo -> endo.apply(init)
);
}
public static <A, B> Collector<A, ?, B> foldLeft(final B init, final BiFunction<? super B, ? super A, ? extends B> f) {
return collectingAndThen(
reducing(Function.<B>identity(), a -> b -> f.apply(b, a), Function::andThen),
endo -> endo.apply(init)
);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment