<br><br><div><span class="gmail_quote">On 2/10/07, <b class="gmail_sendername">Matthew Brecknell</b> <<a href="mailto:haskell@brecknell.org">haskell@brecknell.org</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Rafael Almeida said:<br>> I've always found the following definition of the sieve of eratosthenes<br>> the clearest definition one could write:<br>><br>> sieve [] = []<br>> sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
<br>><br>> It doesn't perform better than Augustsson's solution. It does fairly<br>> worse, actually, but it performs way better than Hogg's 13s algorithm.<br>> It took around 0.1s on my machine.<br>
<br>Interesting. I found the sieve to be somewhere around the 13s mark,<br>while Lennart's solution was about 0.15s. But that may just be because I<br>haven't yet made the jump from GHC 6.4.2 to 6.6...<br><br>I also found that a handcrafted loop-fusion reduced Lennart's solution
<br>to 0.08s:<br><br>primes :: [Int]<br>primes = 2 : filter isPrime [3,5..] where<br> f x p r = x < p*p || mod x p /= 0 && r<br> isPrime x = foldr (f x) True primes</blockquote><div><br>This looks really slick to me, thanks.
<br></div>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?
<br></div>