Hmm. I guess I stand corrected, but maybe you would explain the following:

import System.Time( getClockTime )

add_up 0 acc = acc
add_up n acc = add_up (n - 1) (acc + n)

time = getClockTime >>= print >> return ""

main = do
    time
    print (add_up 10000000 0)
    time
    print (add_up 5000000 0)
    time
    print (add_up 10000000 0)
    time
    return ()

{-
c:\ghc\ghc-6.4\code>ghc 493959.hs

c:\ghc\ghc-6.4\code>main
Thu Sep 22 17:57:10 GMT Daylight Time 2005
Heap exhausted;
Current maximum heap size is 268435456 bytes (256 Mb);
use `+RTS -M<size>' to increase it.

c:\ghc\ghc-6.4\code>main
Thu Sep 22 17:58:10 GMT Daylight Time 2005
50000005000000
Thu Sep 22 17:58:13 GMT Daylight Time 2005
12500002500000
Thu Sep 22 17:58:15 GMT Daylight Time 2005
50000005000000
Thu Sep 22 17:58:15 GMT Daylight Time 2005

-}
[download]

When compiled without optimisations, the program runs out of memory when trying to sum the integers from 1 to 10,000,000. So, as you advised, I compile with optimisations.

Now it performs the calculation in around 3 seconds. The first time.

It then takes around 2 seconds to calculated the sum of 1 .. 5,000,000. Obviously, the intermediate value was not memoized. But ...

Ask it to calculate 1 .. 10,000,000 a second time, and it now takes no time at all!

One interpretation of this empirical evidence is that without optimisations enabled, it runs out of memory trying to retain all the intermediate return values. With the optimisations enabled, it only retains those values that are returned to the caller, and not the intermediate values..

The truth is (probably) somewhat more along the lines that the optimiser replaces the recursive algorithm with an iterative loop, thereby doing away with any recursive calls, and therefore, also doing away with the memoization of the intermediate function returns--as there are none.

This would be a more convincing argument if I knew how to get more accurate timestamping, but none the less, both the empirical evidence and my (shallow) understanding of GHC internals, support the statement I made--every single function in Haskell is automatically memoized by the compiler--though I should have added a note to the effect that this only works for function calls that are not optimised away.

If you have the time/inclination to explain this further I would be happy to have my understanding clarified. If you prefer to this in by email or elsewhere, use the address on my homenode.