[Haskell-cafe] Re: An interesting monad: "Prompt"

[Derek Elkins]

On Fri, 2007-11-23 at 21:11 -0800, Ryan Ingram wrote:
> On 11/22/07, apfelmus <apfelmus at 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
>  


Indeed this was discussed on #haskell a few weeks ago.  That information
has been put on the wiki at
http://www.haskell.org/haskellwiki/Performance/Monads
and refers to a blog post http://r6.ca/blog/20071028T162529Z.html that
describes it in action.

I'm fairly confident, though I'd have to actually work through it, that
the Unimo work, http://web.cecs.pdx.edu/~cklin/  could benefit from
this.  In fact, I think this does much of what Unimo does and could
capture many of the same things.