[Haskell-cafe] Space efficiency problem
Benjamin.Rudiak-Gould at cl.cam.ac.uk
Fri Nov 12 03:56:38 EST 2004
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
More information about the Haskell-Cafe