[Haskell-begin] Maximum of a List?
Niels Aan de Brugh
nielsadb at gmail.com
Sun Jul 27 07:12:48 EDT 2008
Steve Klabnik wrote:
> Hello everyone-
>
> I'm working on some project Euler problems today, and I'm stuck on
> one. It's not the problem itself that's the problem, it's that finding
> the maximum of a list makes me run out of heap space!
>
> http://projecteuler.net/index.php?section=problems&id=14
> <http://projecteuler.net/index.php?section=problems&id=14>
>
> my code:
>
> import Data.List
>
> f :: Int -> Int -> Int
> f acc x
> | x == 1 = acc
> | even x = f (acc + 1) (x `div` 2)
> | otherwise = f (acc + 1) (3 * x + 1)
>
> answer = (foldl' max 0) $ map (f 1) [1 .. 999999]
>
> I tried using 'foldl' max ' instead of 'maximum' because I thought
> that foldl' was supposed to work better than foldl or something...I
> could be confused on that point. Anyway, here's what I get...
>
I've had the same problem when solving that particular puzzle.
The code that solves the puzzle brute-force is following:
f x | even x = x `div` 2
| otherwise = 3*x + 1
col n = (takeWhile (/=1) $ iterate f n) ++ [1]
ls = [(length $ col n, n) | n <- [1..1000000]]
Now, with
maximumBy (\(a,_) (b,_) -> compare a b) ls
I run out of stack space. If I'm not mistaken, maxmimumBy uses foldl, so
maybe it blows up in the number of comparisons it stacks up (rather than
reduce these immediately).
Using foldl' or a custom made function (I used one so I could print
intermediate results):
m' x [] = x
m' (l,e) ((l',e'):xs) | l > l' = m' (l,e) xs
| otherwise = trace ("max: " ++ show
(l',e')) (m' (l',e') xs)
the problem can be solved. It does take a little while (over two
minutes). For all Euler puzzles I've solved so far I've always tried to
minimize "run time" + "development time", not just the run time.
The solution you gave (using foldl') works on my PC (GHC(i) 6.8.2
(Ubuntu package), Linux, 2GB of RAM). That is: it doesn't run out of
stack space. Unfortunately I wasn't able to get an answer out of it
either before I had to kill the process. I'm not sure which function is
so greedy on memory. Maybe you could try making the arguments for f strict.
The thing could probably be heavily optimized (like many Euler puzzles)
by adding state and keeping intermediate results (for f) in an array.
Niels
More information about the Beginners
mailing list