1

リストを1つの結果（つまり）に要約する場合はfoldl（または）が最良のアプローチであり、別の（おそらく無限の）リスト（つまり）を生成する場合は最良のアプローチであると私は考えました。foldl'sumfoldrfilter

そこで、この2つを組み合わせた処理を考えていました。そこで、関数を作成しましたsum_f。sum_fはかなり単純で、リストのf x要素を合計するだけですが、trueのような要素が見つかった場合は、現在の結果がリストの要素として出力され、その時点から合計が開始されます。

コードはここにあります：

sum_f :: (Num a) => (a -> Bool) -> [a] -> [a]
sum_f f = 
  let
    sum_f_worker s (x:xs) = 
      let
        rec_call z = sum_f_worker z xs
        next_sum = s + x
      in
        next_sum `seq` if (f x) then next_sum : (rec_call 0) else rec_call next_sum
    sum_f_worker _ [] = []
  in
    sum_f_worker 0

たとえば、2の累乗でグループ化されたすべての正の整数を合計してみましょう。これにより、次のように出力されます。

[1, 2, 3+4, 5+6+7+8, 9+10+11+12+13+14+15+16, ...]

すなわち

[1, 2, 7, 26, 100, ...]

これは次のように実行できます。

import Data.Bits

main = 
  let
    power_of_two x = (x .&. (x - 1)) == 0 -- .&. is bitwise and
  in
    print $ take 25 $ sum_f power_of_two [(1::Integer)..]

これで、上記の関数（私は信じています）はfoldl'、グループが指数関数的に成長しても、（のように）一定の空間で実行されます。また、無限のリスト（などfoldr）でも機能します。

明示的な再帰なしで（つまり、プレリュード関数内の再帰のみ）プレリュード関数を使用して上記を記述できるかどうか疑問に思いました。または、ここでのアイデアを組み合わせるfoldlと、foldrここでの再帰は標準のプレリュード関数では実行できず、明示的にする必要があることを意味しますか？

4

1 に答える 1

5

あなたが望むものは、次のように右の折り目だけを使用して表現することができます：

{-# LANGUAGE BangPatterns #-}

sum_f :: (Num a) => (a -> Bool) -> [a] -> [a]
sum_f p xs = foldr g (const []) xs 0
  where
    g x f !a = if p x then x+a:f 0 else f (x+a)

Prelude Data.Bits> sum_f (\x -> x .&. pred x == 0) [1..10]
[1,2,7,26]

そしてそれは無限のリストで動作します：

Prelude Data.Bits> take 10 . sum_f (\x -> x .&. pred x == 0) $ [1..]
[1,2,7,26,100,392,1552,6176,24640,98432]
于 2013-03-14T17:26:47.267 に答える