¿Cómo se implementaría una lista de números primos en Haskell para que se pudieran recuperar de forma perezosa?Lista diferida de números primos
Soy nuevo en Haskell y me gustaría aprender sobre los usos prácticos de la funcionalidad de evaluación diferida.
Aquí es una función corta Haskell que enumera los números primos de Literate Programs:
primes :: [Integer]
primes = sieve (2 : [3, 5..])
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
Al parecer, esto es, no la criba de Eratóstenes (gracias, Landei). Creo que sigue siendo un ejemplo instructivo que muestra que se puede escribir un código corto muy elegante en Haskell y eso muestra cómo la elección de una estructura de datos incorrecta puede perjudicar gravemente la eficiencia.
Lea esto y vuelva a pensar su respuesta: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf – Landei
La "estructura de datos incorrecta" (es decir, la lista) no tiene nada que ver con eso la ineficiencia * extrema * del código (O (n^2), * en primos 'n' producidos *), que en cambio es el resultado de la activación prematura de los filtros en cada primo recién encontrado en lugar de en su * cuadrado *. Con la creación de filtros [correctamente pospuesta] (http://www.haskell.org/haskellwiki/Prime_numbers#Postponed_Filters), en su lugar se ejecuta en aproximadamente O (n^1.4..1.45) (en 'n' primos producidos), al igual que cualquier otra división de prueba normal. –
El enlace a [programas de alfabetización] (http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29) está roto. – ThreeFx
Hay una serie de soluciones para la generación perezosa de secuencias principales directamente en la wiki de haskell. La primera y más sencilla es la Postponed Turner sieve: (revisión antigua ... NB)
primes :: [Integer]
primes = 2: 3: sieve (tail primes) [5,7..]
where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, x `rem` p /= 0]
-- or: filter ((/=0).(`rem`p)) t
where (h,~(_:t)) = span (< p*p) xs
me gustaría sugerir que tomar una de las implementaciones de este documento: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Muy interesante, he reflexionado durante un tiempo sobre la simplicidad de un trazador de líneas y encontré que realmente contrastaba con mi propia experiencia de implementar un colador ... ¡hicieron trampa! Estoy bastante frustrado de no haberlo notado también: p –
la respuesta aceptada de @nikie no es muy eficiente, se vuelve relativamente lento después de algunos miles, pero la respuesta de @sleepynate es mucho mejor. Me tomó un tiempo para entenderlo, por lo tanto, aquí es el mismo código, pero sólo con las variables con nombre más claramente:
lazyPrimes :: [Integer]
lazyPrimes = 2: 3: calcNextPrimes (tail lazyPrimes) [5, 7 .. ]
where
calcNextPrimes (p:ps) candidates =
let (smallerSquareP, (_:biggerSquareP)) = span (< p * p) candidates in
smallerSquareP ++ calcNextPrimes ps [c | c <- biggerSquareP, rem c p /= 0]
La idea principal es que los candidatos para los próximos números primos ya no contienen números que son divisibles por cualquier primo menor que el primer primo dado a la función. Así que si usted llama
calcNextPrimes (5:ps) [11,13,17..]
la lista de candidatos contiene ningún número, que es divisible por 2 o 3, eso significa que el primer candidato no prime será 5 * 5, causar 5* 2 y 5 * 3 y 5 * 4 ya están eliminados. Eso le permite tomar todos los candidatos, que son más pequeños que el cuadrado de 5 y agregarlos directamente a los números primos y tamizar el resto para eliminar todos los números divisibles por 5.
Algo así como http://stackoverflow.com/questions/1764163/help-explain-this-chunk-of-haskell-code-that-outputs-a-stream-of-primes? – kennytm
Considere http://hackage.haskell.org/package/primes –
Todo lo contrario: es una tarea difícil crear una lista de números primos no perezosos en Haskell – vpolozov