<div><span class="gmail_quote">On 11/22/07, <b class="gmail_sendername">apfelmus</b> &lt;<a href="mailto:apfelmus@quantentunnel.de">apfelmus@quantentunnel.de</a>&gt; 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>&nbsp;</div>
<div>Wait, are you saying that if you apply ContT to any monad that has the &quot;left recursion on &gt;&gt;=&nbsp;takes quadratic time&quot; problem, and represent all primitive operations via lift (never using &gt;&gt;= within&nbsp;&quot;lift&quot;), that you will get a new monad that doesn&#39;t have that problem?
</div>
<div>&nbsp;</div>
<div>If so, that&#39;s pretty cool.</div>
<div>&nbsp;</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 -&gt; m b) -&gt; m b }</div>
<div>&nbsp;</div>
<div>instance Monad m =&gt; Monad (ContT m) where<br>&nbsp;&nbsp;&nbsp; return x = ContT $ \c -&gt; c x<br>&nbsp;&nbsp;&nbsp; m &gt;&gt;= f&nbsp; = ContT $ \c -&gt; runContT m $ \a -&gt; runContT (f a) c<br>&nbsp;&nbsp;&nbsp; fail&nbsp;&nbsp;&nbsp;&nbsp; = lift . fail</div>
<div>&nbsp;</div>
<div>instance MonadTrans ContT where<br>&nbsp;&nbsp;&nbsp; lift m&nbsp;&nbsp; = ContT $ \c -&gt; m &gt;&gt;= c</div>
<div>&nbsp;</div>
<div>evalContT :: Monad m =&gt; ContT m a -&gt; m a<br>evalContT m = runContT m return</div>
<div>&nbsp;</div>
<div></div></font>&nbsp; -- ryan</div></div></div>