# [Haskell-Cafe] Quick question for a slow program

Dries Harnie dries at harnie.be
Sat Jun 7 13:58:45 EDT 2008

```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