what is the relationship between Haskell's FreeT and Coroutine type

Question

In the "Coroutine Pipelines" article in Monad.Reader Issue 19, the author defines a generic Coroutine type:

newtype Coroutine f m a = Coroutine
  { resume :: m (Either (f (Coroutine f m a)) a)
  }

I noticed that this type is very similar to the FreeT type from the free package:

data FreeF f a b = Pure a | Free (f b)

newtype FreeT f m a = FreeT
  { runFreeT :: m (FreeF f a (FreeT f m a))
  }

It seems that FreeT and Coroutine are isomorphic. Here are the functions mapping from one to the other:

freeTToCoroutine
  :: forall f m a. (Functor f, Functor m) => FreeT f m a -> Coroutine f m a
freeTToCoroutine (FreeT action) = Coroutine $ fmap f action
  where
    f :: FreeF f a (FreeT f m a) -> Either (f (Coroutine f m a)) a
    f (Pure a) = Right a
    f (Free inner) = Left $ fmap freeTToCoroutine inner

coroutineToFreeT
  :: forall f m a. (Functor f, Functor m) => Coroutine f m a -> FreeT f m a
coroutineToFreeT (Coroutine action) = FreeT $ fmap f action
  where
    f :: Either (f (Coroutine f m a)) a -> FreeF f a (FreeT f m a)
    f (Right a) = Pure a
    f (Left inner) = Free $ fmap coroutineToFreeT inner

I have the following questions:

1. What is the relationship between the FreeT and Coroutine types? Why didn't the author of "Coroutine Pipelines" use the FreeT type instead of creating the Coroutine type?
2. Is there some sort of deeper relationship between free monads and coroutines? It doesn't seem like a coincidence that the types are isomorphic.

3. Why aren't popular streaming libraries in Haskell based around FreeT?

   The core datatype in pipes is Proxy:

   data Proxy a' a b' b m r
     = Request a' (a  -> Proxy a' a b' b m r )
     | Respond b  (b' -> Proxy a' a b' b m r )
     | M          (m    (Proxy a' a b' b m r))
     | Pure    r
   

   The core datatype in conduit is Pipe:

   data Pipe l i o u m r
     = HaveOutput (Pipe l i o u m r) (m ()) o
     | NeedInput (i -> Pipe l i o u m r) (u -> Pipe l i o u m r)
     | Done r
     | PipeM (m (Pipe l i o u m r))
     | Leftover (Pipe l i o u m r) l
   

   I imagine it would be possible to write the Proxy or Pipe datatypes based around FreeT, so I wonder why it is not done? Is it for performance reasons?

   The only hint of FreeT I've seen in the popular streaming libraries is pipes-group, which uses FreeT to group items in streams.

Answer 1

To answer your second question, let's first simplify the problem by looking at Free. Free f a allows you to construct f-shaped ASTs of a-values for later reduction (aka, interpretation). When comparing the monad transformers in the article with unlifted free constructions, we can simply choose Identity for m, as is the usual practice for constructing base monads from their transformers: Free f = FreeT Identity f.

The Monad Reader article first presents a lifted Trampoline monad transformer, so let's start by looking at the unlifted version, with Identity elided:

data Trampoline a = Return a | Bounce (Trampoline a)

If we compare this to Free

data Free f r = Pure r | Free (f (Free f r))

and squint a bit, we can see that all we really need to do is "remove" the f-structure, just as we previously "removed" the m-structure. So, we have Trampoline = Free Identity, again because Identity has no structure. That, in turn, means that this trampoline is a FreeT Identity Identity: a sort of degenerate coroutine with trivial shape and no way to use effects to determine whether to bounce or return. So that's the difference between this trampoline and the trampoline monad transformer: the transformer allows the bounces to be interleaved with m-actions.

With a bit of work, we can also see that generators and consumers are free monads for specific choices of f, respectively ((,) a) and ((->) a). Their free monad transformer versions similarly allow them to interleave m-actions (e.g., a generator can ask for user input before yielding). Coroutine generalizes both f, the AST shape (fixed to f ~ Identity for Trampoline) and the type of effects which can be interleaved (fixed to no effects, or m ~ Identity) for Free. This is exactly FreeT m f.

Intuitively, if Free f is the monad for pure construction of f-shaped ASTs then FreeT m f is the monad for constructing f-shaped ASTs interleaved with effects supplied by m. If you squint a bit, this is exactly what coroutines are: a full generalization that parameterizes a reified computation on both the shape of the constructed AST and the type of effects used to construct it.