Come si implementa un elenco di numeri primi in Haskell in modo che possano essere recuperati pigramente?Elenco pigro di numeri primi
Sono nuovo di Haskell e vorrei conoscere gli usi pratici della funzionalità di valutazione lazy.
Ecco una breve funzione di Haskell che enumera i numeri primi da Literate Programs:
primes :: [Integer]
primes = sieve (2 : [3, 5..])
where
sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]
A quanto pare, questo non è il crivello di Eratostene (grazie, Landei). Penso che sia ancora un esempio istruttivo che dimostra che è possibile scrivere un codice breve molto elegante in Haskell e che mostra come la scelta della struttura dei dati sbagliata possa danneggiare gravemente l'efficienza.
Leggere e ripensare alla risposta: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf – Landei
La "struttura dati errata" (ad es. Lista) non ha nulla a che fare con * l'inefficacia * estrema * del codice (O (n^2), * nei primordi 'n' prodotta *), che è invece il risultato dell'accensione prematura dei filtri su ogni primo primo trovato invece che sul suo * quadrato *. Con la creazione dei filtri [correttamente posticipata] (http://www.haskell.org/haskellwiki/Prime_numbers#Postponed_Filters), viene invece eseguito a circa O (n^1.4..1.45) (nei primissimi 'n' prodotti), proprio come qualsiasi altra normale divisione di prova. –
Il collegamento a [programmi di scrittura] (http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29) è interrotto. – ThreeFx
Ci sono un certo numero di soluzioni per la generazione pigra di sequenze primarie proprio nel wiki di haskell. La prima e più semplice è l'Postponed Turner sieve: (vecchia versione ... 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
io suggerirei di prendere una delle implementazioni da questa carta: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
Molto interessante, ho riflettuto per un po 'sulla semplicità dell'unica fodera e l'ho trovato davvero in contrasto con la mia esperienza di implementazione di un setaccio ... hanno imbrogliato! Sono abbastanza frustrato di non averlo notato anche: p –
La risposta accettata da @nikie non è molto efficiente, è relativamente lento dopo alcune migliaia, ma la risposta di @sleepynate è molto meglio. Mi c'è voluto del tempo per capirlo, quindi qui è lo stesso codice, ma solo con le variabili chiamate in modo più chiaro:
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]
L'idea principale è che i candidati per i prossimi numeri primi già non contengono numeri che sono divisibili per qualsiasi numero primo inferiore al primo primo assegnato alla funzione. In modo che se si chiama
calcNextPrimes (5:ps) [11,13,17..]
lista dei candidati contiene nessun numero, che è divisibile per 2 o 3, ciò significa che il primo candidato non-principale sarà 5 * 5, causare 5* 2 e 5 * 3 e 5 * 4 sono già eliminati. Ciò consente di prendere tutti i candidati, che sono più piccoli del quadrato di 5 e aggiungerli subito ai numeri primi e setacciare il resto per eliminare tutti i numeri divisibili per 5.
Qualcosa come http://stackoverflow.com/questions/1764163/help-spiega-il-pezzo-di-Haskell-codice-che-uscite-a-stream-of-numeri primi? – kennytm
Considerate http://hackage.haskell.org/package/primes –
Al contrario: è un compito complicato creare un elenco di numeri primi non pigri in Haskell – vpolozov