MonadTrans instance for Free violates monad transformer laws about free HOT 8 CLOSED

So, it turns out there's a very simple and elegant solution. Define a free monad transformer:

data FreeT f m r = FreeT { runFreeT :: m (Either r (f (FreeT f m r))) }

instance (Functor f, Monad m) => Monad (FreeT f m) where
    return = FreeT . return . Left
    m >>= f = FreeT $ runFreeT m >>= \x -> case x of
        Left  r -> runFreeT $ f r
        Right a -> return $ Right $ fmap (>>= f) a

instance MonadTrans (FreeT f) where
    lift = FreeT . liftM Left

The above solution is a common idiom among coroutine libraries that implement MonadTrans instances and it correctly satisfies the monad transformer laws.

from free.

Great catch.

I've actually built the free monad transformer for a related reason in scala, but had overlooked the actual law violation taking place here.

This is awkward because the existing MonadTrans is actually quite useful but the existence of liftF kind of takes the edge off.

This is definitely a "SHOULD FIX" issue. =)

I'll push a version with it when I can get a better grasp of what downstream packages will be broken, since a major version bump requires me to push about a dozen other packages of my own and I should audit any third party dependencies as well.

from free.

It's not urgent to fix (for me, at least). I only brought it up because I discovered the exact same violation in my own pipes library, which is basically inlines a Free monad and has a wrong MonadTrans instance, too. I checked your library to see how you addressed the issue and only noticed the problem that way.

In a future release I may also use the free monad transformer approach to fix the issue in pipes and if I do that I'd like to use this library as the dependency for it. So from my point of view the existence of the wrong MonadTrans is a not a big issue and it can wait for your next major version, but a free monad transformer would be a useful addition to the library, especially since a lot of coroutine libraries are basically hand-rolling their own right now.

from free.

On Sun, Mar 25, 2012 at 11:25 AM, Gabriel439 <
[email protected]

wrote:

It's not urgent to fix (for me, at least). I only brought it up because I
discovered the exact same violation in my own pipes library, which is
basically inlines a Free monad and has a wrong MonadTrans instance,
too. I checked your library to see how you addressed the issue and only
noticed the problem that way.

We seem to have invented basically the same construction.

At ClariFi have an in-house iteratee-like library (in scala) that looks a
lot like your pipes, except we use bidirectional channels so we can sent
signals back toward the sources. This basically makes the base monad we're
working over look a lot like the base functor for a Mealy machine.

In a future release I may also use the free monad transformer approach to

fix the issue in pipes and if I do that I'd like to use this library as the
dependency for it. So from my point of view the existence of the wrong
MonadTrans is a not a big issue and it can wait for your next major
version, but a free monad transformer would be a useful addition to the
library, especially since a lot of coroutine libraries are basically
hand-rolling their own right now.

I can definitely see the utility of it.

Hrmm. The worry that I have is that folks will then pop up to pressure me
into put the transformer version in as the default and use the type alias
approach pushed by the MTL to base Free on its implementation and I think
from a pedagogical standpoint that is a mistake, so if I do add it I'll
probably just add FreeT as a separate data type. and add its faster
Church-encoded variant as well.

Er that was a bit rambly but I hope you get the idea. =)

-Edward

from free.

I got the idea. I think a separate type is fine.

Regarding bidirectional channels, if you are using the base monad to signal back to upstream, you can implement the same behavior with unidirectional channels by having upstream yield a monadic action alongside its normal yielded value which signals to downstream its desired behavior up until the next time it is requested. This is the approach I'm currently using to safely intercept downstream termination without violating the category laws for pipes. The reason is that I can never get bidirectional channels to satisfy the identity law.

from free.

That FreeT type is exactly the same as the FreeT type from control-monad-free: http://hackage.haskell.org/packages/archive/control-monad-free/0.5.3/doc/html/Control-Monad-Free.html#g:3

from free.

Thanks for the tip! I can use that for now instead of rolling my own.

from free.

I've added FreeT and CofreeT. I've kept the illegal MonadTrans, Alternative and MonadPlus instances, but I've marked them as illegal in the comments.

from free.