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 的回答正确指出的那样，是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. 它可以用来创建列表而不是使用它们，就像foldland一样foldr。下面介绍如何unfoldr生成无限的斐波那契数列。

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

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

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)

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

甚至不会工作，它会永远循环。