Filtrare un elenco infinito in Haskell

Question

Ho il seguente codice che implementa il crivello di Eratostene:

primes :: [Int] 
primes = primes' [2..] 

primes' :: [Int] -> [Int] 
primes' [] = [] 
primes' (p:ps) = p:(primes' [p' | p' <- ps, not (p' `isMultiple` p)]) 

a `isMultiple` b = (a `mod` b) == 0 

main = print (sum (primes' [2..100000])) 

vorrei cambiare principale a qualcosa come

main = print (sum [p | p <- primes, p < 100000])) 

Non a caso, questo si blocca a causa deve confrontare p con ogni elemento dei numeri primi infiniti. Poiché so che i numeri primi sono in ordine crescente, come faccio a troncare la lista infinita non appena trovo un elemento che supera il mio limite superiore?

p.s. In teoria, i primes filtrano la lista di input per restituire una lista di numeri primi. So che ci saranno dei problemi se avrò aperto la lista a qualcosa di diverso da 2. Sto ancora lavorando su come affrontare questo problema da solo, quindi per favore non spoiler. Grazie ;-)

Answer 1

In casi come questo in cui si sa che una volta che il predicato restituisce false per un elemento, non verrà mai restituito per un elemento successivo, è possibile sostituire filter con takeWhile, che interrompe il prelievo di elementi non appena come il predicato restituisce false per la prima volta.