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