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:[EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
