Equivalent of Scala's foldLeft in Java 8

Question

What is the equivalent of of Scala's great foldLeft in Java 8?

I was tempted to think it was reduce, but reduce has to return something of identical type to what it reduces on.

Example:

import java.util.List;

public class Foo {

    // this method works pretty well
    public int sum(List<Integer> numbers) {
        return numbers.stream()
                      .reduce(0, (acc, n) -> (acc + n));
    }

    // this method makes the file not compile
    public String concatenate(List<Character> chars) {
        return chars.stream()
                    .reduce(new StringBuilder(""), (acc, c) -> acc.append(c)).toString();
    }
}

The problem in the code above is the accumulator: new StringBuilder("")

Thus, could anyone point me to the proper equivalent of the foldLeft/fix my code?

Answer 1

There is no equivalent of foldLeft in Java 8's Stream API. As others noted, reduce(identity, accumulator, combiner) comes close, but it's not equivalent with foldLeft because it requires the resulting type B to combine with itself and be associative (in other terms, be monoid-like), a property that not every type has.

There is also an enhancement request for this: add Stream.foldLeft() terminal operation

To see why reduce won't work, consider the following code, where you intend to execute a series of arithmetic operations starting with given number:

val arithOps = List(('+', 1), ('*', 4), ('-', 2), ('/', 5))
val fun: (Int, (Char, Int)) => Int = {
  case (x, ('+', y)) => x + y
  case (x, ('-', y)) => x - y
  case (x, ('*', y)) => x * y
  case (x, ('/', y)) => x / y
}
val number = 2
arithOps.foldLeft(number)(fun) // ((2 + 1) * 4 - 2) / 5

If you tried writing reduce(2, fun, combine), what combiner function could you pass that combines two numbers? Adding the two numbers together clearly does not solve it. Also, the value 2 is clearly not an identity element.

Note that no operation that requires a sequential execution can be expressed in terms of reduce. foldLeft is actually more generic than reduce: you can implement reduce with foldLeft but you cannot implement foldLeft with reduce.

Answer 2

Update:

Here is initial attempt to get your code fixed:

public static String concatenate(List<Character> chars) {
        return chars
                .stream()
                .reduce(new StringBuilder(),
                                StringBuilder::append,
                                StringBuilder::append).toString();
    }

It uses the following reduce method:

<U> U reduce(U identity,
                 BiFunction<U, ? super T, U> accumulator,
                 BinaryOperator<U> combiner);

It may sound confusing but if you look at the javadocs there is a nice explanation that may help you quickly grasp the details. The reduction is equivalent to the following code:

U result = identity;
for (T element : this stream)
     result = accumulator.apply(result, element)
return result;

For a more in-depth explanation please check this source.

This usage is not correct though because it violates the contract of reduce which states that the accumulator should be an associative, non-interfering, stateless function for incorporating an additional element into a result. In other words since the identity is mutable the result will be broken in case of parallel execution.

As pointed in the comments below a correct option is using the reduction as follows:

return chars.stream().collect(
     StringBuilder::new, 
     StringBuilder::append, 
     StringBuilder::append).toString();

The supplier StringBuilder::new will be used to create reusable containers which will be later combined.

Answer 3

The method you are looking for is java.util.Stream.reduce, particularly the overload with three parameters, identity, accumulator, and binary function. That is the correct equivalent to Scala's foldLeft.

However, you are not allowed to use Java's reduce that way, and also not Scala's foldLeft for that matter. Use collect instead.

Answer 4

It can be done by using Collectors:

public static <A, B> Collector<A, ?, B> foldLeft(final B init, final BiFunction<? super B, ? super A, ? extends B> f) {
    return Collectors.collectingAndThen(
            Collectors.reducing(Function.<B>identity(), a -> b -> f.apply(b, a), Function::andThen),
            endo -> endo.apply(init)
    );
}

Usage example:

IntStream.rangeClosed(1, 100).boxed().collect(foldLeft(50, (a, b) -> a - b));  // Output = -5000

For your question, this does what you wanted:

public String concatenate(List<Character> chars) {
        return chars.stream()
                .collect(foldLeft(new StringBuilder(), StringBuilder::append)).toString();
}

Answer 5

Others are correct there's no equivalent though. Here's a util that comes close-

<U, T> U foldLeft(Collection<T> sequence, U identity, BiFunction<U, ? super T, U> accumulator) {
    U result = identity;
    for (T element : sequence)
        result = accumulator.apply(result, element);
    return result;
}

your case using the above method would look like-

public String concatenate(List<Character> chars) {
    return foldLeft(chars, new StringBuilder(""), StringBuilder::append).toString();
}

Or without the lambda method ref sugar,

public String concatenate(List<Character> chars) {
    return foldLeft(chars, new StringBuilder(""), (stringBuilder, character) -> stringBuilder.append(character)).toString();
}