Эквивалент Хаскелла в Java 8

Question

Мы привыкли к foldr в Haskell, где вы берете (например, используя синтаксис 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 вышла и имеет функциональные возможности, мы хотим написать функции (не только эквивалент без дублирования 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 это когда мы берем List<T> мы можем только вернуть <T>и мы хотим вернуть другой тип или даже коллекцию.

Есть ли способ сделать foldr в Java 8?

Answer 1

Этот метод, кажется, ближайший аналог:

interface Stream<T> {
    // ...

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

    // ...
}

Это больше похоже на смесь Хаскелла 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 в отношении ассоциативных операций).

Answer 2

Я не силен в Java 8, но я думаю, что путь к вашему решению лежит в том, как Haskell может предоставить по умолчанию foldr с точки зрения 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

где 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