Skip to content

Instantly share code, notes, and snippets.

@gakuzzzz
Last active November 29, 2020 09:20
Show Gist options
  • Save gakuzzzz/ead643ab1641bc360d171d586497c448 to your computer and use it in GitHub Desktop.
Save gakuzzzz/ead643ab1641bc360d171d586497c448 to your computer and use it in GitHub Desktop.
Java Stream API で foldLeft/foldRight その2

Java Stream API で foldLeft/foldRight で宿題にした StackOverflow しない実装の一例です。

面白ポイントとしては、foldRight/foldLeft の実装差分は Function::compose/Function::andThenEndo::compose/Endo::andThen に変わっただけ、という所ですね。

(注意)ただしこれは不変な List の concat を Stream を使って実装しているため、非常に遅いです。 高速な実装については読者への宿題とします。

/*
* 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.List;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.stream.Collector;
import java.util.stream.Stream;
import static java.util.stream.Collectors.toList;
import static java.util.stream.Stream.concat;
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), Endo::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), Endo::andThen),
endo -> endo.apply(init)
);
}
private static class Endo<A> implements Function<A, A> {
private final List<Function<? super A, ? extends A>> functions;
Endo(List<Function<? super A, ? extends A>> functions) {
this.functions = functions;
}
public A apply(A a) {
A sentinel = a;
for (var f : functions) {
sentinel = f.apply(sentinel);
}
return sentinel;
}
static <T> Endo<T> compose(Function<? super T, ? extends T> f, Function<? super T, ? extends T> g) {
return andThen(g, f);
}
@SuppressWarnings("unchecked")
static <T> Endo<T> andThen(Function<? super T, ? extends T> f, Function<? super T, ? extends T> g) {
var fs = f instanceof Endo ? ((Endo<T>) f).functions.stream() : Stream.of(f);
var gs = g instanceof Endo ? ((Endo<T>) g).functions.stream() : Stream.of(g);
return new Endo<T>(concat(fs, gs).collect(toList()));
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment