[Haskell-cafe] Re: An interesting monad: "Prompt"
Derek Elkins
derek.a.elkins at gmail.com
Sat Nov 24 00:32:56 EST 2007
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.
More information about the Haskell-Cafe
mailing list