[Haskell-cafe] Re: Optimization fun

[Matthew Brecknell]

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.