On Fri, 2007-11-23 at 21:11 -0800, Ryan Ingram wrote: > On 11/22/07, apfelmus <[EMAIL PROTECTED]> 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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe