Haskell在Java 8中的等价折叠[重复]

This question already has an answer here:

这个问题在这里已有答案:

How to reduce given list by using Lambda expression .reduce() method 2 answers

如何使用Lambda表达式减少给定列表.reduce()方法2答案

We are used to foldr in Haskell where you take (for example, using Java syntax) a List<T> and you return whatever type you want (<T>, List<T>, etc.).

我们习惯于在Haskell中进行折叠(例如,使用Java语法)和List ,然后返回所需的任何类型( ,List 等)。

For example in Haskell, this function that takes a List<Integer> and return another List<Integer> and uses as an accumulator a List<Integer> (is only an example, the objetive of the function doesn't matter):

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

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

Now that Java 8 is out and have functional-style features, we want to write functions (not only the duplication-free equivalent of an List<T>) with a kind of foldr as we used here:

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

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

The problem using reduce is that when we take a List<T> we can only return a <T>, and we want to return a different type or even a collection.

使用reduce的问题是,当我们使用List 时,我们只能返回 ,并且我们想要返回不同的类型甚至是集合。

Is there any way of doing foldr in Java 8?

有没有办法在Java 8中进行foldr?

2 个解决方案

#1

I'm not strong on Java 8, but I think the road to your solution lies in how Haskell can provide a default foldr in terms of Foldable's fold.

我对Java 8并不擅长,但我认为解决问题的方法在于Haskell如何根据Foldable折叠提供默认的折叠。

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

where Endo a is just the monoid of endomorphisms under composition.

其中Endo a只是构成下的内同胚的幺半群。

So a solution could be to use Function<B,B> as an analogue for Endo b, and pass Function::compose to T reduce(T identity, BinaryOperator<T> accumulator) as the accumulator.

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

// 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

But I don't currently have a Java 8 compiler, so I can't test it.

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

If we wanted to do foldl, the solution would be similar, except we'd use Function::andThen.

如果我们想做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

#2

This method seems to be the closest counterpart:

这种方法似乎是最接近的对应方:

interface Stream<T> {
    // ...

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

    // ...
}

It's more like a mix of Haskell's foldMap and foldl', however, and not a fold from the right. This is probably the better choice for an eagerly evaluated language like Java—left folds with eager evaluation always run in constant space, whereas right folds with eager evaluation run in linear space—right folding a long list can blow the stack.

它更像是Haskell的foldMap和foldl'的组合,而不是右边的折叠。对于热切评估的语言来说,这可能是更好的选择,例如Java-left folds,急切的评估总是在恒定的空间中运行,而右侧折叠的热切评估在线性空间中运行 - 右侧折叠长列表可能会使堆栈崩溃。

In Haskell, since it has lazy evaluation, right folds with functions that are not strict on the spine of the list do often run in linear space. This is exploited for example in the following implementation of find, which does not have to evaluate the fold past the element that it returns:

在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

But such implementations are to be avoided in eager languages like Scheme, where you avoid using folds in such functions because you want them to exit early:

但是在诸如Scheme之类的急切语言中要避免使用这样的实现,在这种情况下,您可以避免在这些函数中使用折叠,因为您希望它们提前退出:

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

The other thing is that Java streams also are meant to support parallelism—so the operation it's designed so that elements may be visited out of order (and thus the Javadoc's insistence on associative operations).

另一件事是Java流也意味着支持并行性 - 所以它的设计操作使得元素可以不按顺序访问(因此Javadoc坚持关联操作)。

#1