¿Se puede plegar para crear listas infinitas?

Question

he escrito el código siguiente que crea una lista infinita de los números de Fibonacci:

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

¿Puede el código anterior escribirse usando foldl o foldr para evitar la repetición?

Answer 1

No sé si es posible crear listas infinitas con foldl. Quizás puedas resolver este problema usando foldr, pero luego tendrás que crear otra lista para doblar. ¿Cuál sería esa lista? No hay nada con los números de Fibonacci que sugieran que se generan a partir de alguna otra lista.

Lo que quiere en su lugar es usar unfoldr. Se puede usar para crear listas en lugar de consumirlas, como es el caso de foldl y foldr. Así es como usaría unfoldr para generar la lista infinita de números de Fibonacci.

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

puede encontrar unfoldr en el módulo Data.List en el paquete base.

Answer 2

Puede utilizar zipWith para escribir su definición

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

edición: Ok, yo no creo que se pueda utilizar foldl o foldr para crear lista infinita. No en un sentido simple imaginable. Si nos fijamos en la definición simple de foldl

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

foldl nunca se regresa hasta que se haya agotado la lista entera. Así un ejemplo sencillo como

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

> take 10 g 

no funcionará uniforme y se hará en bucle para siempre.

Answer 3

Los foldl y foldr funciones son lista- consumidores. Como svenningsson's answer señala correctamente, unfoldr es un productor de la lista que es adecuado para capturar co -estructura recursiva de fibs.

Sin embargo, dado que foldl y foldr son polimórficos en sus tipos de devolución, es decir, lo que están produciendo al consumir una lista, es razonable preguntar si podrían usarse para consumir una lista y producir otra. ¿Podría alguna de estas listas producidas ser infinita?

En cuanto a la definición de foldl

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

vemos que para foldl para producir nada en absoluto, la lista que consume debe ser finito. Por lo tanto, si foldl f a produce salida infinita, es porque a es infinito o porque f a veces realiza una generación de lista infinita.

Es una historia diferente con foldr

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

que no admite la posibilidad de que f perezoso podría generar alguna salida para cada b consumida de la entrada. Operaciones como

map g = foldr (\ b gbs -> g b : gbs) [] -- golfers prefer ((:) . g) 
stutter = foldr (\ x xxs -> x : x : xxs) [] 

producen un poco de salida para cada entrada, entregan salida infinita desde la entrada infinita.

Una persona descarada puede expresar cualquier recursión infinita como una foldr no recursiva en una lista infinita. Por ejemplo,

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

(Editar:. O, para el caso

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

que está más cerca a la definición en la pregunta)

aunque esta observación, mientras que cierto, no es indicativo de un estilo de programación saludable.

Answer 4

Una forma de evitar la recursión explícita es usar fix para expresar la recursión como un punto fijo.

import Data.Function (fix) 

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

o en puntos libre de estilo

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

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