[Haskell-cafe] Space efficiency problem

[Ben Rudiak-Gould]

Adrian Victor CRISCIU wrote:

>  Thanks for the advice. However, though I don't know how ghc manages
>  the heap, I am not sure it is possible to achieve constant heap
>  usage, because a value of type State is a function, and >>= is
>  creating a call stack in this case. I mean, I think that, even if the
>  argument of f :: a -> State s a has a stricness flag, the value m0 ::
>  State s a is itself a function of the state (with type s); then the
>  value ((m0 >>= f) >>= f) >>= .....) >>= f is applied to a state s0,
>  this must be passed down to the bottom of the call stack to perform
>  the actual computation. And this may eat up a lot of heap space.

I don't think this is a problem if the expression associates the other 
way (as your program does), i.e.

    m0 >>= (\x -> f x >>= (\x -> f x >>= (\x -> f x >>= ... f)))

This can be tail recursive if there's enough strictness.

On a related note, it seems like it might be worth introducing

    (=>>=) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

with a higher precedence than (>>=) and associating to the right, so 
that one could write

    m0 >>= f1 =>>= f2 =>>= ... =>>= fn

and avoid the inefficiency of the left-associative (>>=). Does this make 
any sense?

-- Ben