Tương đương foldr của Haskell trong Java 8

Question

Chúng tôi được sử dụng để foldr trong Haskell nơi bạn lấy (ví dụ, sử dụng cú pháp Java) List<T> và bạn trả về bất kỳ loại nào bạn muốn (<T>, List<T>, v.v.).

Ví dụ trong Haskell, chức năng này mà phải mất một List<Integer> và trở List<Integer> khác và sử dụng như một ắc một List<Integer> (được chỉ là ví dụ, các objetive của hàm không quan trọng):

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

Bây giờ Java 8 là ra ngoài và có các tính năng chức năng theo phong cách, chúng tôi muốn chức năng ghi (không chỉ tương đương với sự trùng lặp miễn phí của một List<T>) với một loại foldr như chúng ta sử dụng ở đây:

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

Sự cố khi sử dụng reduce là khi chúng tôi lấy số List<T>, chúng tôi chỉ có thể trả lại một số <T> và chúng tôi muốn trả về một loại khác hoặc thậm chí là một bộ sưu tập.

Có cách nào để thực hiện foldr trong Java 8 không?

Answer 1

Tôi không mạnh trên Java 8, nhưng tôi nghĩ con đường dẫn đến giải pháp của bạn nằm ở cách Haskell có thể cung cấp mặc định foldr về số .

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 

trong đó Endo a chỉ là monoid cấu trúc cuối cùng trong bố cục.

Vì vậy, một giải pháp có thể được sử dụng như một chất tương tự Function<B,B> cho Endo b, và vượt qua Function::compose để T reduce(T identity, BinaryOperator<T> accumulator) như 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 

Nhưng hiện tại tôi không có trình biên dịch Java 8, vì vậy tôi không thể kiểm tra nó.

Nếu chúng tôi muốn thực hiện foldl, giải pháp sẽ tương tự, ngoại trừ chúng tôi sẽ sử dụng 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 có vẻ là đối tác gần gũi nhất:

interface Stream<T> { 
    // ... 

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

    // ... 
} 

Nó giống như một sự pha trộn của Haskell của foldMap và foldl', tuy nhiên, và không phải là một lần từ bên phải. Điều này có lẽ là lựa chọn tốt hơn cho một ngôn ngữ được đánh giá háo hức như Java - các nếp gấp trái với sự đánh giá háo hức luôn chạy trong không gian cố định, trong khi các nếp gấp phải với việc đánh giá mong muốn chạy trong không gian tuyến tính.

Trong Haskell, vì nó có đánh giá lười biếng, nếp gấp phải với các hàm không nghiêm ngặt trên cột sống của danh sách thường chạy trong không gian tuyến tính.Này được khai thác ví dụ trong việc thực hiện sau đây của find, mà không nhất thiết phải đánh giá gấp quá khứ yếu tố đó nó sẽ trả về:

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 

Nhưng hiện thực như vậy là để tránh được bằng các ngôn ngữ háo hức như Đề án, nơi bạn tránh sử dụng nếp gấp trong các chức năng như vậy bởi vì bạn muốn họ để thoát sớm:

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

Một điều khác là Java suối cũng có nghĩa là để hỗ trợ xử lý song song-so hoạt động nó được thiết kế để các phần tử có thể được truy cập trong trật tự (và do đó sự nhấn mạnh của Javadoc về các hoạt động liên kết).