Many architectures gives both the quotient and remainder when you use the division instruction, so divMod (quotRem) shouldn't cost more than a div or mod. But if the code generator takes advantage of that is another matter. On Feb 12, 2007, at 02:32 , Matthew Brecknell wrote:
I wrote:
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
Creighton Hogg wrote:
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?
Yes. Look at the definition of %% and ||:
True && x = x False && _ = False
True || _ = True False || x = x
The second argument of && or || won't be evaluated if the first determines the result.
And this brings you back to the point made by Lennart and others about why foldl is the wrong choice: foldl won't allow you to take advantage of this short-circuiting. Write out a few steps of each type of fold if you don't understand why.
Note, I wouldn't call r an accumulator: it's just the rest of the fold (which, as you've pointed out, only needs to be evaluated if you don't already know the result).
Since writing the above, I've realised that the second argument of the foldr most certainly shouldn't be True. One might be able to argue that False would be more correct, but really it's irrelevant since we know we'll never reach the end of the list of primes. What I found most surprising was that replacing True with undefined made the calculation about 10% faster (GHC 6.4.2, amd64):
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) undefined primes
Comparing this to DavidA's solution: At least on my platform, testing (x < p*p) is significantly quicker than using quotRem/divMod. I suspect quotRem actually requires the division to be performed twice, and multiplication is faster than division.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe