可以折叠用于创建无限列表吗？

Question

我编写了以下代码,它创建了一个无限的Fibonacci数列表:

fibs = 1:1:fib 1 1
  where fib a b = a+b:fib b (a+b)

上面的代码可以使用foldl或foldr避免递归吗？

Answer 1

这些foldl和foldr功能是列表消费者.正如svenningsson的回答正确指出的那样,unfoldr是一个适合捕获共同结构的列表生成器.fibs

然而,考虑到foldl和foldr在他们的返回类型,即他们通过消耗列表产生什么多态,这是合理的问他们是否可能被用来消耗一个列表,并产生另一种.这些产生的列表中的任何一个都可能无限吗？

看看的定义 foldl

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a []        = a
foldl f a (b : bs)  = foldl f (f a b) bs

我们看到,为了foldl生产任何东西,它所消耗的清单必须是有限的.因此,如果foldl f a产生无限输出,那是因为它是a无限的,或者因为f有时执行无限列表生成.

这是一个不同的故事 foldr

foldr :: (b -> a -> a) -> a -> [b] -> a
foldr f a []        = a
foldr f a (b : bs)  = f b (foldr f a bs)

它承认f可能为b输入中消耗的每个产生一些输出的懒惰可能性.操作如

map g = foldr (\ b gbs -> g b : gbs) []   -- golfers prefer ((:) . g)
stutter = foldr (\ x xxs -> x : x : xxs) []

为每个输入产生一点输出,从无限输入提供无限输出.

因此,一个厚颜无耻的人可以表达任何无限递归作为foldr无限列表上的非递归.例如,

foldr (\ _ fibs -> 1 : 1 : zipWith (+) fibs (tail fibs)) undefined [1..]

(编辑:或者,就此而言

foldr (\_ fib a b -> a : fib b (a + b)) undefined [1..] 1 1

这更接近问题中的定义.)

虽然这种观察虽然是真实的,但并不能说明健康的编程风格.

Answer 2

我不知道是否可以创建无限列表foldl.你可以通过使用来解决这个问题foldr,但是你必须创建另一个折叠列表.那份清单是什么？斐波那契数字没有任何暗示它们是从其他列表中生成的.

你想要的是使用unfoldr.它可以用来创建列表,而不是消耗他们,因为是这样的foldl和foldr.以下是如何使用unfoldr生成无限的斐波纳契数列表.

fib = unfoldr (\(a,b) -> Just (a,(b,a+b))) (1,1)

您可以unfoldr在Data.List基础包中的模块中找到.