[Haskell-cafe] Re: Optimization fun
Matthew Brecknell
haskell at brecknell.org
Sun Feb 11 21:32:55 EST 2007
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.
More information about the Haskell-Cafe
mailing list