quelle est la relation entre type Freet de Haskell et Coroutine

Question

Dans l'article "Coroutine Pipelines" dans Monad.Reader Issue 19, l'auteur définit un type Coroutine générique:

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

Je remarque que c'est très similaire au type FreeT de l'emballage free:

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)) 
    } 

Il semble que FreeT et Coroutine sont isomorphes. Voici la mise en correspondance des fonctions de l'un à l'autre:

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 

je les questions suivantes:

1. Quelle est la relation entre les types FreeT et Coroutine? Pourquoi l'auteur de "Coroutine Pipelines" n'a-t-il pas utilisé le type FreeT au lieu de créer le type Coroutine?
2. Existe-t-il une sorte de relation plus profonde entre les monades libres et les coroutines? Cela ne semble pas une coïncidence si les types sont isomorphes.

3. Pourquoi les bibliothèques de streaming populaires dans Haskell ne sont-elles pas basées sur FreeT?

   Le type de données de base dans pipes est 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 
   

   Le type de données de base dans conduit est 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 
   

   J'imagine qu'il serait possible d'écrire les Proxy ou Pipe types de données à base autour FreeT , alors je me demande pourquoi ce n'est pas fait? Est-ce pour des raisons de performance?

   Le seul indice de FreeT que j'ai vu dans les bibliothèques de diffusion populaires est pipes-group, qui utilise FreeT pour regrouper des éléments dans les flux.

Answer 1

Pour répondre à votre deuxième question, simplifions d'abord le problème en regardant Free. Free f a vous permet de construire f-AST en forme de a -valeurs pour la réduction plus tard (aka, interprétation). Lorsque l'on compare les transformateurs monad dans l'article avec des constructions libres, on peut simplement choisir Identity pour m, comme c'est la pratique habituelle pour construire des monades de base à partir de leurs transformateurs: Free f = FreeT Identity f.

L'article Monad lecteur présente d'abord un transformateur de monade de trampoline levé, alors commençons par regarder la version non relevé, avec Identity élision:

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

Si l'on compare cela à Free

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

et un peu strabisme, nous pouvons voir que tout ce que nous avons vraiment besoin de faire est de "supprimer" la structure f, tout comme nous l'avons précédemment "enlevé" la structure m. Donc, nous avons Trampoline = Free Identity, encore une fois parce que Identity n'a pas de structure. Cela, à son tour, signifie que ce trampoline est un FreeT Identity Identity: une sorte de coroutine dégénérée avec une forme triviale et aucun moyen d'utiliser des effets pour déterminer s'il faut rebondir ou revenir. C'est la différence entre ce trampoline et le transformateur monad trampoline: le transformateur permet d'entrelacer les rebonds avec m -actions. Avec un peu de travail, nous pouvons également voir que les générateurs et les consommateurs sont des monades libres pour des choix spécifiques de f, respectivement ((,) a) et ((->) a). Leurs versions de transformateur monade libres leur permettent également d'entrelacer m -actions (par exemple, un générateur peut demander une entrée utilisateur avant de céder). Coroutine généralise à la fois f, la forme AST (fixée à f ~ Identity pour Trampoline) et le type d'effets qui peuvent être entrelacés (fixé à aucun effet, ou m ~ Identity) pour Free. C'est exactement FreeT m f.

Intuitivement, si Free f est la monade pour la construction pure de f RSHS alors FreeT m f est en forme de la monade pour la construction f RSHS avec des effets intercalées en forme fournis par m. Si vous louchez un peu, c'est exactement ce que sont les coroutines: une généralisation complète qui paramétrise un calcul réifié à la fois sur la forme de l'AST construite et sur le type d'effets utilisés pour la construire.