[Haskell-cafe] Optimization fun

[Creighton Hogg]

On 2/10/07, Lennart Augustsson <lennart at augustsson.net> wrote:
>
> There are many things that makes your code slow.
> * The default for Haskell is to compute with Integer, not Int.  So
> that makes from Integral and floor very slow.
> * foldl' is a bad choice, because it is too strict, you want to abort
> the loop as soon as possible.


Now why is foldl' too strict?  I don't think I understand?

* your take is really wrong.  The number of primes you need to take
> cannot be computed like that.  You want to take primes while the sqrt
> of x is larger than the prime.


Yeah, I don't know what the %#*( happened there.  I should have proofread.

Also, your code is not idiomatic Haskell.
>
> Here's a different version:
>
> primes :: [Int]
> primes = 2:filter isPrime [3,5..]
>      where isPrime x = all (\ y -> x `mod` y /= 0) $ takeWhile (\ p -
> > p*p <= x) primes
>
>
> On Feb 10, 2007, at 21:02 , Creighton Hogg wrote:
>
> > primes = 2:(foldr (\x y -> if isPrime x then x:y else y) [] [3..])
> >     where isPrime x = foldl' (\z y -> z && (if x `mod` y == 0 then
> > False else True)) True (take (floor $ sqrt $ fromIntegral x) primes)
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070210/9806a6e3/attachment.htm