Running out of memory in a simple program

[Josef Svenningsson]

Hmmm, I generally try to avoid using seq. It's a hack and often one can
refrain from using it. Here's how I would solve the problem:

First of all your monad constains an int which is passed around. Typically
we want this to be computed strictly. The way to do this is to add a
strictness annotation. A naive try would be this:

newtype M a = M (Int -> (a,!Int))

Unfortunately we cannot have stricness annotation in this way. So to
achieve this effect we make a new data type for pairs with a strict int:

data PairInt a = P a !Int

Secondly, your bind is lazy. This can be usedful but usually one wants it
to be strict because then we get tail-recursion. The lack of
tail-recursion is the second problem in this example. Strictness is
achieved be converting let to case like this:

  M f >>= k = M $ \i -> case f i of
                          P x i2 ->
                                case k x of
                                  M f2 -> f2 i2

This version doesn't have any problems with spaceleaks. It can now swallow
pretty large numbers, I've tried with 1000000.

I hope this sheds some light on the problem.

	/Josef


On Fri, 15 Nov 2002, Magnus Lindberg wrote:

> Hi again!
> Thanks for your help, Malcolm. I added `seq' at two places to prevent
> laziness and now I never run out of memory.
>
> instance Monad M where
>   return x  = M $ \i -> (x,i)
>   M f >>= k = M $ \i -> let (x,i2) = i `seq' f i
>                             M f2 = x `seq' k x
>                         in f2 i2
>
> (however, I think that just one of the two `seq' should do but if I
> remove any single `seq' then I still run out of memory :(  )
>
> Kind regards
>   Magnus
> _______________________________________________
> Haskell mailing list
> Haskell@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
>