list - zipwith - takewhile haskell

Plegado a la izquierda y a la derecha sobre una lista infinita

Question

Tengo problemas con el siguiente pasaje de Learn You A Haskell (Gran libro, no lo digas):

¡Una gran diferencia es que los pliegues derechos funcionan en listas infinitas, mientras que los de la izquierda no funcionan! Para decirlo claramente, si tomas una lista infinita en algún punto y la pliegas desde la derecha, eventualmente llegarás al comienzo de la lista. Sin embargo, si tomas una lista infinita en un punto e intentas plegarla desde la izquierda, ¡nunca llegarás a un final!

Simplemente no entiendo esto. Si tomas una lista infinita y tratas de doblarla desde la derecha, entonces tendrás que comenzar en el punto infinito, lo cual no está sucediendo (si alguien sabe de un idioma donde puedes hacer esto, dile: p ) Al menos, tendrías que comenzar allí de acuerdo con la implementación de Haskell porque en Haskell foldr y foldl no se toma un argumento que determine en qué parte de la lista deberían comenzar a doblar.

Estoy de acuerdo con la cita Iff foldr y foldl tomaban argumentos que determinaban en qué parte de la lista deberían comenzar a doblar, porque tiene sentido que si tomas una lista infinita y comienzas a doblar desde un índice definido terminará eventualmente, mientras que no lo hace No importa dónde comiences con un doblez izquierdo; estarás doblando hacia el infinito. Sin embargo, foldr y foldl no toman este argumento, y por lo tanto la cita no tiene sentido. En Haskell, tanto un doblez a la izquierda como un doblez a la derecha sobre una lista infinita no terminarán .

¿Es correcto mi entendimiento o me estoy perdiendo algo?

Answer 1

Hay una buena explicación en la wiki de Haskell . Muestra la reducción paso a paso con diferentes tipos de funciones de pliegue y acumulador.

Answer 2

La clave aquí es la pereza. Si la función que está utilizando para doblar la lista es estricta, entonces ni un doblez a la izquierda ni un doblez a la derecha terminarán, dada una lista infinita.

Prelude> foldr (+) 0 [1..]
^CInterrupted.

Sin embargo, si intenta doblar una función menos estricta, puede obtener un resultado final.

Prelude> foldr (/x y -> x) 0 [1..]
1

Incluso puede obtener un resultado que es una estructura de datos infinita, por lo que si bien en cierto sentido no termina, aún puede producir un resultado que se puede consumir perezosamente.

Prelude> take 10 $ foldr (:) [] [1..]
[1,2,3,4,5,6,7,8,9,10]

Sin embargo, esto no funcionará con foldl , ya que nunca podrá evaluar la llamada a la función más externa, floja o no.

Prelude> foldl (flip (:)) [] [1..]
^CInterrupted.
Prelude> foldl (/x y -> y) 0 [1..]
^CInterrupted.

Tenga en cuenta que la diferencia clave entre un plegado a la izquierda y a la derecha no es el orden en que se recorre la lista, que es siempre de izquierda a derecha, sino más bien cómo se anidan las aplicaciones de funciones resultantes.

• Con foldr , están anidados en "el interior"

  foldr f y (x:xs) = f x (foldr f y xs)

  Aquí, la primera iteración dará como resultado la aplicación más externa de f . Por lo tanto, f tiene la oportunidad de ser flojo para que el segundo argumento no siempre se evalúe, o puede producir una parte de una estructura de datos sin forzar su segundo argumento.

• Con foldl , están anidados en "el exterior"

  foldl f y (x:xs) = foldl f (f y x) xs

  Aquí, no podemos evaluar nada hasta que hayamos alcanzado la aplicación más externa de f , que nunca alcanzaremos en el caso de una lista infinita, independientemente de si f es estricta o no.

Answer 3

La frase clave es "en algún momento".

si tomas una lista infinita en algún punto y la pliegas desde la derecha, eventualmente llegarás al comienzo de la lista.

Así que tienes razón, no puedes comenzar en el "último" elemento de una lista infinita. Pero el punto del autor es este: supongamos que pudieras. Simplemente escoja un punto muy lejos (para los ingenieros, esto es "lo suficientemente cerca" hasta el infinito) y comience a doblar hacia la izquierda. Eventualmente terminas al principio de la lista. Lo mismo no es cierto para el doblez izquierdo, si eliges un punto waaaay (y lo llamas "lo suficientemente cerca" para el comienzo de la lista), y comienzas a doblar hacia la derecha, todavía tienes un infinito camino por recorrer.

Entonces, el truco es que a veces no necesitas ir al infinito. Es posible que no necesites ni siquiera ir por ahí. Pero es posible que no sepa qué tan lejos debe ir antes, en cuyo caso las listas infinitas son bastante útiles.

La ilustración simple es foldr (:) [] [1..] . Vamos a realizar el doblez.

Recuerde que foldr fz (x:xs) = fx (foldr fz xs) . En una lista infinita, en realidad no importa qué es z así que solo lo guardo como z lugar de [] que desordena la ilustración

foldr (:) z (1:[2..])         ==> (:) 1 (foldr (:) z [2..])
1 : foldr (:) z (2:[3..])     ==> 1 : (:) 2 (foldr (:) z [3..])
1 : 2 : foldr (:) z (3:[4..]) ==> 1 : 2 : (:) 3 (foldr (:) z [4..])
1 : 2 : 3 : ( lazily evaluated thunk - foldr (:) z [4..] )

Vea cómo foldr , a pesar de teóricamente ser un doblez desde la derecha , en este caso realmente saca los elementos individuales de la lista resultante empezando por la izquierda . Entonces, si take 3 de esta lista, puedes ver claramente que será capaz de producir [1,2,3] y no es necesario evaluar el pliegue más lejos.

Answer 4

Recuerde que en Haskell puede usar listas infinitas debido a la evaluación perezosa. Entonces, head [1..] es solo 1, y head $ map (+1) [1..] es 2, aunque `[1 ..] es infinitamente largo. Si no entiendes eso, detente y juega con eso por un tiempo. Si lo consigue, siga leyendo ...

Creo que parte de tu confusión es que foldl y foldr siempre comienzan de un lado o del otro, por lo tanto, no necesitas dar un largo.

foldr tiene una definición muy simple

 foldr _ z [] = z
 foldr f z (x:xs) = f x $ foldr f z xs

¿Por qué podría esto terminar en listas infinitas?

 dumbFunc :: a -> b -> String
 dumbFunc _ _ = "always returns the same string"
 testFold = foldr dumbFunc 0 [1..]

aquí pasamos a foldr a "" (dado que el valor no importa) y la lista infinita de números naturales. ¿Esto termina? Sí.

La razón por la que termina es porque la evaluación de Haskell es equivalente a la reescritura de términos perezosos.

Asi que

 testFold = foldr dumbFunc "" [1..]

se convierte (para permitir la coincidencia de patrones)

 testFold = foldr dumbFunc "" (1:[2..])

que es lo mismo que (de nuestra definición de fold)

 testFold = dumbFunc 1 $ foldr dumbFunc "" [2..]

ahora por la definición de dumbFunc podemos concluir

 testFold = "always returns the same string"

Esto es más interesante cuando tenemos funciones que hacen algo, pero a veces son flojas. Por ejemplo

foldr (||) False 

se usa para encontrar si una lista contiene elementos True . Podemos usar esto para definir la función de orden superior any que devuelva True si y solo si la función transmitida es verdadera para algún elemento de la lista

any :: (a -> Bool) -> [a] -> Bool
any f = (foldr (||) False) . (map f)

Lo bueno de la evaluación perezosa es que esto se detendrá cuando encuentre el primer elemento e tal que fe == True

Por otro lado, esto no es verdad de foldl . ¿Por qué? Bueno, una foldl realmente simple parece

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

Ahora, ¿qué hubiera pasado si probamos nuestro ejemplo anterior?

testFold'' = foldl dumbFunc "" [1..]
testFold'' = foldl dumbFunc "" (1:[2..])

esto ahora se convierte en:

testFold'' = foldl dumbFunc (dumbFunc "" 1) [2..]

asi que

testFold'' = foldl dumbFunc (dumbFunc (dumbFunc "" 1) 2) [3..]
testFold'' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) [4..]
testFold'' = foldl dumbFunc (dumbFunc (dumbFunc (dumbFunc (dumbFunc "" 1) 2) 3) 4) [5..]

Y así sucesivamente y así sucesivamente. Nunca podemos llegar a ningún lado, porque Haskell siempre evalúa primero la función más externa (es decir, la evaluación perezosa en pocas palabras).

Una buena consecuencia de esto es que puedes implementar foldl desde foldr pero no viceversa. Esto significa que de alguna manera profunda foldr es la más fundamental de todas las funciones de cadena de orden superior, ya que es la que usamos para implementar casi todas las demás. Puede que desee utilizar un foldl veces, porque puede implementar foldl tail recursivamente, y obtener algo de rendimiento de eso.

Answer 5

Su comprensión es correcta. Me pregunto si el autor está tratando de hablar sobre el sistema de evaluación perezosa de Haskell (en el que puede pasar una lista infinita a varias funciones, sin incluir el doblez, y solo evaluará todo lo que se necesite para devolver la respuesta). pero estoy de acuerdo con usted en que el autor no está haciendo un buen trabajo al describir algo en ese párrafo, y lo que dice es incorrecto.