What is the relationship between Haskell FreeT and Coroutine

Question

What is the relationship between Haskell FreeT and Coroutine

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

:

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 type FreeT

from 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 they are FreeT

also Coroutine

isomorphic. Here are the functions that map functions to each 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:

What is the relationship between types FreeT

and Coroutine

? Why didn't the author of Coroutine Pipelines use type Coroutine

instead of Coroutine

type Coroutine

?
Is there some deeper relationship between free monads and coroutines? The types do not appear to be isomorphic.
Why aren't there popular streaming libraries in Haskell based on FreeT

?

Basic datatype in :pipes

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

      

        
        
        
      

    
```
Basic datatype in :conduit

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 am guessing it would be possible to create datatypes Proxy

or Pipe

based on FreeT

, so I wonder why this is not done? Is this for performance reasons?

The only hint FreeT

I've seen in popular streaming libraries is pipes-group , which it uses FreeT

for group in streams.

+3

coroutine haskell free-monad conduit haskell-pipes

illabout Jul 19 17 at 13:27

source to share

1 answer

Rein Henrichs · Accepted Answer · 2017-07-21T17:38:58+0000

To answer the second question, let's simplify the problem first by looking Free

. Free f a

allows you to construct f

-shaped AST a

-values for subsequent reduction (aka, interpretation). Comparing monad transformers in the article with the non-free-free designs, we can simply choose Identity

to m

, as is usually done for the construction of the base of their monads transformers: Free f = FreeT Identity f

.

The first Monad Reader article features the removed monk Identity

trampling transformer, so let's start by looking at the unlighted version with elided:

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

If you compare this with Free

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

and feel a little, we can see that all we really need to do is "remove" the structure f

as we previously "removed" the structure m

. So we have Trampoline = Free Identity

, again because it Identity

has no structure. This, in turn, means that this trampoline is FreeT Identity Identity

: a kind of degenerate coroutine with a trivial form and no way to use effects to determine whether to bounce or return. So the difference between this trampoline and the monad-trampoline transformer: the transformer allows you to jump using m

-actions.

With a bit of work, we can also see that generators and consumers are free monads for certain options f

, respectively, ((,) a)

and ((->) a)

. Their free versions of monad transformers similarly allow them to intersperse m

-actions (for example, the generator can ask for user input before committing). Coroutine

summarizes both the f

form of the AST (fixed on f ~ Identity

for Trampoline) and the type of effects that can alternate (fixed with no effects or m ~ Identity

) for Free

. That's for sure FreeT m f

.

Intuitively, if it Free f

is a monad for a pure construction of f

-shaped AST, then it FreeT m f

is a monad for constructing f

-shaped AST, alternating with the effects provided m

. In case you're squinting a bit, this is exactly what coroutines are: a complete generalization that parameterizes an initialized computation in both the shape of the AST constructed and the type of effects used to construct it.

What is the relationship between Haskell FreeT and Coroutine

More articles: