结合foldl和foldr

Question

我已经发现自己当你想要将一个列表汇总到一个结果(即)时,foldl(或foldl')是最好的方法sum,并且foldr当你想要产生另一个(甚至是无限的)列表(即filter)时,这是最好的方法.

所以我正在考虑将这两者结合起来的处理.所以我做了这个功能sum_f.sum_f它是相当简单的,它只是添加列表的元素,但如果它找到一个如此f x为真的元素,它将当前结果作为输出作为列表的元素,并从该点开始全部求和.

代码在这里:

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

我想知道我是否可以在没有显式递归的情况下使用prelude函数编写上述函数(即只有prelude函数内的递归).抑或相结合的思路foldl,并foldr在这里的意思是,这里的递归不能用标准的前奏函数来完成的,需要是明确的？

Answer 1

您想要的只能使用右折叠表示如下:

{-# 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]