结合foldl和foldr
我已经弄清楚自己foldl
(或foldl'
)是最好的方法,当你想产生一个列表到一个结果(即sum
),而foldr
是最好的方法,当你想产生另一个(甚至可能是无限的)列表(即filter
)。
所以我正在考虑将这两者结合起来进行处理。 所以我做了sum_f
函数。 sum_f
非常简单,它所做的就是将列表中的元素相加,但如果它找到一个使得fx
为真的元素,它将当前结果作为列表元素的输出并从该点开始总结。
代码在这里:
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
现在例如,让我们将所有正整数的和按任意两个幂进行分组。 这应该输出以下内容:
[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'
),即使这些组按指数foldl'
增长。 此外,它在无限列表上工作(如foldr
)。
我想知道我是否可以使用前奏函数而不用显式递归来编写上面的代码(即只有前奏函数内部的递归)。 或者在这里结合foldl
和foldr
的思想意味着这里的递归不能用标准的前奏函数来完成,并且需要明确吗?
你想要的东西只能用如下的正确折叠来表示:
{-# 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]
链接地址: http://www.djcxy.com/p/80729.html
上一篇: Combining foldl and foldr
下一篇: foldl and foldr?