recursivos - tipos de datos en haskell

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

Question

Para ayudarme a aprender Haskell, estoy trabajando en los problemas del Proyecto Euler. Después de resolver cada problema, comparo mi solución con la wiki de Haskell en un intento de aprender mejores prácticas de codificación. Aquí está la solución al problema 3 :

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 ingenua lectura de esto es que los primes se definen en términos de primeFactors , que se definen en términos de primes . Así que evaluar primeFactors 9 seguiría este proceso:

1. Evaluar los factor 9 primes .
2. Pregunta primes por su primer elemento, que es 2.
3. Preguntar primes por su siguiente elemento.
4. Como parte de este proceso, evalúe primeFactors 3 .
5. Pregunta primes por su primer elemento, que es 2.
6. Preguntar primes por su siguiente elemento.
7. Como parte de este proceso, evalúe primeFactors 3 .
8. ...

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

Answer 1

La respuesta de Kevin es satisfactoria, pero permítame señalar la falla en su lógica. Es el # 6 que está mal. Entonces estamos evaluando primeFactors 3 :

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

El THUNK nunca necesita ser evaluado para determinar que el primeFactor 3 es [3] .

Answer 2

primeFactors 3 no pide primes para su siguiente elemento, solo el primero, porque 2*2 es mayor que 3

Answer 3

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 se "pone al día" con el número que está probando para su inclusión en la lista. Debido a que Haskell es perezoso, esto significa que la prueba de primeFactors termina.

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