Haskell, entendiendo una solución para euler # 3

Question

Recientemente he aprendido a aprenderme un haskell y lo he estado pasando muy bien. He estado trabajando en algunos problemas de Project Euler para comprender la sintaxis y he estado revisando las soluciones publicadas aquí http://www.haskell.org/haskellwiki/Euler_problems/1_to_10 como una herramienta de aprendizaje. Aunque he encontrado a mí mismo incapaz de hacerme a la solución publicado por problem #3:

-- Find the largest prime factor of 317584931803. 

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) 

no puedo averiguar por la vida de mí cómo funciona. primes y primeFactors parecen llamarse entre sí para construir sus propias listas y tratar de seguirlo me deja en blanco. ¿Alguien sabe una buena publicación en el blog sobre esta solución o quiere escribir una explicación al respecto aquí?

Answer 1

Esto es desconcertante a primera vista. Pero no es mágico si no piensas "imperativamente". Las definiciones de Haskell son solo eso: le dicen que algo es, no qué operaciones de nivel inferior debe ejecutar la computadora.

Por lo tanto, la lista de números primos es la lista que contiene 2 y todos los números naturales impares mayores 2 que tienen un solo factor primo (es decir, sí mismo).

La lista de factores primos para un número entero n, por otro lado, es la lista de los números primos que dividen n.

Asegúrese de comprender esas definiciones antes de seguir leyendo.

Como Haskell abstracto puede ser, todavía es un lenguaje de programación, por lo que tenemos que dar algún consejo de vez en cuando cómo para calcular algo. Específicamente, en el ejemplo de arriba, hacemos no probamos todos los números primos para encontrar factores primos de n, porque es suficiente para probar 2..k donde k*k <= n. Esto también asegura que solo usemos esa parte de primo que ya está calculada.

Al comienzo, primes se parece a esto:

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

Si exigimos el siguiente elemento después de 2, que forzar la evaluación de la correcta expresión de los dos puntos. Esto, a su vez, hace que el filtro para evaluar el predicado de 3. Entonces va:

primeFactors 3 
    factor 3 (2 : ...) 
    2*2 > 3 
    [3] 
[3] 

Por lo tanto, es primeFactors 3[3] y que no era necesario mirar más allá de 2 en números primos. (Este es el punto clave de por qué esto funciona!) Claramente, la longitud de [3] es 1 y

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

evalúa a

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

Ahora puede querer reducir primeFactors 5 por sí mismo.

Answer 2

pereza en acción :) La lista de números primos comienza no vacío,

primes = 2 : don't_know_yet_let's_see 

y primeFactors calcula los factores primos de un número usando la lista de los números primos. Pero para encontrar los factores primos de cualquier número 'n', solo necesitamos saber los números primos hasta sqrt(n). Así que la cola de primes,

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

puede utilizar lo que ya se conoce de primes. Para comprobar 3, que

factor 3 (2:don't_kow_yet_let's_see) 
    | 2*2 > 3 = [3] 
    | don't_care_above_was_true 

Y si empezamos con cualquier n, n = 35 decir que sea breve,

factor 35 (2:??) 
    | 2*2 > 35 -- False, next clause 
    | 35 `mod` 2 == 0 -- False, next clause 
    | otherwise = factor 35 ?? 

Ahora tenemos que averiguar qué es ??. Hemos visto que el ing filter deja 3 pase, así que es 3:???, por lo tanto,

factor 35 (3:???) 
    | -- first two guards are False 
    | otherwise = factor 35 ??? 

Ahora lo que es ???? Bueno, filter ((== 1) . length . primeFactors) [5, 7 .. ], por lo que vamos a ver si pasa el filtro 5

factor 5 (2:3:???) -- note, we already know the first two elements of primes 
    | 2*2 > 5 -- False 
    | 5 `mod` 2 == 0 -- False 
    | otherwise = factor 5 (3:???) 
        | 3*3 > 5 = [5] 

Así 5 pases y sabemos que los tres primeros elementos de primes. En la factorización de 35, continuamos

factor 35 (5:????) 
    | 5*5 > 35 -- False 
    | 35 `mod` 5 == 0 = 5 : factor (35 `div` 5) (5:????) 
          factor 7 (5:????) 
           | 5*5 > 7 = [7] 

lo tanto, cuando la factorización de un número, la lista de los números primos es edificado la medida de lo necesario, se determinará cada nuevo primer cuando se exigió, y en ese momento, toda los primos necesarios para determinar el próximo primo ya se han encontrado.