[Haskell-Cafe] Quick question for a slow program

[Daniel Fischer]

Am Samstag, 7. Juni 2008 11:26 schrieb Slavomir Kaslev:
> Hello,
>
> I was just brushing my haskell-fu skills writing a solution for Google
>
> Treasure Hunt Problem 4. Hers is what it looks like:
> > primes = sieve [2..]
> >     where
> >       sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

That alone breaks at least three of the tortoise's legs.
Simple trial division:
primes = 2:3:filter isPrime [5,7 .. ]

isPrime n
    | n < 2	= False
    | n < 4 = True
    | even n = False
    | otherwise = go (tail primes)
      where
	r = floor $ sqrt (fromIntegral n + 0.5)
	go (p:ps) = (r < p) || (n `mod` p /= 0) && go ps

is orders of magnitude faster. A really good prime generator wins a lot.

> >
> > sumOf n l = sum (take n l) : sumOf n (tail l)

This is also not really good,

sumOf n l = zipWith (-) (drop n sms) sms
      where
	sms = scanl (+) 0 l

is a bit faster, specialising 

primeSums = scanl (+) 0 primes

sumOfPrimes n = zipWith (-) (drop n primeSums) primeSums

a bit more.
I don't see more improvements directly.

> >
> > find l = foldl1 aux l
> >     where
> >       aux (x:xs) (y:ys) | x == y = x : aux xs ys
> >
> >                         | x < y  = aux xs (y:ys)
> >                         | x > y  = aux (x:xs) ys
> >
> > puzzle = find (reverse [primes, p7, p17, p41, p541])
> >     where
> >       p7 = sumOf 7 primes
> >       p17 = sumOf 17 primes
> >       p41 = sumOf 41 primes
> >       p541 = sumOf 541 primes
> >
> > main = do mapM (\x -> putStrLn $ show x) puzzle
>
> While the code is quite readable and straight forward it is as slow as
> tortoise with four legs broken. What optimizations would you suggest,
> while still keeping the code clear and highlevel?
>
> Thank you in advance.
>
> Cheers.