ハスケルのJavaでのHaskellのfoldr 8

Question

ハスケルのfoldr（たとえば、Java構文を使用）にはList<T>が使用され、任意のタイプ（<T>、List<T>など）が返されます。

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

：ハスケル、アキュムレータList<Integer>（一例であり、関数のobjetiveは問題ではない）としてList<Integer>を取り、別のList<Integer>を返す使用し、この機能、例えば

我々がここで使用されるようになりましたJava 8が出ていると機能的なスタイルの機能を持っていることを、我々はfoldrの一種で書き込み機能（List<T>のだけではなく、重複のない相当）にしたい：

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>を返すことができ、別のタイプまたはコレクションを返すことになります。

Java 8でfoldrを実行する方法はありますか？

Answer 1

私は、Java 8の強くないんだけど、私はあなたの解決への道は、HaskellはFoldableのfoldの面でデフォルトfoldrを提供できるかにあると思います。

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は組成下の内在性の単相である。

そこで溶液は、Endo bためのアナログとしてFunction<B,B>使用 とアキュムレータとしてT reduce(T identity, BinaryOperator<T> accumulator)にFunction::composeを渡すことができました。

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

Answer 2

This method最も近い対応のようです：

interface Stream<T> { 
    // ... 

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

    // ... 
} 

それは右から倍しかし、HaskellのfoldMapとfoldl'のミックスのようなより多くのだ、とではありません。これは、熱心な評価が常に一定の空間で実行されるJavaの左の折りたたみのような熱心に評価された言語にとってはおそらく良い選択です。

ハスケルでは、怠惰な評価をしているので、リストの背骨に厳密でない関数を使った右折は、しばしば線形空間で実行されます。これは、それが返す要素を過ぎ倍を評価する必要はありません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 

しかし、このような実装では、あなたが避けるスキーム、のような熱心な言語で避けるべきですあなたは彼らが早く終了したいので、そのような機能で折り目を使用して：

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

他の事は、Javaはまた、要素の順序が訪問することができるように、それが設計されています並列処理-ので、操作をサポートすることを意図しているストリームということです（とJavadocは連想操作を主張している）。