[Haskell-begin] Maximum of a List?

[Braden Shepherdson]

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...
> 
>   / _ \ /\  /\/ __(_)
>  / /_\// /_/ / /  | |      GHC Interactive, version 6.4, for Haskell 98.
> / /_\\/ __  / /___| |      http://www.haskell.org/ghc/
> \____/\/ /_/\____/|_|      Type :? for help.
> 
> Loading package base-1.0 ... linking ... done.
> Prelude> :l ..\test.hs
> Compiling Main             ( ..\test.hs, interpreted )
> Ok, modules loaded: Main.
> *Main> answer
> GHC's heap exhausted: current limit is 268435456 bytes;
> Use the `-M<size>' option to increase the total heap size.
> 
> I also tried writing a simple 'max' function that I thought was tail 
> recursive, and that that would help. Same error. I'm finding it hard to 
> believe that finding a maximum of a list of a million small integers 
> would cause this kind of overflow...is it really that big of a problem?

Hello Steve,

First, is there a reason to use such an old GHC? Newer versions produce 
much better code.

That said, certainly 6.4 is sufficient for this problem. foldl' is the 
right choice here, it is strict in the accumulating parameter and that 
is what you want. The problem is the two parameters in f. When you make 
the recursive call 'f (acc + 1) ...', a thunk is being created to hold 
that calculation (acc + 1). It isn't being evaluated right away, so the 
thunk remains. On the next iteration, acc is incremented again. You are 
effectively building up the expression 'acc + 1 + 1 + 1 + 1 ...', 
perhaps quite deeply. This takes up heap space; apparently too much 
space. Similarly, the (x `div` 2) and (3 * x + 1) calculations are being 
suspended as thunks, though x gets forced on the next call, since it is 
tested by the guards.

Adding the pragma
{-# LANGUAGE BangPatterns #-} at the top of the file, you could then 
annotate acc:

f !acc x

this seems to run in constant space for me.

Note that there is a much more concise way to write f, though I doubt it 
would be much faster. Consider 'iterate' and 'takeWhile'.

Finally, compiling to a binary with ghc -O2 will yield much better speed 
than ghci. And GHC 6.8.3 would provide a further 20%+ speed boost, if 
installing it is an option on your environment.


Hope this helps,

Braden Shepherdson
shepheb