可以使用摺疊創建無限列表嗎？

Question

我寫了下面的代碼創建了斐波那契數的無限名單：

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

，在上面的代碼中使用foldl或foldr避免遞歸寫？

Answer 1

我不知道是否可以用foldl創建無限列表。你也許可以通過使用foldr來解決這個問題，但是你必須創建另一個列表來摺疊。那個清單會是什麼？斐波那契數字並沒有表明它們是從其他列表中產生的。

你想要的是使用unfoldr。它可以用來創建列表而不是使用它們，例如foldl和foldr。以下是如何使用unfoldr來生成斐波納契數字的無限列表。

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

您可以找到unfoldr在基礎包模塊Data.List英寸

Answer 2

您可以使用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 

一個簡單的例子，甚至不工作，就會對永遠循環。

Answer 3

foldl和foldr功能列表-消費者。正如svenningsson's answer正確地指出，unfoldr是一個列表-生產者它適合於捕獲co-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) [] 

爲每個輸入產生一點輸出，從無限輸入提供無限輸出。

厚臉皮的人可以因此表達任何infinitary遞歸作爲無限列表上的非遞歸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 4

避免顯式遞歸的一種方法是使用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)