Estimados,
Tengo una duda de cómo funciona lazy evaluation con foldr y foldl.
La duda es, por qué con foldr no tengo problema con listas infinitas y con foldl sí? Leí que foldl es tail recursive, o sea que antes de producir algo tiene que "recorrer" toda la lista, pero no me doy cuenta por qué.
Agradezco si me pueden dar una mano entendiendo como funciona foldr y foldl en estos casos.
Tal vez sea bueno verlo con un ejemplo. Hagamos con foldr una función bien tonta, que tome una lista y retorne una lista idéntica:
idr = foldr (:) []
Recordemos que foldr se implementa:
foldr _ e [] = e
foldr h e (x:xs) = h x (foldr h e xs)
Ahora supongamos que queremos hacer (head (idr ones)), la secuencia de evaluación sería:
head (idr ones)
== head (foldr (:) [] ones)
== head (foldr (:) [] (1:ones))
== head (1 : foldr (:) [] ones)
== 1
Intenemos hacer lo mismo con foldl, una función igual a la anterior pero implementada con foldl sería:
idl = foldl snoc [] where snoc xs x = xs ++ [x]
Recordemos foldl:
foldl _ e [] = e
foldl h e (x:xs) = foldl h (h e x) xs
Veamos la secuencia de evaluación de hacer (head (idl ones)):
head (idl ones)
== head (foldl snoc [] ones)
== head (foldl snoc [] (1:ones))
== head (foldl snoc (snoc [] 1) ones)
== head (foldl snoc (snoc [] 1) (1:ones))
== head (foldl snoc (snoc (snoc [] 1) 1) ones)
== head (foldl snoc (snoc (snoc [] 1) 1) (1:ones))
== ...
Como la lista es infinita foldl nunca llega al caso base, que es donde se retornaría algo que head puede consumir.
Marcos,
Muchas gracias por el ejemplo, me quedó clarísimo.
Saludos.