Comment la monade gratuite et les extensions réactives sont-elles corrélées?

14

Je viens d'un milieu C #, où LINQ a évolué en Rx.NET, mais a toujours eu un certain intérêt pour FP. Après une introduction aux monades et quelques projets parallèles en F #, j'étais prêt à essayer de passer au niveau suivant.

Maintenant, après plusieurs discussions sur la monade gratuite de personnes de Scala et plusieurs écritures en Haskell, ou F #, j'ai trouvé des grammaires avec des interprètes pour que la compréhension soit assez similaire aux IObservablechaînes.

Dans FRP, vous composez une définition d'opération à partir de blocs spécifiques à un domaine plus petit, y compris les effets secondaires et les échecs qui restent à l'intérieur de la chaîne, et modélisez votre application comme un ensemble d'opérations et d'effets secondaires. En monade libre, si j'ai bien compris, vous faites de même en faisant vos opérations en tant que foncteurs, et en les soulevant à l'aide de coyoneda.

Quelles seraient les différences entre les deux qui inclinent l'aiguille vers l'une des approches? Quelle est la différence fondamentale lors de la définition de votre service ou programme?

MLProgrammer-CiM
la source
2
Voici une façon intéressante de penser au problème ... FRP peut être considéré comme une monade, même s'il n'est généralement pas formulé de cette façon . La plupart (mais pas toutes) des monades sont isomorphes à la monade libre . Comme Contc'est la seule monade que j'ai vue suggérer qui ne peut pas être exprimée via la monade libre, on peut probablement supposer que FRP peut l'être. Comme presque tout le reste .
Jules
2
Selon Erik Meijer, le concepteur de LINQ et de Rx.NET, IObservableest une instance de la monade de continuation.
Jörg W Mittag
1
Je n'ai pas le temps de travailler sur les détails pour le moment, mais je suppose que les extensions RX et l'approche de la monade gratuite atteignent des objectifs très similaires mais peuvent avoir des structures légèrement différentes. Il est possible que les observables RX soient eux-mêmes des monades, puis vous pouvez mapper un calcul de monade libre à un calcul utilisant des observables - c'est très approximativement ce que signifie le «libre» dans «monade libre». Ou peut-être que la relation n'est pas si directe et que vous ne voyez que comment ils sont utilisés à des fins similaires.
Tikhon Jelvis

Réponses:

6

Monades

Une monade se compose de

  • Un endofuncteur . Dans notre monde du génie logiciel, nous pouvons dire que cela correspond à un type de données avec un seul paramètre de type sans restriction. En C #, ce serait quelque chose de la forme:

    class M<T> { ... }
    
  • Deux opérations définies sur ce type de données:

    • return/ pureprend une valeur "pure" (c'est-à-dire une Tvaleur) et "l'enveloppe" dans la monade (c'est-à-dire qu'elle produit une M<T>valeur). Puisque returnc'est un mot-clé réservé en C #, je vais utiliser purepour faire référence à cette opération à partir de maintenant. En C #, pureserait une méthode avec une signature comme:

      M<T> pure(T v);
      
    • bind/ flatmapprend une valeur monadique ( M<A>) et une fonction f. fprend une valeur pure et retourne une valeur monadique ( M<B>). À partir de ceux-ci, bindproduit une nouvelle valeur monadique ( M<B>). binda la signature C # suivante:

      M<B> bind(M<A> mv, Func<A, M<B>> f);
      

En outre, pour être une monade, pureet bindsont tenus d'obéir aux trois lois de la monade.

Maintenant, une façon de modéliser des monades en C # serait de construire une interface:

interface Monad<M> {
  M<T> pure(T v);
  M<B> bind(M<A> mv, Func<A, M<B>> f);
}

(Remarque: afin de garder les choses brèves et expressives, je vais prendre quelques libertés avec le code tout au long de cette réponse.)

Nous pouvons maintenant implémenter des monades pour des types de données concrets en implémentant des implémentations concrètes de Monad<M>. Par exemple, nous pouvons implémenter la monade suivante pour IEnumerable:

class IEnumerableM implements Monad<IEnumerable> {
  IEnumerable<T> pure(T v) {
    return (new List<T>(){v}).AsReadOnly();
  }

  IEnumerable<B> bind(IEnumerable<A> mv, Func<A, IEnumerable<B>> f) {
    ;; equivalent to mv.SelectMany(f)
    return (from a in mv
            from b in f(a)
            select b);
  }
}

(J'utilise délibérément la syntaxe LINQ pour appeler la relation entre la syntaxe LINQ et les monades. Mais notez que nous pourrions remplacer la requête LINQ par un appel à SelectMany.)

Maintenant, pouvons-nous définir une monade pour IObservable? Il semblerait donc:

class IObservableM implements Monad<IObservable> {
  IObservable<T> pure(T v){
    Observable.Return(v);
  }

  IObservable<B> bind(IObservable<A> mv, Func<A, IObservable<B>> f){
    mv.SelectMany(f);
  }
}

Pour être sûr que nous avons une monade, nous devons prouver les lois de la monade. Cela peut être non trivial (et je ne connais pas suffisamment Rx.NET pour savoir s'ils peuvent même être prouvés à partir de la seule spécification), mais c'est un début prometteur. Pour faciliter le reste de cette discussion, supposons simplement que les lois de la monade s'appliquent dans ce cas.

Monades gratuites

Il n'y a pas de "monade libre" singulière. Les monades libres sont plutôt une classe de monades construites à partir de foncteurs. Autrement dit, étant donné un foncteur F, nous pouvons automatiquement dériver une monade pour F(c'est-à-dire la monade libre de F).

Foncteurs

Comme les monades, les foncteurs peuvent être définis par les trois éléments suivants:

  • Un type de données, paramétré sur une seule variable de type sans restriction.
  • Deux opérations:

    • pureencapsule une valeur pure dans le foncteur. Ceci est analogue à pureune monade. En fait, pour les foncteurs qui sont aussi des monades, les deux doivent être identiques.
    • fmapmappe les valeurs de l'entrée aux nouvelles valeurs de la sortie via une fonction donnée. Sa signature est:

      F<B> fmap(Func<A, B> f, F<A> fv)
      

Comme les monades, les foncteurs sont tenus d'obéir aux lois des foncteurs.

Comme pour les monades, nous pouvons modéliser des foncteurs via l'interface suivante:

interface Functor<F> {
  F<T> pure(T v);
  F<B> fmap(Func<A, B> f, F<A> fv);
}

Maintenant, comme les monades sont une sous-classe de foncteurs, nous pourrions également refactoriser Monadun peu:

interface Monad<M> extends Functor<M> {
  M<T> join(M<M<T>> mmv) {
    Func<T, T> identity = (x => x);
    return mmv.bind(x => x); // identity function
  }

  M<B> bind(M<A> mv, Func<A, M<B>> f) {
    join(fmap(f, mv));
  }
}

Ici, j'ai ajouté une méthode supplémentaire join, et fourni des implémentations par défaut de joinet bind. Notez cependant qu'il s'agit de définitions circulaires. Vous devez donc remplacer au moins l'un ou l'autre. Notez également qu'il pureest désormais hérité de Functor.

IObservable et monades gratuites

Maintenant, puisque nous avons défini une monade pour IObservableet puisque les monades sont une sous-classe de foncteurs, il s'ensuit que nous devons être en mesure de définir une instance de foncteur pour IObservable. Voici une définition:

class IObservableF implements Functor<IObservable> {
  IObservable<T> pure(T v) {
    return Observable.Return(v);
  }

  IObservable<B> fmap(Func<A, B> f, IObservable<A> fv){
    return fv.Select(f);
  }
}

Maintenant que nous avons défini un foncteur IObservable, nous pouvons construire une monade libre à partir de ce foncteur. Et c'est précisément ce qui se IObservablerapporte aux monades libres - à savoir, que nous pouvons construire une monade libre à partir de IObservable.

Nathan Davis
la source
Compréhension perspicace de la théorie des catégories! J'étais après quelque chose qui ne parlait pas de la façon dont ils sont créés, plus des différences lors de la construction d'une architecture fonctionnelle et de la modélisation de la composition d'effets avec l'un ou l'autre. FreeMonad peut être utilisé pour créer des DSL pour des opérations réifiées, tandis que les IObservables concernent davantage les valeurs discrètes au fil du temps.
MLProgrammer-CiM
1
@ MLProgrammer-CiM, je vais voir si je peux ajouter quelques informations à ce sujet dans les prochains jours.
Nathan Davis
J'aimerais un exemple pratique de monades gratuites
l --''''''----------------- '' '' '' '' '' '22