Java 8中类似于Haskell的foldr函数的等价实现

Question

我们在Haskell中习惯使用foldr，其中你可以（例如使用Java语法）将一个List<T>作为输入，返回任何类型的值（如<T>，List<T>等）。

例如，在Haskell中，以下函数接受一个List<Integer>并返回另一个List<Integer>，同时使用一个List<Integer>作为累加器（这仅是一个示例，函数的目标并不重要）:

evens :: [Integer] -> [Integer]
evens = foldr (\ x acc -> if mod x 2 == 0 then x : acc else acc) []

现在 Java 8 已经发布了并且具有函数式特性，我们想要使用一种类似于 foldr 的方式来编写函数（不仅仅是一个没有重复的List<T>）。

public static Double entropy (List<Double> probs){
    return -probs.stream().reduce(0.0, (acc, p) -> acc + p * Math.log(p, 2));
}

使用reduce的问题在于，当我们使用一个List<T>时，我们只能返回一个<T>，但我们希望返回不同类型甚至是一组。

在Java 8中是否有实现foldr的方法？

- Nico

---

你能提供一个输入/输出的样例，以更好地理解需求吗？ - Tunaki

如果我理解 Haskell 正确的话（我从未使用过 Haskell，但可以尝试），似乎您只过滤偶数元素并将它们收集到列表中。这将是：probs.stream().filter(i -> i % 2 == 0).collect(toList())。 - Tunaki

@Tunaki，问题在于我们需要一个类似于我们提供的示例中的累加器。 - Nico

那么这是一个重复的问题：https://dev59.com/Wojca4cB1Zd3GeqP1sYS - Tunaki

你有检查过另一个reduce方法吗？ - assylias

@assylias - 但是在OP的概念中没有“combiner” :) - ZhongYu

Answer 1

我对Java 8不是很熟悉，但我认为你解决问题的方法在于Haskell如何使用Foldable的fold提供默认的foldr。

foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo . f) t) z

foldMap :: (Foldable t, Functor t, Monoid m) => (a -> m) -> t a -> m
foldMap f = fold . fmap f

fold :: (Foldable t, Monoid m) => t m -> m

这里的 Endo a 只是组合下的自同态幺半群。

因此，一种解决方案是使用 Function<B,B> 作为 Endo b 的模拟， 并将 Function::compose 传递给 T reduce(T identity, BinaryOperator<T> accumulator) 作为累加器。

// given
//  BiFunction<A,B,B> step
//  B start
//  Stream<A> stream
stream                                            // Stream<A>
  .map((a) -> (b) -> step.apply(a,b))             // Stream<Function<B,B>>
  .reduce(Function.identity(), Function::compose) // Function<B,B>
  .apply(start)                                   // B

但是我目前没有Java 8编译器，所以无法测试。

如果我们想要执行foldl，解决方案将类似，只需使用Function::andThen。

// given
//  BiFunction<B,A,B> step
//  B start
//  Stream<A> stream
stream                                            // Stream<A>
  .map((a) -> (b) -> step.apply(b,a))             // Stream<Function<B,B>>
  .reduce(Function.identity(), Function::andThen) // Function<B,B>
  .apply(start)                                   // B

- rampion

Answer 2

这个方法 看起来是最接近的对应方法:

interface Stream<T> {
    // ...

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

    // ...
}

这更像是Haskell的foldMap和foldl'的混合体，而不是从右侧进行折叠。对于像Java这样的急切求值语言来说，这可能是更好的选择-使用渴望求值的左折叠总是在恒定空间中运行，而使用渴望求值的右折叠则在线性空间中运行-右折叠长列表可能会导致堆栈溢出。

在Haskell中，由于它具有惰性求值，对于不严格的函数，右折叠通常会在线性空间中运行。例如，在下面的find实现中利用了这一点，它不必评估超过返回元素的折叠：

find :: (a -> Bool) -> [a] -> Maybe a
find p = foldr go Nothing
   where go a next
     | p a = Just a     -- discards `next` without evaluating it
     | otherwise = next

但是在像Scheme这样的急切语言中，应该避免使用折叠操作来实现此类函数，因为你希望它们能够尽早退出：

(define (find pred? as)
  (and (not-null? as)
       (let ((head (car as)))
         (if (pred? head)
             head
             (find pred? (cdr as))))))

另一件事是 Java 流也旨在支持并行处理——因此它的设计使得元素可以无序访问（因此 Javadoc 强调关联操作）。

- Luis Casillas