[Haskell-cafe] Re: Optimization fun

Matthew Brecknell haskell at brecknell.org
Sun Feb 11 00:04:16 EST 2007

Rafael Almeida said:
> I've always found the following definition of the sieve of eratosthenes
> the clearest definition one could write:
> sieve [] = []
> sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
> It doesn't perform better than Augustsson's solution. It does fairly
> worse, actually, but it performs way better than Hogg's 13s algorithm.
> It took around 0.1s on my machine.

Interesting. I found the sieve to be somewhere around the 13s mark,
while Lennart's solution was about 0.15s. But that may just be because I
haven't yet made the jump from GHC 6.4.2 to 6.6...

I also found that a handcrafted loop-fusion reduced Lennart's solution
to 0.08s:

primes :: [Int]
primes = 2 : filter isPrime [3,5..] where
  f x p r = x < p*p || mod x p /= 0 && r
  isPrime x = foldr (f x) True primes

More information about the Haskell-Cafe mailing list