On 11/22/07, apfelmus <apfelmus@quantentunnel.de> wrote:

A context passing implementation (yielding the ContT monad transformer)
will remedy this.

Wait, are you saying that if you apply ContT to any monad that has the "left recursion on >>= takes quadratic time" problem, and represent all primitive operations via lift (never using >>= within "lift"), that you will get a new monad that doesn't have that problem?

If so, that's pretty cool.

To be clear, by ContT I mean this monad:

newtype ContT m a = ContT { runContT :: forall b. (a -> m b) -> m b }

instance Monad m => Monad (ContT m) where
    return x = ContT $ \c -> c x
    m >>= f = ContT $ \c -> runContT m $ \a -> runContT (f a) c
    fail     = lift . fail

instance MonadTrans ContT where
lift m = ContT $ \c -> m >>= c

evalContT :: Monad m => ContT m a -> m a
evalContT m = runContT m return

-- ryan