[Haskell-beginners] Re: [Haskell-begin] Maximum of a List?

Steve Klabnik steve.klabnik at gmail.com
Mon Jul 28 16:32:34 EDT 2008

On Mon, Jul 28, 2008 at 12:15 PM, Niels Aan de Brugh <nielsadb at gmail.com>wrote:

> Because you're not providing the right number. :-)

You know, I realized that this morning after I woke up....ha ha. Sometimes a
good night's sleep is all it takes...

> I've tested your code with strictness annotations and it appears to not
> make a difference. GHC employs several optimization techniques, one of those
> being strictness analysis, so maybe it is already using a strict, unboxed
> integer.

Ah. I figured that I probably didn't have to worry about it manually...

> The real speed-up (a non-linear one) here is not to re-calculate every
> sequence over and over again, but keep it in a map/array (as suggested by
> Rafael and me). I've found some Euler puzzles are impossible to solve
> without this technique.
> Niels
> P.S.: If you're really going for speed, compile (not interpret) the code
> (using -O -fvia-C, and there's some more stuff in the manual) using the
> latest greatest version of GHC.

I'll keep this in mind. Right now I'm going for just doing it, but I'll heed
your advice for future problems.

Finally, what I ended up doing:

f :: Integer -> Integer -> Integer
f acc x
    | x == 1 = acc
        | even x = f (acc + 1) (x `div` 2)
        | otherwise = f (acc + 1) (3 * x + 1)

g :: Integer -> (Integer, Integer)
g x = (f 1 x, x)

answer = (foldl' max (0,0)) $ map g [1 .. 999999]

main = putStrLn( show answer)

Again, not the most efficient, but pretty clean. Runs in just under a minute
on my machine. Thanks again!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20080728/855e6787/attachment.htm

More information about the Beginners mailing list