On 11/22/07, apfelmus
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