MonadTrans instance for Free violates monad transformer laws

[Gabriella439]

Like the title says, the MonadTrans instance for Free violates both monad transformer laws. I'll begin with the first law:

-- The first monad transformer law, written as a functor identity law
(lift .) return /= return

This is because the left-hand side creates a Pure embedded within a Free:

lift . return
= Free . liftM Pure . return
= Free . return . Pure

... but the right-hand side creates just a naked Pure:

return
= Pure

The MonadTrans instance for Free also violates the second monad transformer law:

-- The second monad transformer law, written as a functor composition law
(lift .) (f >=> g) /= (lift .) f >=> (lift .) g

The left-hand side comes out to:

lift . (f >=> g)
= Free . liftM Pure . (f >=> g)
= \x -> Free $ liftM Pure $ f x >>= g

... which gives a Pure embedded within a single Free, whereas the right-hand side:

lift . f >=> lift . g
= \x -> lift (f x) >>= lift . g
= \x -> Free (liftM Pure $ f x) >>= Free . liftM Pure . g
= \x -> Free (liftM (Free . liftM Pure . g) $ f x)

... gives a Pure embedded within two Frees.

The laws are only true if you apply retract to both sides of the equation, but retract is not a monomorphism.

[Gabriella439]

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.

[ekmett]

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.

[Gabriella439]

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.

[ekmett]

On Sun, Mar 25, 2012 at 11:25 AM, Gabriel439 <
reply@reply.github.com

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

[Gabriella439]

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.

[sjoerdvisscher]

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

[Gabriella439]

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

[ekmett]

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.