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

On Fri, 2007-11-23 at 21:11 -0800, Ryan Ingram wrote:

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