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