Natürliches Vorkommen von Monaden, die den kategorietheoretischen Rahmen nutzen

18

Ein Vortrag von Henning Kerstan ("Spurensemantik für probabilistische Übergangssysteme") hat mich heute erstmals mit Kategorietheorie konfrontiert. Er hat einen theoretischen Rahmen für die allgemeine Beschreibung probablistischer Übergangssysteme und ihres Verhaltens geschaffen, dh mit unzähligen unendlichen Zustandssätzen und unterschiedlichen Vorstellungen von Spuren. Zu diesem Zweck durchläuft er mehrere Abstraktionsebenen, um schließlich den Begriff der Monaden zu entwickeln, den er mit der Maßtheorie kombiniert, um das Modell zu erstellen, das er benötigt.

Am Ende brauchte er 45 Minuten, um (ungefähr) ein Framework zu erstellen, um ein Konzept zu beschreiben, das er anfangs in 5 Minuten erklärt hatte. Ich schätze die Schönheit des Ansatzes (er verallgemeinert sich gut über verschiedene Vorstellungen von Spuren), aber er scheint mir trotzdem eine merkwürdige Balance zu sein.

Ich kämpfe darum zu sehen, was eine Monade wirklich ist und wie allgemein ein Konzept in Anwendungen nützlich sein kann (sowohl in der Theorie als auch in der Praxis). Lohnt sich der Aufwand wirklich ergebnisseitig?

Deshalb diese Frage:

Gibt es natürliche Probleme (im Sinne von CS), bei denen der abstrakte Begriff der Monaden angewendet werden kann und hilft (oder sogar hilft), gewünschte Ergebnisse zu erzielen (überhaupt oder besser als ohne)?

Raphael
quelle
2
Codierungszustände in einer rein funktionalen Programmiersprache? Ist das ein natürliches CS-Problem?
Stéphane Gimenez
2
Das allgemeinere Problem des Umgangs mit Effekten in funktionalen Sprachen ist das Beispiel, das ich am häufigsten gesehen habe: Für die Theorie sind die Monaden für Effekte sexy und für die Praxis ist Haskells IO-Monade sehr praktisch.
Jmad
Und was wären die Vorteile gegenüber der klassischen, relativ leichten Semantik? Sind FP-Monaden überhaupt dasselbe wie in der Kategorietheorie? Fragen über Fragen.
Raphael
Siehe diese Frage auf cstheory.SE für eine allgemeinere Frage nach Verwendung der Kategorietheorie.
Raphael

Antworten:

6

Die Frage, ob das Auftreten einer Monade natürlich ist, ist vergleichbar mit der Frage, ob eine Gruppe (im Sinne der Gruppentheorie) natürlich ist. Sobald Sie etwas formalisiert haben, in diesem Fall als Endofunktor, erfüllt es entweder die Axiome, eine Monade zu sein, oder nicht. Wenn es die Axiome erfüllt, bekommt man eine Menge technischer Maschinen gratis.

Moggis Aufsatz " Begriffe der Berechnung und Monaden" besiegelt so ziemlich das Geschäft: Monaden sind unglaublich natürlich und nützlich, um Recheneffekte auf einheitliche Weise zu beschreiben. Wadlerund andere übersetzten diese Begriffe, um Recheneffekte in funktionalen Programmiersprachen zu behandeln, indem sie die Verbindung verwendeten, dass ein Funktor ein Datentypkonstruktor ist. Dies fügt das i-Tüpfelchen hinzu. FP-Monaden ermöglichen die Behandlung von Computereffekten wie IO, die ohne sie äußerst unnatürlich wären. Monaden haben verwandte nützliche Begriffe wie Pfeile und Redewendungen inspiriert, die auch zur Strukturierung von Funktionsprogrammen sehr nützlich sind. Siehe den Wadler-Link für Referenzen. FP-Monaden sind dasselbe wie kategorietheoretische Monaden in dem Sinne, dass für eine FP-Monade die gleichen Gleichungen gelten müssen, auf die sich der Compiler verlässt. Im Allgemeinen unterscheidet sich die Darstellung der Monade (verschiedene, aber äquivalente Operationen und Gleichungen), dies ist jedoch ein oberflächlicher Unterschied.

Ein großer Teil der Arbeit von Bart Jacobs , um nur ein Beispiel zu nennen, verwendet Monaden. Viele Arbeiten stammen aus der Kohlegebra, einer allgemeinen Systemtheorie. Einer von Jacobs (vielen) Beiträgen in diesem Bereich ist die Entwicklung eines allgemeinen Begriffs der Spurensemantik für Systeme (als Kohlegebren bezeichnet), die auf Monaden basieren. Man könnte argumentieren, dass der Begriff der Trace-Semantik natürlich ist: Was ist die Semantik eines Systems? Die Liste der Aktionen, die beobachtet werden können!

Eine Möglichkeit, Monaden zu verstehen, besteht darin, zuerst in Haskell mit Monaden zu programmieren. Dann finden Sie eines der vielen guten Tutorials (über Google). Beginnen Sie mit der Programmierung und gehen Sie dann zur theoretischen Seite über, wobei Sie mit einer grundlegenden Kategorietheorie beginnen.

Dave Clarke
quelle