<div><span class="gmail_quote">On 11/22/07, <b class="gmail_sendername">apfelmus</b> <<a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de</a>> wrote:</span>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">A context passing implementation (yielding the ContT monad transformer)<br>will remedy this.</blockquote>
<div> </div>
<div>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?
</div>
<div> </div>
<div>If so, that's pretty cool.</div>
<div> </div>
<div>To be clear, by ContT I mean this monad:</div>
<div>
<div><font face="courier new,monospace">
<div>newtype ContT m a = ContT { runContT :: forall b. (a -> m b) -> m b }</div>
<div> </div>
<div>instance Monad m => Monad (ContT m) where<br> return x = ContT $ \c -> c x<br> m >>= f = ContT $ \c -> runContT m $ \a -> runContT (f a) c<br> fail = lift . fail</div>
<div> </div>
<div>instance MonadTrans ContT where<br> lift m = ContT $ \c -> m >>= c</div>
<div> </div>
<div>evalContT :: Monad m => ContT m a -> m a<br>evalContT m = runContT m return</div>
<div> </div>
<div></div></font> -- ryan</div></div></div>