Running out of memory in a simple program

[Malcolm Wallace]

Magnus Lindberg <f98mali@dd.chalmers.se> writes:

>   I have a problem with monads. When a monadic function calls itself
>   many times (see below) Hugs and GHCi runs out of memory/stack,

A little heap profiling shows that the memory is being filled
with unevaluated function applications.  The effect of your 'inc'
computation is to build a huge lambda expression whose size is directly
proportional to the integer argument.  Each recursive call of 'inc'
simply builds an unevaluated application of the previous lambda by
wrapping another lambda around the outside.

You probably hoped that lazy evaluation would build only enough of the
lambda expression as was immediately needed, delaying the construction
of the "tail" of the function (i.e. the right-hand-side of the >>=) until
later.  Unfortunately, graph reduction doesn't work like that.  The
function in an application must be fully evaluated before it is entered,
hence the build-up of thunks.

Regards,
    Malcolm

> newtype M a = M (Int -> (a,Int))
> 
> instance Monad M where
>   return x  = M $ \i -> (x,i)
>   M f >>= k = M $ \i -> let (x,i2) = f i
>                             M f2 = k x
>                         in f2 i2
> 
> inc 0 = return ()
> inc n = do inc'; inc (n-1)
>  where inc' = M $ \i -> ((), i+1)
> 
> runM :: M () -> IO ()
> runM  (M m) =
>   print (m 0)
>   -- in print i
> 
> run n = runM (inc n) -- crashes for large n !!