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