Java 8中类似于Scala的foldLeft函数的等效实现方式

Question

Scala中很棒的foldLeft在Java 8中有什么等价物吗？

我曾经认为答案是reduce，但是reduce需要返回与其减少的对象类型相同的对象。

例如：

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();
    }
}

上面代码中的问题在于累加器：new StringBuilder("")

因此，有没有人能够指点我正确的等价于foldLeft的方法或者修复我的代码？

- GA1

---

请注意：该语言的名称是“Scala”，而不是“SCALA”。（我相信有一种名为“SCALA”的不同语言，这可能不是您想要的那种。） - Jörg W Mittag

相关内容：https://dev59.com/9Yvda4cB1Zd3GeqPd8i5 - Tunaki

除非你有证据证明有另一种同名但大写的语言，否则我会非常惊讶。我认为大写的拼写来自于习惯将语言大写的老经理们，比如BASIC和FORTRAN :D - nafg

@nafg：我试着在谷歌上搜索，但是有点难，因为搜索“SCALA”也会返回“Scala”的结果。我相信我在IBM中端系统上看到过它，当时我们称之为“大数据分析”，但在“大数据”（或Scala）出现之前。然而，我个人从未在IBM中端系统上工作过，因此我无法记住相关工具、框架、库或语言的名称，以进行更好的谷歌查询。Scala用于大数据，并且IBM正在大力推广Scala这一事实也没有帮助。 - Jörg W Mittag

Answer 1

Java 8的Stream API中没有foldLeft的等效方法。正如其他人所指出的，reduce(identity, accumulator, combiner)接近，但它与foldLeft不等价，因为它需要结果类型B与自身组合并且是可结合的（换句话说，类似于单子），而并非每种类型都具有该属性。

也有一个增强请求：添加Stream.foldLeft()终端操作

为了说明为什么reduce不能工作，请考虑以下代码，其中你打算执行一系列算术运算，从给定数字开始：

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

如果您尝试编写reduce(2, fun, combine)，那么您可以传递哪个组合器函数来将两个数字组合起来？显然将这两个数字相加并不能解决问题。另外，值2显然不是一个恒等元素。

请注意，任何需要顺序执行的操作都无法用reduce表达。实际上，foldLeft比reduce更通用：您可以使用foldLeft实现reduce，但您无法使用reduce实现foldLeft。

- dzs

Answer 2

更新：

这是修复您代码的初始尝试：

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

它使用以下的reduce方法：reduce method。

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

这可能听起来有点困惑，但如果您查看Javadocs，那里有一个很好的解释，可以帮助您快速掌握细节。简化等同于以下代码：

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

为了更深入的解释，请查看这个来源。

然而，此用法是不正确的，因为它违反了reduce的契约，该契约规定累加器应该是一个“关联的、非干扰的、无状态的函数，用于将附加元素合并到结果中”。换句话说，由于身份标识是可变的，在并行执行的情况下，结果将被破坏。

如下所示，正如下面的评论所指出的，正确的选项是使用reduction:

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

供应商 StringBuilder::new 将用于创建可重复使用的容器，稍后将进行组合。

- Lachezar Balev

---

和另一个答案一样：不要这样使用reduce。函数不允许修改它们的参数。正确的用法是.collect(StringBuilder::new, StringBuilder::append, StringBuilder::append)。请参见可变归约。 - Holger

这不是关于效率的问题，而是关于正确性的问题。以这种方式使用reduce违反了契约，并且必须被视为已经损坏，即使在某些情况下它可能会达到预期的效果。特别需要注意的是，当使用并行流时，它肯定会出错。 - Holger

你是在考虑连接字符的顺序还是构建器的状态？ - Lachezar Balev

这段内容涉及到对 StringBuilder 的修改。顺序没有问题。 - Holger

我在想如果我们将流并行化，那么使用StringBuilder会是线程安全的吗？ - Mr.Q

Answer 3

您要查找的方法是 java.util.Stream.reduce，特别是具有三个参数的重载版本，即标识、累加器和二元函数。那是 Scala 的 foldLeft 的正确等价物。

但是，您不允许以这种方式使用 Java 的 reduce，同样也不能使用 Scala 的 foldLeft。请改用 collect。

- Jörg W Mittag

---

虽然我喜欢你的回答，但是“你不被允许”似乎有些不妥。你能否重新表述一下？ - Sean Patrick Floyd

如果Java的类型系统足够表达该约束，则会出现类型错误。但事实并非如此，因此该约束仅在JavaDocs中提到。JavaDocs指定了允许传递哪些类型的对象，而OP传递的对象不满足这些约束，因此她无法调用“reduce”。你还有其他的表述方式吗？ - Jörg W Mittag

没有类型限制，只有对象使用的限制。如果您使用累加器和组合函数，例如(a,b) -> new StringBuilder().append(a).append(b)，这是合法的用法，尽管与collect解决方案相比不太高效。 - Holger

除了这不只是反模式，它根本就不被该方法的文档所允许。反模式可能会导致难以维护的代码，但原帖中的代码完全有问题，已经崩溃了，不能工作。 - Jörg W Mittag

这个回答是完全错误的。Stream的reduce(identity, accumulator, combiner)需要一个可结合的组合函数，这不是foldLeft的要求，因此，并非每个foldLeft结构都可以被重写为reduce。请看下面的例子，其中减法和除法不是可结合的： 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 } ops.foldLeft(2)(fun) // ((2 + 1) * 4 - 2) / 5``` - dzs

Answer 4

你可以使用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)
    );
}

使用示例：

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

对于您的问题，这样做可以实现您想要的功能：

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

- yi-ji

---

收集器必须遵守"关联性约束"（请参阅javadoc），这意味着此代码不遵守foldLeft的"左部分"。一个由(1, 2) 组成的流可以通过执行finisher.apply(combiner.apply(accumulator.accept(supplier.get(), 1), accumulator.accept(supplier.get(), 2)))来进行收集。如果您尝试使用Collectors.reducing来创建累积列表（例如，[[], [1], [1, 2]]），那么您可能会得到[[], [1], [], [2]]。 - Daniel C. Sobral

Answer 5

其他人是正确的，没有相应的等价物。这里有一个工具，它接近-

<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;
}

你的案例使用上述方法将如下所示 -

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

或者不使用 lambda 方法的 ref 糖语法，

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

- Gagandeep Kalra