Haskell's foldr equivalent in Java 8 [duplicate]

Question

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.).

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):

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:

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.

Is there any way of doing foldr in Java 8?

Answer 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.

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.

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.

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

If we wanted to do foldl, the solution would be similar, except we'd use 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

Answer 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.

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:

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:

(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).