È possibile utilizzare la piega per creare elenchi infiniti?

Question

ho scritto il seguente codice che crea una lista infinita di numeri di Fibonacci:

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

Può il codice di cui sopra essere scritta utilizzando foldl o foldr per evitare la ricorsione?

Answer 1

Non so se è possibile creare elenchi infiniti con foldl. Potresti forse risolvere questo problema usando foldr, ma poi dovresti creare un altro elenco da ripiegare. Cosa sarebbe quella lista? Non c'è nulla con i numeri di Fibonacci che suggeriscono che siano generati da qualche altra lista.

Quello che vuoi invece è usare unfoldr. Può essere utilizzato per creare elenchi anziché consumarli, come nel caso di foldl e foldr. Ecco come utilizzare unfoldr per generare l'elenco infinito di numeri di Fibonacci.

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

Potete trovare unfoldr nel modulo Data.List nel pacchetto base.

Answer 2

È possibile utilizzare zipWith di scrivere la tua definizione

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

edit: Ok, io non credo che si possa utilizzare foldl o foldr per creare lista infinita. Non in un semplice senso immaginabile. Se si guarda alla semplice definizione di foldl

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

foldl mai restituisce fino a quando non ha esaurito l'intera lista. Quindi, un semplice esempio come

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

> take 10 g 

non funzionerà nemmeno ed è in loop per sempre.

Answer 3

Le funzioni foldl e foldr sono elenco- consumatori. Come svenningsson's answer giustamente sottolinea, unfoldr è una lista- produttore che è adatto per catturare la struttura -recursive co di fibs.

Tuttavia, dato che foldl e foldr sono polimorfici nei loro tipi di ritorno, vale a dire ciò che producono consumando un elenco, è ragionevole chiedersi se potrebbero essere utilizzati per consumare un elenco e generarne un altro. Qualcuno di questi elenchi prodotti potrebbe essere infinito?

Guardando la definizione di foldl

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

vediamo che per foldl per produrre qualcosa, la lista che consuma deve essere finito. Quindi se foldl f a produce un output infinito, è perché a è infinito o perché lo f a volte esegue la generazione di liste infinite.

E 'una storia diversa con foldr

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

che ammette la possibilità pigro che f potrebbe generare una certa uscita per ogni b consumato dall'ingresso. Operazioni come

produrre un po 'di output per ogni input, fornire un output infinito da input infinito.

Una persona sfacciata può così esprimere qualsiasi ricorsione infinita come una foldr non ricorsiva su una lista infinita. Ad esempio,

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

(Edit:. O, se è per questo

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

che è più vicino alla definizione in questione)

anche se questa osservazione, pur vero, non è certo indicativo di uno stile di programmazione sano.

Answer 4

Un modo per evitare la ricorsione esplicita è utilizzare fix per esprimere la ricorsione come punto fisso.

import Data.Function (fix) 

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

o in-point gratuito stile

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

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