haskell - fold 可以用来创建无限列表吗？

Question

我编写了以下代码，它创建了一个无限的斐波那契数列:

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

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

Answer 1

foldl和 foldr函数是列表消费者。如svenningsson's answer正确指出，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

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

虽然这种观察虽然是真实的，但很难表明一种健康的编程风格。