Sto cercando di imitare il Sieve per trovare tutti i numeri primi meno di un numero usando Haskell. Ho trovato altri programmi Haskell che usano il metodo Sieve con grande velocità. Tuttavia la seguente funzione ricorsiva che ho scritto è molto lenta. Il codice è il seguentePerché questa funzione ricorsiva in Haskell è così lenta?
sieve' :: Integer -> Integer -> [Integer]
sieve' n 1 = [2 .. n]
sieve' n (k + 1) | [x | x <- sieve' n k, x == k + 1] == [] = sieve' n k
|otherwise = [x | x <- sieve' n k, x == k + 1 || not (mod x (k + 1) == 0)]
sieve :: Integer -> [Integer]
sieve n = sieve' n n
Setaccio 20 impiega circa 2 minuti. Sieve 30 non ha ancora finito mentre sto scrivendo questa domanda.
Qualcuno può spiegare perché questa funzione ricorsiva sia così lenta. Grazie per tutto l'aiuto che potete fornire.
Come massima autorità sul setaccio di Eratostene in Haskell dovresti dare un'occhiata all'articolo di Melissa O'Neill (http://lambda-the-ultimate.org/node/3127) nel Journal of Functional Programming (2009). Ci dovrebbero essere alcuni altri trucchi in esso. – ShiDoiSi