Vimal wrote:
Why not just:
primes = sieve [2..]
sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
main = print (take 1000 primes)
I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 10000, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove!
Say for eg: I give
take 100 primes
2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Now. It has to remove 6, based on the fact that it was a multiple of 2 ... (or 3? Which one comes first?)
This happens in a different order than what would be expected generally in a sieve :-)
To get a grip on the order in which things are sieved, try the following little experiment (should also work for other sieves): The original sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0] is equivalent (by desugaring the list comprehension) to sieve (p : xs) = p : sieve (filter (\x -> x `mod` p > 0) xs) To see the non-primes as well, replace the filter with a map, where the result type is an Either, with Left for primes and Right for non-primes. To keep track of which modules have been tested for each given number, let the element type of the Either-alternatives be a pair consisting of the number and the list of checked modules. This gives: sieve (Left l@(p,_) : xs) = Left l : sieve (map (either (\(x,e) -> (if x `mod` p > 0 then Left else Right) (x,p:e)) Right) xs) sieve (r : xs) = r : sieve xs Now try:
sieve [Left (i,[]) | i <-[2..]] [Left (2,[]),Left (3,[2]),Right (4,[2]),Left (5,[3,2]),Right (6,[2]),Left (7,[5,3,2]),Right (8,[2]),Right (9,[3,2]),Right (10,[2]),Left (11,[7,5,3,2]),...
The Left-entries are primes, the Right-entries are non-primes, and the second element of each pair shows against which modules the first pair element has been checked (in reverse order). Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:voigt@tcs.inf.tu-dresden.de