¿Por qué este fragmento de código de Haskell no es infinitamente recursivo?

Para ayudarme a aprender Haskell, estoy trabajando en los problemas del Proyecto Euler. Después de resolver cada problema, compruebo mi solución contra la wiki de Haskell en un intento de aprender mejores prácticas de codificación. Aquí es the solution-problem 3:¿Por qué este fragmento de código de Haskell no es infinitamente recursivo?

primes = 2 : filter ((==1) . length . primeFactors) [3,5..] 

primeFactors n = factor n primes 
    where 
    factor n (p:ps) 
     | p*p > n  = [n] 
     | n `mod` p == 0 = p : factor (n `div` p) (p:ps) 
     | otherwise  = factor n ps 

problem_3 = last (primeFactors 317584931803)

Mi lectura ingenua de esto es que primes se define en términos de primeFactors, que se define en términos de primes. Así evaluar primeFactors 9 seguiría este proceso:

Evaluar factor 9 primes.
Pregunte primes para su primer elemento, que es 2.
Pregunte primes para su siguiente elemento.
Como parte de este proceso, evalúe primeFactors 3.
Pregunte primes para su primer elemento, que es 2.
Pregunte primes para su siguiente elemento.
Como parte de este proceso, evalúe primeFactors 3.
...

En otras palabras, los pasos 2-4 sería repetir infinitamente. Claramente estoy equivocado, ya que el algoritmo termina. ¿Qué error estoy haciendo aquí?

Fuente

2011-12-12 Matthew Pirocchi

porque, como las respuestas aquí dicen, 'primeFactors' solo accede a' primos' hasta que el cuadrado de un primo excede el número que se está probando, ese código es equivalente a 'primos = 2: [n | n <- [3 ..], todo ((> 0) .rem n) $ takeWhile ((<= n). (^ 2)) primos] 'que claramente no es bucle. –

primeFactors solo lee hasta la raíz cuadrada del número que está evaluando. Nunca se ve más en la lista, lo que significa que nunca "alcanza" el número que está probando para su inclusión en la lista. Como Haskell es flojo, esto significa que la prueba primeFactors finaliza.

La otra cosa para recordar es que primes no es una función que se evalúa en una lista cada vez que accede, sino más bien una lista que se construye de forma perezosa. Entonces, una vez que se ha accedido al 15º elemento una vez, acceder a él por segunda vez es "gratuito" (por ejemplo, no requiere ningún cálculo adicional).

Fuente

2011-12-12 03:17:30

detalle: Acceder a él por segunda vez todavía cuesta 15 desreferenciaciones ya que estamos haciendo listas de conteo ... esto puede ser mucho si tiene cientos de elementos de lista – naiad

@sparkleshy que serían cuadráticos en (aproximadamente) 'sqrt (n) ', es decir, agregue (aproximadamente) el costo lineal a un cálculo * sobre-lineal *. –

primeFactors 3 no se pregunta por su primes siguiente elemento, sólo el primero, porque 2*2 es mayor que 3 ya

Fuente

2011-12-12 05:59:01 asvyazin

respuesta de Kevin es satisfactoria, pero me permite localizar la falla en su lógica. Es el # 6 que está mal. Así que estamos evaluando primeFactors 3:

primeFactors 3   ==> 
factor 3 primes   ==> 
factor 3 (2 : THUNK) ==> 
2*2 > 3 == True   ==> 
[3]

El THUNK no tiene por qué ser evaluado para determinar que el primeFactor 3 es [3].

Fuente

2011-12-12 22:17:28

¿Por qué este fragmento de código de Haskell no es infinitamente recursivo?

Respuesta

Cuestiones relacionadas