Wie korrelieren die freie Monade und die reaktive Erweiterung?

14

Ich komme aus einem C # -Hintergrund, in dem sich LINQ zu Rx.NET entwickelt hat, hatte aber immer ein gewisses Interesse an FP. Nach einer Einführung in Monaden und einigen Nebenprojekten in F # war ich bereit zu versuchen, die nächste Stufe zu erreichen.

Nach mehreren Gesprächen über die freie Monade von Leuten aus Scala und mehreren Zuschreibungen in Haskell oder F # habe ich Grammatiken mit eingeschalteten Dolmetschern gefunden, damit das Verständnis IObservableKetten ziemlich ähnlich ist.

In FRP erstellen Sie eine Operationsdefinition aus kleineren domänenspezifischen Abschnitten, einschließlich Nebenwirkungen und Fehlern, die in der Kette verbleiben, und modellieren Ihre Anwendung als eine Reihe von Operationen und Nebenwirkungen. In der freien Monade tun Sie, wenn ich es richtig verstanden habe, dasselbe, indem Sie Ihre Operationen als Funktoren ausführen und sie mit coyoneda anheben.

Was wären die Unterschiede zwischen beiden, die die Nadel in Richtung eines der Ansätze neigen? Was ist der grundlegende Unterschied bei der Definition Ihres Dienstes oder Programms?

MLProgrammer-CiM
quelle
2
Hier ist ein interessanter Weg, um über das Problem nachzudenken ... FRP kann als Monade angesehen werden, auch wenn es normalerweise nicht so formuliert ist . Die meisten (wenn auch nicht alle) Monaden sind isomorph zur freien Monade . Da dies Contdie einzige Monade ist, die ich gesehen habe und die nicht über die freie Monade ausgedrückt werden kann, kann man wahrscheinlich davon ausgehen, dass es sich um eine FRP handelt. Da kann fast alles andere .
Jules
2
Erik Meijer, der Designer von LINQ und Rx.NET, IObservableist eine Instanz der Fortsetzung Monade.
Jörg W Mittag
1
Ich habe momentan keine Zeit, die Details zu klären, aber ich vermute, dass sowohl die RX-Erweiterungen als auch der kostenlose Monad-Ansatz sehr ähnliche Ziele erreichen, aber möglicherweise leicht unterschiedliche Strukturen aufweisen. Es ist möglich, dass RX Observables selbst Monaden sind, und Sie können dann mithilfe von Observables eine freie Monadenberechnung auf eine abbilden - genau das bedeutet "frei" in "freie Monade". Oder vielleicht ist die Beziehung nicht so direkt und Sie lernen nur, wie sie für ähnliche Zwecke verwendet werden.
Tikhon Jelvis

Antworten:

6

Monaden

Eine Monade besteht aus

  • Ein Endofunktor . In unserer Welt der Softwareentwicklung können wir sagen, dass dies einem Datentyp mit einem einzigen, uneingeschränkten Typparameter entspricht. In C # wäre dies etwa so:

    class M<T> { ... }
    
  • Zwei über diesen Datentyp definierte Operationen:

    • returnIch purenehme einen "reinen" Wert (dh einen TWert) und "hülle" ihn in die Monade (dh es wird ein M<T>Wert erzeugt ). Da returnes sich bei C # um ein reserviertes Schlüsselwort handelt, werde ich purevon nun an auf diesen Vorgang verweisen. In C # purewäre eine Methode mit einer Signatur wie:

      M<T> pure(T v);
      
    • bind/ flatmapnimmt einen monadischen Wert ( M<A>) und eine Funktion an f. fNimmt einen reinen Wert und gibt einen monadischen Wert zurück ( M<B>). Daraus bindergibt einen neuen monadischen Wert ( M<B>). bindhat die folgende C # Signatur:

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

Auch, um eine Monade zu sein, pureund bindmüssen die drei Monadengesetze befolgen.

Eine Möglichkeit, Monaden in C # zu modellieren, besteht darin, eine Schnittstelle zu erstellen:

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

(Hinweis: Um die Dinge kurz und aussagekräftig zu halten, nehme ich mir in dieser Antwort einige Freiheiten mit dem Code.)

Jetzt können wir Monaden für konkrete Datentypen implementieren, indem wir konkrete Implementierungen von implementieren Monad<M>. Beispielsweise könnten wir die folgende Monade implementieren für 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);
  }
}

(Ich verwende die LINQ-Syntax absichtlich, um die Beziehung zwischen LINQ-Syntax und Monaden herauszufinden. Beachten Sie jedoch, dass wir die LINQ-Abfrage durch einen Aufruf von ersetzen können SelectMany.)

Können wir nun eine Monade definieren für IObservable? Es scheint so:

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

Um sicherzugehen, dass wir eine Monade haben, müssen wir die Monadengesetze beweisen. Dies kann nicht trivial sein (und ich kenne Rx.NET nicht gut genug, um zu wissen, ob sie auch nur anhand der Spezifikation bewiesen werden können), aber es ist ein vielversprechender Anfang. Um den Rest dieser Diskussion zu vereinfachen, nehmen wir einfach die in diesem Fall geltenden Monadengesetze an.

Freie Monaden

Es gibt keine singuläre "freie Monade". Freie Monaden sind vielmehr eine Klasse von Monaden, die aus Funktoren aufgebaut sind. Das heißt, wenn ein Funktor gegeben ist F, können wir automatisch eine Monade für F(dh die freie Monade von F) ableiten .

Functors

Wie Monaden können Funktoren durch die folgenden drei Elemente definiert werden:

  • Ein Datentyp, der über eine einzelne Variable vom Typ ohne Einschränkungen parametrisiert wird.
  • Zwei Operationen:

    • pureWickelt einen reinen Wert in den Funktor. Dies ist analog zu pureeiner Monade. Tatsächlich sollten für Funktoren, die auch Monaden sind, die beiden identisch sein.
    • fmapOrdnet Werte in der Eingabe über eine bestimmte Funktion neuen Werten in der Ausgabe zu. Ihre Unterschrift lautet:

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

Wie Monaden müssen auch Funktoren die Funktorgesetze einhalten.

Ähnlich wie bei Monaden können wir Funktoren über die folgende Schnittstelle modellieren:

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

Nun, da Monaden eine Unterklasse von Funktoren sind, können wir auch Monadein wenig überarbeiten :

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

Hier habe ich eine zusätzliche Methode hinzugefügt joinund Standardimplementierungen von beiden joinund bereitgestellt bind. Beachten Sie jedoch, dass dies zirkuläre Definitionen sind. Sie müssten also mindestens das eine oder andere außer Kraft setzen. Beachten Sie außerdem, dass purejetzt von geerbt wird Functor.

IObservable und freie Monaden

Da wir nun eine Monade für definiert haben IObservableund Monaden eine Unterklasse von Funktoren sind, müssen wir in der Lage sein, eine Funktorinstanz für zu definieren IObservable. Hier ist eine Definition:

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

Jetzt, da wir einen Funktor definiert haben IObservable, können wir aus diesem Funktor eine freie Monade konstruieren. Und genau so IObservableverhält es sich mit freien Monaden - nämlich, aus denen wir eine freie Monade konstruieren können IObservable.

Nathan Davis
quelle
Aufschlussreiches Verständnis der Kategorietheorie! Ich wollte etwas, bei dem es nicht darum ging, wie sie erstellt werden, sondern um die Unterschiede beim Erstellen einer funktionalen Architektur und beim Modellieren der Effektkomposition. Mit FreeMonad können DSLs für wiederkehrende Vorgänge erstellt werden, während es bei IObservables eher um diskrete Werte im Zeitverlauf geht.
MLProgrammer-CiM
1
@ MLProgrammer-CiM, ich werde sehen, ob ich in den nächsten Tagen einige Einsichten dazu geben kann.
Nathan Davis
Ich würde ein praktisches Beispiel für freie Monaden lieben
l - '' '''--------- '' '' '' '' '' ''