结合foldl和foldr(Combining foldl and foldr)

结合foldl和foldr(Combining foldl and foldr)

我已经发现自己，当你想要将一个列表汇总到一个结果（即sum ）时， foldl （或foldl' ）是最好的方法，而当你想要产生另一个（甚至是无限的）时， 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

现在举例来说，让所有正整数除以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函数内的递归）。 或者将foldl和foldr的思想结合起来意味着这里的递归不能用标准的前奏函数完成，需要明确吗？

I've figured out myself that foldl (or foldl') is the best approach when you want to produce summarise a list into one result (i.e. sum), and foldr is the best approach when you want to produce another (perhaps even infinite) list (i.e. filter).

So I was considering was processing that combines these two. So I made the function sum_f. sum_f is fairly simple, all it does is add up the elements of a list, but if it finds an element such that f x is true, it gives the current result as output as the element of a list and starts summing from that point all over.

The code is here:

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

Now for example, lets sum all the positive integers grouped by any powers of two. This should output the following:

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

i.e.

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

We can do this like the following:

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

Now this above function (I believe) runs in constant space (like foldl'), even though the groups grow exponentially. Also, it works on infinite lists (like foldr).

I was wondering whether I could write the above using prelude functions without explicit recursion (i.e. only the recursion inside prelude functions). Or does combining the ideas of foldl and foldr here mean that the recursion here can't be done with standard prelude functions and needs to be explicit?

最满意答案

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

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

What you want can be expressed using only a right fold as follows:

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

And it works on infinite lists:

Prelude Data.Bits> take 10 . sum_f (\x -> x .&. pred x == 0) $ [1..] [1,2,7,26,100,392,1552,6176,24640,98432]结合foldl和foldr(Combining foldl and foldr)

我已经发现自己，当你想要将一个列表汇总到一个结果（即sum ）时， foldl （或foldl' ）是最好的方法，而当你想要产生另一个（甚至是无限的）时， 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

现在举例来说，让所有正整数除以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函数内的递归）。 或者将foldl和foldr的思想结合起来意味着这里的递归不能用标准的前奏函数完成，需要明确吗？

I've figured out myself that foldl (or foldl') is the best approach when you want to produce summarise a list into one result (i.e. sum), and foldr is the best approach when you want to produce another (perhaps even infinite) list (i.e. filter).

So I was considering was processing that combines these two. So I made the function sum_f. sum_f is fairly simple, all it does is add up the elements of a list, but if it finds an element such that f x is true, it gives the current result as output as the element of a list and starts summing from that point all over.

The code is here:

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

Now for example, lets sum all the positive integers grouped by any powers of two. This should output the following:

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

i.e.

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

We can do this like the following:

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

Now this above function (I believe) runs in constant space (like foldl'), even though the groups grow exponentially. Also, it works on infinite lists (like foldr).

I was wondering whether I could write the above using prelude functions without explicit recursion (i.e. only the recursion inside prelude functions). Or does combining the ideas of foldl and foldr here mean that the recursion here can't be done with standard prelude functions and needs to be explicit?

最满意答案

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

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

What you want can be expressed using only a right fold as follows:

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

And it works on infinite lists:

Prelude Data.Bits> take 10 . sum_f (\x -> x .&. pred x == 0) $ [1..] [1,2,7,26,100,392,1552,6176,24640,98432]