Was sind freie Monaden?

Question

Ich habe den Begriff Freie Monade auftauchen jede jetzt und dann seit einiger Zeit, aber jeder scheint sie nur zu verwenden/zu diskutieren, ohne zu erklären, was sie sind. Also: Was sind freie Monaden? (Ich würde sagen, ich bin mit Monaden und den Haskell-Grundlagen vertraut, habe aber nur eine sehr grobe Kenntnis der Kategorientheorie).

Answer 1

Ich denke, ein einfaches konkretes Beispiel ist hilfreich. Angenommen, wir haben einen Funktor

data F a = One a | Two a a | Two' a a | Three Int a a a

mit dem offensichtlichen fmap . Dann Free F a ist der Typ der Bäume, deren Blätter den Typ a und deren Knoten mit der Kennzeichnung One , Two , Two' et Three . One -Knoten haben ein Kind, Two - und Two' -Knoten haben zwei Kinder und Three -Knoten haben drei und sind außerdem mit einem Int .

Free F ist eine Monade. return Karten x zu dem Baum, der nur ein Blatt mit Wert ist x . t >>= f sieht sich jedes der Blätter an und ersetzt sie durch Bäume. Wenn das Blatt einen Wert hat y ersetzt es dieses Blatt durch den Baum f y .

Ein Diagramm verdeutlicht dies, aber ich habe nicht die Möglichkeit, es einfach zu zeichnen!

Answer 2

Ich versuche, eine "Brücken"-Antwort zwischen den supereinfachen Antworten hier und der vollständigen Antwort zu geben.

Die "freien Monaden" bilden also eine "Monade" aus einem beliebigen "Funktor", also nehmen wir diese der Reihe nach.

Funktoren im Detail

Einige Dinge sind auf Typenebene Adjektive Das bedeutet, dass sie ein Substantiv vom Typ "Ganzzahlen" nehmen und ein anderes Substantiv vom Typ "Listen von Ganzzahlen" oder "Paare von Zeichenketten mit Ganzzahlen" oder sogar "Funktionen, die Zeichenketten aus Ganzzahlen erzeugen" zurückgeben. Um ein beliebiges Adjektiv zu bezeichnen, möchte ich das Ersatzwort "blau" verwenden.

Aber dann bemerken wir ein Muster, dass einige dieser Adjektive Input-ish ou Ausgabe: in dem Substantiv, das sie modifizieren. Zum Beispiel "Funktionen, die Zeichenketten aus __ machen" ist input-ish, "Funktionen, die Zeichenketten in __ verwandeln" ist output-ish. Die Regel hier beinhaltet, dass ich eine Funktion habe X Y ein Adjektiv "blau" ausgegeben wird, oder ein Funktor ob ich eine solche Funktion verwenden kann, um ein blaues X in eine blaue Y . Stellen Sie sich einen "Feuerschlauch vor, der sprüht X s" und dann schraubt man an diesem X Y Funktion und jetzt sprüht Ihr Feuerschlauch Y s. Oder es ist inputtish oder ein kontravariant wenn es das Gegenteil ist, ein Staubsauger, der aufsaugt Y s und wenn ich das aufschraube, entsteht ein Vakuum, das alles aufsaugt. X s. Manche Dinge sind weder outputtish noch inputtish. Dinge, die sind beide sich herausstellt, sind Phantom : Sie haben absolut nichts mit den Substantiven zu tun, die sie beschreiben, in dem Sinne, dass man eine Funktion "coerce" definieren kann, die eine blaue X und macht eine blaue Y aber *ohne die Details der Typen zu kennen X ou Y ," die nicht einmal eine Funktion zwischen ihnen erfordern.

Also "Listen von __" ist outputtish, man kann eine X Y über eine Liste von X s, um eine Liste von Y s. In ähnlicher Weise ist "ein Paar aus einem String und einem __" outputtisch. In der Zwischenzeit ist "eine Funktion von __ zu sich selbst" weder outputtisch noch inputtisch, während "eine Zeichenkette und eine Liste von genau null __s" vielleicht der "Phantomfall" sein könnte.

Aber ja, das ist alles, was es an Funktoren in der Programmierung gibt, sie sind einfach Dinge, die abbildbar sind. Wenn etwas ein Funktor ist, ist es ein Funktor Einzigartig gibt es höchstens eine Möglichkeit, eine Funktion generisch auf eine Datenstruktur abzubilden.

Monaden

A Monade ist ein Funktor, der darüber hinaus sowohl

1. Universell anwendbar, bei jeder X kann ich eine blaue Farbe konstruieren. X ,
2. Kann wiederholt werden, ohne dass sich der Sinn wesentlich ändert. Also ein blau -blau X ist in gewissem Sinne dasselbe wie eine blaue X .

Das bedeutet also, dass es eine kanonische Funktion gibt, die jede blau -(Und wir fügen natürlich Gesetze hinzu, um alles vernünftig zu machen: Wenn eine der blauen Schichten aus der universellen Anwendung stammt, dann wollen wir diese universelle Anwendung einfach löschen; wenn wir außerdem ein blau-blau-blaues X zu einem blauen X abflachen, sollte es keinen Unterschied machen, ob wir die ersten beiden blau s zuerst oder die zweiten beiden zuerst).

Das erste Beispiel ist "a nullable __". Wenn ich Ihnen also einen nullable nullable int gebe, habe ich Ihnen in gewissem Sinne nicht viel mehr als einen nullable int gegeben. Oder "a list of lists of ints", wenn es nur darum geht, 0 oder mehr davon zu haben, dann funktioniert "a list of ints" ganz gut und der richtige Zusammenbruch ist die Verkettung aller Listen zu einer Superliste.

Monaden wurden in Haskell groß, weil Haskell einen Ansatz brauchte, um Dinge in der realen Welt zu tun, ohne seine mathematisch reine Welt zu verletzen, in der nichts wirklich passiert. Die Lösung war, eine Art verwässerte Form von Metaprogrammierung wo wir ein Adjektiv einführen, das "ein Programm, das einen __ erzeugt". Wie kann ich also das aktuelle Datum abrufen? Nun, Haskell kann das nicht direkt ohne unsafePerformIO aber Sie können damit das Programm beschreiben und zusammenstellen, das das aktuelle Datum erzeugt. In dieser Vision sollen Sie ein Programm beschreiben, das nichts produziert und "Main.main" heißt, und der Compiler soll Ihre Beschreibung nehmen und Ihnen dieses Programm als ausführbare Binärdatei aushändigen, die Sie ausführen können, wann immer Sie wollen.

Jedenfalls bringt "ein Programm, das ein Programm erzeugt, das einen int erzeugt" nicht viel mehr als "ein Programm, das einen int erzeugt", so dass sich dies als eine Monade herausstellt.

Freie Monaden

Im Gegensatz zu Funktoren sind Monaden keine eindeutigen Monaden. Es gibt nicht nur eine Monadeninstanz für einen bestimmten Funktor. Also zum Beispiel "ein Paar aus einem int und einem __", was macht man mit diesem int? Man könnte ihn addieren oder multiplizieren. Wenn man es zu einem nullbaren int macht, könnte man den minimalen nicht-nullen oder den maximalen nicht-nullen, oder den ganz linken nicht-nullen oder den ganz rechten nicht-nullen behalten.

Die freie Monade für einen gegebenen Funktor ist die "langweiligste" Konstruktion, sie ist einfach "A free blue X ist eine blaue n X für jede n \= 0, 1, 2, ...".

Sie ist universell, denn eine blaue X ist nur ein X . Und eine kostenlose blaue kostenlose blaue X ist eine blaue m blau n X die nur eine blaue m + n X . Es implementiert "collapse" also dadurch, dass es "collapse" überhaupt nicht implementiert, intern sind die Blauen beliebig verschachtelt.

Das bedeutet auch, dass Sie die Wahl der Monade auf einen späteren Zeitpunkt verschieben können, wenn Sie eine Funktion definieren, die eine blau -blau X zu einer blauen X und klappen Sie alle zu blau 0,1 X und dann eine weitere Funktion von X zu blau X gibt Ihnen blau 1 X durchgehend.