Learning Haskell: Programa aparentemente circular - Por favor ayuda a explicar

Question

Actualmente estoy revisando el libro "The Haskell Road to Logic, Math and Programming" de Doets y Van Eijck. Nunca he estado expuesto a ningún lenguaje de programación funcional hasta este libro, así que tenlo en cuenta.

Todavía al principio del libro, se da el siguiente código para una prueba de primalidad:

ldp :: Integer -> Integer 
ldp n = ldpf primes1 n 

ldpf :: [Integer] -> Integer -> Integer 
ldpf (p:ps) n | rem n p == 0 = p 
       | p^2 > n  = n 
       | otherwise = ldpf ps n 

primes1 :: [Integer] 
primes1 = 2 : filter prime [3..] 

prime :: Integer -> Bool 
prime n | n < 1  = error "not a positive integer" 
     | n == 1 = False 
     | otherwise = ldp n == n 

Hay una programación aparentemente circular pasando en esa PLD llama primes1, que llama preferencial, que llama PLD de nuevo. Si bien el libro ofrece esto como una explicación de por qué el programa se ejecuta y finaliza:

ldp realiza una llamada a primes1, la lista de números primos. Esta es una primera ilustración de una 'lista diferida'. La lista se llama 'floja' porque calculamos solo la parte de la lista que necesitamos para un procesamiento posterior. Para definir primes1 necesitamos una prueba de primalidad, pero esa prueba se define a sí misma en términos de la función LD, que a su vez se refiere a primes1. Parece que estamos corriendo en círculo. Este círculo puede ser no cruel evitando la prueba de primalidad para 2. Si se da que 2 es primo, entonces podemos usar la primalidad de 2 en la verificación LD de que 3 es primo, y así sucesivamente, y estamos arriba y funcionando

Aunque creo que entiendo esta explicación, le agradecería mucho si alguien puede explicar en términos de los laicos:

1. lo que una "lista perezoso" es y cómo se aplica en este ¿contexto?
2. ¿Cómo saber que 2 es primo permite que el programa no sea feroz?

Cualquier respuesta es muy apreciada.

Answer 1

En orden:

La pereza es la propiedad de expresiones sólo se evalúan como sea necesario, en lugar de cuando fue posible. Una lista perezosa es una que podría ser infinita. Obviamente, intentar evaluar una lista infinita sería una mala idea si la evaluación no fuera vaga.

No estoy seguro de lo que significa "no cruel", pero creo que encontrará que tener el valor "2" como primo conocido proporciona caso base para la recursión, es decir, proporciona un particular entrada sobre la cual finalizará el programa. Escribir una función recursiva (o, de hecho, un conjunto de funciones mutuamente recursivas) generalmente implica reducir el valor de entrada hacia este caso base en pasos sucesivos de la aplicación.

Como referencia, los fragmentos del programa de esta forma generalmente se llaman mutuamente recursivos. El término "referencia circular" no es uno que realmente aplicaría en este caso.

Answer 2

Una característica definitoria de Haskell es su pereza. Las listas son solo parte de esa historia. Básicamente, Haskell nunca realiza ningún cálculo hasta que:

1. el valor del cálculo es necesaria para calcular otra cosa que es necesaria a ...
2. le dijo a Haskell que calcule algo antes de lo que podría hacerlo.

Por lo tanto la función primes1 produce una lista de Integer valores, pero que no produce más de lo que es necesario cumplir con el cálculo global. Aún así, si lo definió de esta manera:

primes1 :: [Integer] 
primes1 = filter prime [2..] 

usted tendría un problema. primes1 intentaría generar el primer valor en su secuencia evaluando (indirectamente) prime 2, que evaluaría ldp 2, lo que solicitaría el primer valor producido por primes1 ... presto bucle infinito!

Al devolver 2 directamente como el primer valor de la secuencia generada por primes1, se evita el ciclo infinito. Para cada valor subsiguiente generado en la secuencia, primes1 ya ha generado un valor anterior que será evaluado por ldp como parte del cálculo del valor posterior.

Answer 3

Lo primero a tener en cuenta es que, por sí solo, ese código no hace nada. Es solo un montón de expresiones matemáticas y no importa qué tan circular sea hasta que intentemos extraer algunos valores de ellas. ¿Como hacemos eso?

que podíamos hacer:

print $ take 1 primes1 

No hay problema aquí. Podemos tomar el primer valor de primes1 sin mirar a cualquier parte del código recursivo, que está ahí explícitamente como 2. ¿Qué pasa:

print $ take 3 primes1 

Vamos a intentar expandir primes1 para obtener algunos valores cabo. Para mantener estas expresiones manejables, ahora ignoro las partes print y take, pero recuerda que solo estamos haciendo este trabajo debido a ellas. primes1 es:

primes1 = 2 : filter prime [3..] 

Tenemos nuestro primer valor, y el primer paso en nuestro segundo es la ampliación de filtro. Si este fuera un lenguaje estricto, intentaríamos ampliar [3 ..] primero y obtener atascado. Una posible definición de filtro es:

filter f (x:xs) = if f x then x : filter f xs else filter f xs 

lo que da:

primes1 = 2 : if prime 3 then 3 : filter prime [4..] else filter prime [4..] 

Nuestro siguiente paso tiene que ser averiguar si prime 3 es verdadera o falsa, así que vamos a expandirlo usando nuestras definiciones de prime, ldp y ldpf.

primes1 = 2 : if ldp 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 
primes1 = 2 : if ldpf primes1 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 

Ahora, las cosas se ponen interesantes, primes1 referencia a sí mismo y necesita ldpf el primer valor hacer su cálculo. Afortunadamente, podemos obtener el primer valor fácilmente.

primes1 = 2 : if ldpf (2 : tail primes) 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 

Ahora, que se aplican las cláusulas de guardia en ldpf y encontrar 2^2 > 3, por lo tanto, ldpf (2 : tail primes) 3 = 3.

primes1 = 2 : if 3 == 3 then 3 : filter prime [4..] else filter prime [4..] 
primes1 = 2 : 3 : filter prime [4..] 

Ahora tenemos nuestro segundo valor. Tenga en cuenta que el lado derecho de nuestra evaluación nunca creció especialmente grande y que nunca tuvimos que seguir el ciclo recursivo muy lejos.

primes1 = 2 : 3 : if prime 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : if ldp 4 == 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : if ldpf primes1 4 == 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : if ldpf (2 : tail primes1) 4 == 4 then 4 : filter prime [5..] else filter prime [5..] 

Utilizamos la cláusula de guardia rem 4 2 == 0, por lo tanto, obtenemos 2 aquí.

primes1 = 2 : 3 : if 2 == 4 then 4 : filter prime [5..] else filter prime [5..] 
primes1 = 2 : 3 : filter prime [5..] 
primes1 = 2 : 3 : if prime 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldp 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldpf primes1 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldpf (2 : tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 

No hay coincidencias de guardia, por lo que son recursivos:

primes1 = 2 : 3 : if ldpf (tail primes) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : if ldpf (3 : tail (tail primes)) 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 

Ahora 3^2 > 5 manera que la expresión es 5.

primes1 = 2 : 3 : if 5 == 5 then 5 : filter prime [6..] else filter prime [6..] 
primes1 = 2 : 3 : 5 : filter prime [6..] 

única Necesitamos tres valores, por lo que la evaluación puede parar.

Por lo tanto, ahora para responder a sus preguntas. Una lista diferida es aquella que solo requiere que evaluemos lo que necesitamos, y la 2 ayuda porque garantiza que cuando lleguemos al paso recursivo siempre tengamos suficientes valores ya calculados. (Imagine expandir esa expresión si no conociéramos el 2, terminaríamos atrapados en un bucle muy bonito rápidamente.)