能否使用 fold 创建无限列表？

Question

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

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

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

- Dragno

---

虽然这很有趣，但实际上有更好的方法来做到这一点，那就是使用寻找斐波那契数列的闭式解。 - Andrew Walker

@AndrewWalker，使用浮点数算术运算并不能得到精确的解决方案。 - huon

请注意，在像Haskell这样的非严格函数式语言中，没有必要因为效率原因而避免递归，但出于风格原因避免使用递归是可以的。 - AndrewC

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

虽然这个观察结果是正确的，但并不意味着编程风格健康。

（其中更接近问题定义。）

- pigworker

---

谢谢您的回答，非常有趣。但是使用fib调用fib会使用递归，我们尝试避免使用fold。 - Dragno

我的术语中的 fib 是与 lambda 绑定的，而不是通过递归定义的。另一方面，我确实使用 foldr 来构建一个通用的不动点运算符。 - pigworker

在您的foldl定义中，您忘记了应用f。因此，foldl f a (b : bs) = foldl (f a b) bs必须更改为foldl f a (b : bs) = foldl f (f a b) bs。 - David Unric

Answer 2

我不知道是否可以使用foldl创建无限列表。也许你可以通过使用foldr解决这个问题，但那样你就需要创建另一个列表来进行折叠。那么这个列表应该是什么呢？斐波那契数列中没有任何提示表明它们是从其他列表生成的。

你想要的是使用unfoldr。它可以用于创建列表，而不是像foldl和foldr那样消耗列表。下面是如何使用unfoldr生成无限斐波那契数列的方法。

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

你可以在基本包中的模块Data.List中找到unfoldr函数。

- svenningsson

Answer 3

避免显式递归的一种方法是使用fix将递归表达为一个不动点。

import Data.Function (fix)

fibs = fix $ \l -> [1,1] ++ zipWith (+) l (tail l)

或者使用无参数样式的方式

import Data.Function (fix)
import Control.Monad.Instances

fibs = fix $ ([1,1] ++) . (zipWith (+) =<< tail)

- shang

Answer 4

您可以使用zipWith来编写您的定义。

fibonacci = 1:1:zipWith (+) fibonacci (tail fibonacci)

编辑： 好的，我认为你不能使用foldl或foldr来创建无限列表。在任何简单可想象的意义上都不行。 如果你看一下foldl的简单定义。

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

foldl在遍历完整个列表后才会返回。因此，一个简单的例子如下：

g = foldl f [] [1..]
 where 
  f xs a = xs ++ [a]

> take 10 g

这样做是行不通的，而且会一直循环下去。

- Satvik