[Haskell-Cafe] Quick question for a slow program

[Dries Harnie]

On Sat, 7 Jun 2008 12:26:17 +0300
"Slavomir Kaslev" <slavomir.kaslev at gmail.com> wrote:

> 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]
> >
> > sumOf n l = sum (take n l) : sumOf n (tail l)
> >
> > 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?

While I can't quite prove it, I surmise find is wasting a lot of time
tracking down numbers which are sums of three or four of those lists before
continuing.

Here's mine:

> sliding n = map (sum . take n) $ tails primes
> 
> merge (x:xs) (y:ys) | x < y     = x:merge xs (y:ys)
> 	              | otherwise = y:merge (x:xs) ys
> 
> four = filter (\l -> length l == 5) $ group $ foldr1 merge $ map sliding [1,5,43,107,689]

In my original implementation I used an isPrime test at the end, but I like
your approach better (hence the 1 in map sliding).

Does this still count as "clear and highlevel"? :)

Dries Harnie
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080607/f1cb8c99/signature.bin