haskell - programacion - ¿Evaluación perezosa para funciones generadoras de listas?

programacion funcional pdf

Question

Actualmente estoy leyendo Programación en Haskell, por Graham Hutton.

En la página 40, se presenta una prueba de primalidad de juguete:

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

prime :: Int -> Bool
prime n = factors n == [1,n]

El autor continúa explicando cómo

"Decidir que un número no es primo no requiere que la función cebe produzca todos sus factores, porque en una evaluación perezosa, el resultado False se devuelve tan pronto como se produce un factor distinto de uno o el número".

Como alguien que viene de C y Java, me parece impactante. Habría esperado que los factors llamada se completaran primero, guardaran el resultado en la pila y pasaran el control a la función de llamada. Pero al parecer, aquí se está ejecutando un programa muy diferente: debe haber un bucle sobre la comprensión de la lista en factors y la verificación de igualdad en prime se está verificando para cada nuevo elemento agregado a la lista de factores.

¿Cómo es esto posible? ¿No hace esto más difícil de razonar sobre el orden de ejecución de un programa?

Answer 1

¿No hace esto más difícil de razonar sobre el orden de ejecución de un programa?

Probablemente, al menos, para aquellos que vienen de un paradigma de procedimiento / OO. He hecho mucho con los iteradores y la programación funcional en otros lenguajes de evaluación entusiasta, y para mí la estrategia de evaluación perezosa no es el principal problema de aprendizaje de Haskell. (¿Cuántas veces ha deseado que su declaración de registro de Java ni siquiera obtuviera los datos para el mensaje hasta después de haber decidido realmente iniciar sesión?)

Piense en todo el procesamiento de listas en Haskell como si estuviera compilado en una implementación basada en iteradores bajo las carátulas. Si estuviera haciendo esto en Java con los posibles factores de n dados como un Iterator<Integer> , ¿no querría detenerse tan pronto como encuentre uno que no era 1 o n ? Y si es así, ¡realmente no importa si el iterador es infinito o no!

Cuando llegas a eso, el orden de ejecución no importa mucho. Lo que realmente te importa es:

• Corrección del resultado.
• Terminación oportuna
• El orden relativo de cualquier efecto secundario.

Ahora bien, si tiene un programa "puramente funcional", no hay efectos secundarios. Pero, ¿cuándo sucede eso? Prácticamente cualquier cosa útil más allá del procesamiento de números / cadenas y metacódigo (es decir, funciones de orden superior) tendrá efectos secundarios.

Afortunadamente (o desafortunadamente, dependiendo de a quién pregunte), tenemos la monad como un patrón de diseño en Haskell que sirve para (entre otras cosas) controlar el orden de evaluación y, por lo tanto, los efectos secundarios.

Pero incluso sin aprender sobre las mónadas y todo eso, en realidad es tan fácil de razonar sobre el orden de ejecución como en los lenguajes de procedimiento. Solo tienes que acostumbrarte a ello.

Answer 2

Lo encuentras "chocante" porque no lo esperas. Una vez que te acostumbras ... Bueno, en realidad todavía hace tropezar a la gente. Pero después de un tiempo, eventualmente envuelves tu mente alrededor de eso.

Cómo funciona Haskell es esto: cuando llamas a una función, ¡ no pasa nada! La llamada se anota en alguna parte, y eso es todo. Esto lleva aproximadamente ningún tiempo en absoluto. Su "resultado" es en realidad solo un "Te debo" que le dice a la computadora qué código ejecutar para obtener el resultado. No todo el resultado, fíjate; Solo el primer paso de ello. Para algo como un entero, solo hay un paso. Pero para una lista, cada elemento es un paso separado.

Déjame mostrarte un ejemplo más simple:

print (take 10 ([1..] ++ [0]))

Hablé con un programador de C ++ que estaba "sorprendido" de que esto funcionara. ¿Seguramente la parte " ++[0] " tiene que "encontrar el final de la lista" antes de que pueda agregarle cero? ¿Cómo se puede completar este código en tiempo finito?

Parece que esto genera [1..] (en la lista infinita), y luego ++[0] escanea hasta el final de esta lista e inserta un cero, y luego take 10 recortes solo los primeros 10 elementos, y luego huellas dactilares. Eso, por supuesto, tomaría tiempo infinito.

Así que aquí está lo que realmente sucede. La función más externa es take , así que ahí es donde empezamos. (No esperábamos eso, ¿eh?) La definición de take es algo como esto:

take 0 (   _) = []
take n (  []) = []
take n (x:xs) = x : (take (n-1) xs)

Así que claramente 10! = 0, así que la primera línea no se aplica. Por lo tanto, se aplica la segunda o la tercera línea. Así que ahora take vistazo a [1..] ++ [0] para ver si es una lista vacía, o una lista no vacía.

La función más externa aquí es (++) . Su definición es similar a

(  []) ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Así que tenemos que averiguar qué ecuación se aplica. O bien el argumento de la izquierda es una lista vacía (se aplica la línea uno), o no lo es (se aplica la línea dos). Bueno, dado que [1..] es una lista infinita, la línea dos siempre se aplica. Entonces el "resultado" de [1..] ++ [0] es 1 : ([2..] ++ [0]) . Como puedes ver, esto no está completamente ejecutado; pero se ejecuta lo suficiente como para decir que esta es una lista no vacía. Que es todo lo que le importa.

take 10 ([1..] ++ [0])
take 10 (1 : ([2..] ++ [0]))
1 : take 9 ([2..] ++ [0])
1 : take 9 (2 : ([3..] ++ [0]))
1 : 2 : take 8 ([3..] ++ [0])
1 : 2 : take 8 (3 : ([4..] ++ [0]))
1 : 2 : 3 : take 7 ([4..] ++ [0])
...
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : take 0 ([11..] ++ [0])
1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : []

¿Ves cómo se desenrolla esto?

Ahora, volviendo a su pregunta específica: el operador (==) toma un par de listas y las repite en ambas, comparándolas elemento por elemento para asegurarse de que son iguales. Tan pronto como se encuentra una diferencia , inmediatamente aborta y devuelve falso:

(  []) == (  []) = True
(x:xs) == (y:ys) = (x == y) && (xs == ys)
(   _) == (   _) = False

Si ahora intentamos, digamos, prime 6 :

prime 6
factors 6 == [1,6]
??? == [1,6]
1 : ??? == [1,6]
??? == [6]
2 : ??? == [6]
False

Answer 3

Me centraré en este punto:

¿No hace esto más difícil de razonar sobre el orden de ejecución de un programa?

Sí, pero el orden de evaluación no importa tanto en la programación funcional pura. Por ejemplo:

(1 * 3) + (4 * 5)

P: ¿Qué multiplicación se realiza primero? A: no nos importa, el resultado es el mismo. Incluso los compiladores de C pueden elegir cualquier orden aquí.

(f 1) + (f 2)

P: ¿Qué función de llamada se realiza primero? A: no nos importa, el resultado es el mismo. Aquí, los compiladores de C pueden elegir cualquier orden también. Sin embargo, en C, la función f puede tener efectos secundarios, por lo que el resultado de la suma anterior depende del orden de evaluación. En la programación funcional pura, no hay efectos secundarios, por lo que realmente no nos importa.

Además, la pereza permite la expansión de cualquier función para preservar la semántica. Supongamos que definimos

f x = e -- e is an expression which can use x

y llamamos f 2 . El resultado debe ser el mismo que e{2/x} , es decir, como e donde cada aparición (gratuita) de x ha sido reemplazada por 2 . Esto es solo "desplegar la definición", como en matemáticas. Por ejemplo,

f x = x + 4

-- f 2 ==> 2 + 4 ==> 6

Sin embargo, supongamos que llamamos f (g 2) lugar. La pereza hace esto equivalente a e{g 2/x} . De nuevo, como en matemáticas. Por ejemplo:

f x = 42
g n = g (n + 1)  -- infinite recursion

entonces todavía tenemos f (g 2) = 42 {g 2/x} = 42 ya que x no se usa. No tenemos que preocuparnos si g 2 está definido o no (bucle para siempre). La definición desplegada siempre funciona.

Esto hace que sea más fácil razonar sobre el comportamiento del programa.

Sin embargo, hay algunas desventajas de la pereza. La principal es que, si bien la semántica del programa es (posiblemente) más simple, estimar el rendimiento del programa es más difícil. Para evaluar el rendimiento, debe comprender más de lo que será el resultado final: debe tener un modelo de todos los pasos intermedios que conducen a ese resultado. Especialmente en código de alto nivel, o cuando se inicia una optimización inteligente, esto requiere cierta experiencia sobre cómo funciona realmente el tiempo de ejecución.