Haskell在Java 8中的倍增器

Question

我们已经习惯了foldr在Haskell中,你需要(例如,使用Java语法)一个List<T>和你回你想要的任何类型(<T>,List<T>,等).

例如在Haskell中,这个函数接受List<Integer>并返回另一个List<Integer>并用作累加器a List<Integer>(仅作为示例,函数的目标并不重要):

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

现在Java 8已经出来并且具有功能样式的特性,我们想要用我们在这里使用的那种函数来编写函数(不仅是一个无复制的等价函数List<T>)foldr:

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

使用的问题reduce是,当我们采取a时,List<T>我们只能返回a <T>,并且我们想要返回不同的类型甚至是集合.

foldr在Java 8中有什么办法吗？

Answer 1

我对 Java 8 不太熟悉，但我认为解决方案的关键在于 Haskell 如何提供'sfoldr方面的默认值。Foldablefold

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