[Haskell-begin] Maximum of a List?

[Niels Aan de Brugh]

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