Posts Tagged ‘Fold’
[DevoxxFR2013] WTF – What’s The Fold?
Lecturer
Olivier Croisier operates as a freelance Java expert, trainer, and speaker through Moka Technologies. With over twelve years in the field, he assists clients in Java 8 migrations, advanced stack development, and revitalizing team enthusiasm for coding.
Abstract
Olivier Croisier elucidates the fold concept from functional programming, demonstrating its abstraction of iteration for enhanced code expressiveness. Using Java 8 streams and Haskell parallels, he dissects implementations, applications in mapping/filtering/reducing, and performance implications. The analysis positions fold as a versatile pattern surpassing traditional loops, integrable even in pre-Java 8 environments.
Origins and Essence: Fold as Iterative Abstraction
Croisier traces fold to functional languages like Haskell, where it generalizes accumulation over collections. Left fold (foldl) processes sequentially; right fold (foldr) enables laziness.
In essence, fold applies a binary operation cumulatively: start with accumulator, combine with each element.
Java analogy: external iterators (for-loops) versus internal (streams). Fold internalizes control, yielding concise, composable code.
Implementing Fold in Java: From Basics to Streams
Pre-Java 8, Croisier crafts a utility:
public static <T, R> R fold(Collection<T> coll, R init, BiFunction<R, T, R> f) {
R acc = init;
for (T e : coll) acc = f.apply(acc, e);
return acc;
}
Usage: sum integers—fold(list, 0, (a, b) -> a + b).
Java 8 streams natively provide reduce (fold alias):
int sum = list.stream().reduce(0, Integer::sum);
Parallel streams distribute: .parallelStream().reduce().
Croisier notes identity requirement for parallelism; non-associative operations risk inconsistencies.
Beyond Reduction: Mapping, Filtering, and Collection Building
Fold transcends summing; rebuild collections:
List<String> mapped = fold(list, new ArrayList<>(), (acc, e) -> { acc.add(transform(e)); return acc; });
Filter via conditional accumulation. This unifies operations—map/filter as specialized folds.
Haskell’s foldr constructs lists lazily, enabling infinite structures. Java’s eager evaluation limits but streams offer similar chaining.
Expressive Power and Performance Trade-offs
Croisier contrasts verbose loops with declarative folds, enhancing readability/maintainability. Encapsulate patterns in methods for reuse/optimization.
Performance: sequential folds match loops; parallel leverages multicore but incurs overhead (threading, combining).
JVM optimizations (invokedynamic for lambdas) potentially outperform anonymous classes. Croisier advocates testing under load.
Versus map-reduce: fold suits in-memory; Hadoop for distributed big data.
Integration Strategies and Broader Implications
Adopt incrementally: utility class for legacy code. Java 8+ embraces streams.
Croisier views fold as expressivity tool—not replacing conditionals but abstracting mechanics.
Implications: functional paradigms ease concurrency, prepare for multicore era. Fold’s versatility—from reductions to transformations—elevates code abstraction.