[Haskell-cafe] Re: Optimization fun

[Creighton Hogg]

On 2/10/07, Matthew Brecknell <haskell at brecknell.org> wrote:
>
> 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


This looks really slick to me, thanks.
So if I understand correctly, the main thing that makes this work is that
&&'ing the test with the accumulator r will make it bail out of the fold as
soon as one of the two tests is failed because the result must be False?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070211/ecbdd167/attachment.htm