„Monade (Informatik)“ – Versionsunterschied

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Versionsgeschichte interaktiv durchsuchen
[gesichtete Version][ungesichtete Version]
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
Inhalt gelöscht Inhalt hinzugefügt
VisuellWikitext
K Änderungen von Carsten Milkau (Diskussion) auf die letzte Version von Trustable zurückgesetzt (HG)
Carsten Milkau (Diskussion | Beiträge)
119 Bearbeitungen
Änderung 146701636 von Regi51 rückgängig gemacht;
Zeile 1: Zeile 1:
In der [[Funktionale Programmierung|funktionalen Programmierung]] sind '''Monaden''' ein [[abstrakter Datentyp]]. Wesentliche Eigenschaft von Monaden ist die Fähigkeit der Übertragung von Werten und Berechnungen in einem „einfacheren” Typ zu Berechnungen in einem „höheren Typ”, der mittels eines [[Typkonstruktor]]s aus dem einfacheren Typ hervorgeht, sowie die Verknüpfung mehrerer solcher Übertragungen zu einer einzigen.

== Hintergrund ==
Der Hauptnutzen von Monaden ist es, [[Eingabe (Computer)|Ein-]] und [[Ausgabe (Computer)|Ausgabeoperationen]], zustandsbehaftete Berechnungen und Nichtdeterminismus (auch als Iteration über Kollektionen und ihren Kombinationen interpretierbar) und anderes auszudrücken. Dabei soll die Sprache keine [[Wirkung (Informatik)|Nebeneffekte]] einführen.<ref>[[Simon Peyton Jones|Simon L. Peyton Jones]], Philip Wadler: [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.2504 ''Imperative Functional Programming''.] Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston SC 1993</ref>

Das Konzept der [[Monade (Kategorientheorie)|Monade]] stammt aus der [[Kategorientheorie]], ein Zweig der Mathematik, welcher mathematische Objekte mittels [[Morphismus|Morphismen]] oder [[Funktor (Mathematik)|Funktoren]] vergleicht. Die Wörter [[Monade (Philosophie)|Monade]] oder aber auch [[Funktor (Logik)|Funktor]] sind wiederum von Konzepten in der Philosophie abgeleitet.

Die [[Programmiersprache]] [[Haskell (Programmiersprache)|Haskell]] ist eine funktionale Sprache, die Monaden stark einsetzt und versucht, monadische [[Komposition (Mathematik)|Kompositionen]] zu vereinfachen, beispielsweise durch [[Syntaktischer Zucker|syntaktischen Zucker]] (u.a. die sogenannte ''do''-Notation).

== Definitionen ==
Die übliche Formulierung einer Monade in der Programmierung hat folgende Komponenten:
# Ein ''Typkonstruktor'', der für jeden zugrunde liegenden Typ definiert, wie der korrespondierende Monadentyp zu erhalten ist. Der Name dieses Typkonstruktors wird dabei oft synonym mit der ganzen Monade verwendet. Wenn ''M'' der Name der Monade und ''t'' der Datentyp ist, so ist ''M&nbsp;t'' der korrespondierende monadische Typ.
# Eine ''Einheitsfunktion'', die einen Wert des zugrunde liegenden Typs auf den Wert des korrespondierenden Monadentyps abbildet. Das Ergebnis ist der "einfachste" Wert im korrespondierenden Typ, der sich aus dem Originalwert gewinnen lässt. In Haskell wird diese Funktion <tt>return</tt> genannt. Die Einheitsfunktion hat den polymorphen Typ ''t→M&nbsp;t''.
# mindestens eine weitere Operation (siehe dazu die folgenden Abschnitte), welche die Verknüpfung monadischer Operationen beschreibt.

Die folgenden Operationen sind typisch für Monaden und können für deren Definition Verwendung finden:
# Die Einheitsfunktion <syntaxhighlight lang="Haskell">return :: a -> m a</syntaxhighlight>
# Der ''bind''-Operator <syntaxhighlight lang="Haskell">(>>=) :: m a -> (a -> m b) -> m b</syntaxhighlight> erlaubt, einen monadischen Typ an eine Funktion zu übergeben, die nur den zugrundeliegenden Typ verwendet. Sein erstes Argument ist ein Wert von monadischem Typ und sein zweiter ist eine Funktion, die vom zugrunde liegenden Typ des ersten Arguments auf einen anderen monadischen Typ abbildet. Der Rückgabewert ist vom anderen Monadentyp.
# Der [[Kleisli-Kategorie|Kleisli-Operator]] <syntaxhighlight lang="Haskell">(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)</syntaxhighlight> realisiert eine Komposition (Hintereinanderausführung) für Funktionen, die einen monadischen Typ zurückgeben, aber nur den jeweils zugrundeliegenden Typ verwenden.
# Der [[Funktor]] <syntaxhighlight lang="Haskell">fmap :: (a -> b) -> m a -> m b </syntaxhighlight> erlaubt, einen monadischen Typ an eine Funktion zu übergeben, die nur den zugrundeliegenden Typ verwendet. Sein erstes Argument ist eine Funktion, die vom zugrunde liegenden Typ des ersten Arguments auf einen anderen, meist nicht monadischen, Typ abbildet. Sein zweites Argument ist ein Wert von monadischem Typ. Der Rückgabewert ist vom Monadentyp des zugrunde liegenden Typs des Rückgabewertes der Funktion.
# Eine [[natürliche Transformation]] <syntaxhighlight lang="Haskell">join :: m (m a) -> m a</syntaxhighlight> welche ein „Abflachen” des monadischen Typs um eine Verschachtelungsebene erlaubt.
(dabei steht <code>m</code> für den Typkonstruktor)

Diese Operationen müssen folgenden Gesetzen gehorchen:

# "Assoziativität" von <code>>>=</code><syntaxhighlight lang="Haskell"> (ma >>= f) >>= g == ma >>= ( \a -> ((f a) >>= g) )</syntaxhighlight>
# Assoziativität von <code>>=></code><syntaxhighlight lang="Haskell"> (f >=> g) >=> h == f >=> (g >=> h)</syntaxhighlight>
# Kompatibilität von Verkettung und <code>fmap</code><syntaxhighlight lang="Haskell"> fmap (f . g) == (fmap f) . (fmap g)</syntaxhighlight>
# <code>join</code> ist eine natürliche Transformation von <code>fmap . fmap</code> auf <code>fmap</code><syntaxhighlight lang="Haskell"> (fmap f) . join == join . ((fmap . fmap) f)</syntaxhighlight>
# Kommutativität von <code>fmap</code> und <code>join</code><syntaxhighlight lang="Haskell"> join . join == join . (fmap join) -- das zweite join hat den typ m (m (m a)) -> m (m a)</syntaxhighlight>
# <code>return</code> ist eine natürliche Transformation von <code>id</code> auf <code>fmap</code><syntaxhighlight lang="Haskell"> (fmap f) . return == return . f</syntaxhighlight>
# Neutralität von <code>return</code> unter <code>>>=</code> <syntaxhighlight lang="Haskell" line>
ma >>= return == ma
(return a) >>= f == f a
</syntaxhighlight>
# Neutralität von <code>return</code> unter <code>>=></code><syntaxhighlight lang="Haskell"> f >=> return == return >=> f == f</syntaxhighlight>
# Neutralität von <code>return</code> unter <code>>=></code>, in <code>fmap</code>/<code>join</code>-Notation<syntaxhighlight lang="Haskell"> join . return == join . (fmap return) == id</syntaxhighlight>

=== In Anlehnung an Haskell ===
In Haskell wird eine Monade über die Operationen <code>return</code> und <code>(>>=)</code> definiert:
<syntaxhighlight lang="Haskell">
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
</syntaxhighlight>

Die anderen Operationen lassen sich dann über diese beiden definieren:
<syntaxhighlight lang="Haskell">

(f >=> g) a = f a >>= g
(fmap f) ma = ma >>= (return . f)
join mma = mma >>= id
</syntaxhighlight>

=== Über den Kleisli-Operator ===
Eine Monade lässt sich auch über ihre [[Kleisli-Kategorie]] definieren:
<syntaxhighlight lang="Haskell">
class Monad m where
return :: a -> m a
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
</syntaxhighlight>

Die übrigen Operationen ergeben sich dann wie folgt:
<syntaxhighlight lang="Haskell">
ma >>= f = (id >=> f) ma
fmap f = id >=> (return . f)
join = id >=> id
</syntaxhighlight>

=== Analog zur Kategorientheorie ===
In der Kategorientheorie wird eine Monade üblicherweise über einen [[Funktor]] <code>fmap</code> sowie zwei [[Natürliche Transformation|natürliche Transformationen]] <code>return</code> und <code>join</code> definiert:
<syntaxhighlight lang="Haskell">
class Monad m where
fmap :: (a -> b) -> m a -> m b
return :: a -> m a
join :: m (m a) -> m a
</syntaxhighlight>

Die übrigen Operationen lassen sich dann wie folgt realisieren:
<syntaxhighlight lang="Haskell">
ma >>= f = (join . (fmap f)) ma
f >=> g = join . (fmap g) . f
</syntaxhighlight>

== Beziehungen zu anderen Typklassen ==
Jede Monade ist auch ein [[Applikativer Funktor]] und mithin auch ein <!-- pointed --> [[Kategorientheorie#Funktor|Funktor]]. Umgekehrt gilt das nicht.
Diese Eigenschaft findet sich aus historischen Gründen nicht explizit in Haskells Standardbibliothek, der [[Glasgow Haskell Compiler]] wird dies jedoch mit Version 7.10 einführen.<ref>http://www.haskell.org/ghc/docs/7.8.1/html/users_guide/release-7-8-1.html</ref>

Besonders deutlich wird diese Beziehung auch, vergleicht man die kategorientheoretische Definition mit der Funktor-Klasse in Haskell:
<syntaxhighlight lang="Haskell">
class Functor f where
fmap :: (a -> b) -> f a -> f b
</syntaxhighlight>
Dabei muss <code>fmap</code> ebenfalls die Kompatibilitätsbedingung mit der Komposition (<code>.</code>) erfüllen.

== Beispiele ==
=== Behälter ===
{{Hauptartikel|Container (Informatik)}}

Container wie [[Liste (Datenstruktur)|Liste]]n, [[Menge (Mathematik)|Menge]]n, [[Multimenge]]n stellen Monaden dar, deren Bindeoperation die übergebene Funktion auf alle Elemente anwendet und die dabei erhaltenen Ergebnisse vereinigt. Die Vereinigungsoperation ist dabei jeweils Listenverkettung, Vereinigungsmengenbildung bzw. Bildung der Multimengenvereinigung. Die Einheitsfunktion ergibt Einermengen und -listen.

Hier als Beispiel die Monade für verkettete Listen. Das Konzept der Instanz für Listen ist es, eine Liste einzulesen, dann jedes Element an die Funktion zu übergeben und die Ergebnisse zu verbinden. Hier eine Beispielimplementation in Haskell:

<syntaxhighlight lang="haskell">
-- Hier nochmal zur Erinnerung, der Listentyp ist folgendermaßen definiert:
data [a] = [] | a:[a]
-- Als syntaktischer Zucker kann [a,b,c] für a:b:c:[] verwendet werden.

instance Monad [] where
--return :: a -> [a]
return a = [a] -- Per Definition eine Liste mit einem Element zurückgeben
--(>>=) :: [a] -> (a -> [b]) -> [b]
liste >>= f = concat zwischenergebnis where -- Die einzelnen Teillisten zusammenfügen
zwischenergebnis :: [[b]]
zwischenergebnis = map f liste -- Die Funktion auf die Liste abbilden
</syntaxhighlight>

=== Vektoren und lineare Abbildungen ===
Der Typkonstruktor bildet hier einen Typ <math>T</math> auf einen [[Vektorraum]] <math>V(T)</math> ab, bei dem <math>T</math> als (Namensgeber für eine) [[Basis (Vektorraum)|Basis]] dient, und dessen Elemente beispielsweise als Funktionen <math>T\to\mathbb R</math> modelliert werden. Die Bindeoperation hat den Typ <math>V(T) \to (T\to V(U)) \to V(U)</math>. Durch Vertauschen der Argumente erhält man den Typ <math>(T\to V(U)) \to (V(T) \to V(U))</math>, an dem man die Semantik erkennen kann: die gegebene Funktion, die auf den Basiselementen definiert ist, wird zu einer vollen linearen Abbildung erweitert. Die Einheitsfunktion bildet das Basiselement (welches in dieser Modellierung noch ''kein'' „richtiger“ Vektor ist) auf den entsprechenden Basisvektor ab.

=== State, I/O ===
Bei zustandsbehafteten Aktionen dient die Bindeoperation der Verwirklichung der Hintereinanderausführung. Die Einheitsfunktion erstellt eine Aktion, die ''nichts tut'' und ein festes Resultat zurückgibt.

Das Konzept ist dabei recht natürlich. Wenn man in einer rein funktionalen Programmiersprache einen veränderlichen Status übergeben will, dann macht man das in der Regel auf folgende Weise, hier am Beispiel einer Zählerfunktion:

<syntaxhighlight lang="haskell">
-- Den Zähler hochzählen und den alten Zähler zurückgeben
hochzählen :: Int -> Int -> (Int,Int)
hochzählen schrittweite zählerstand = (zählerstand,neuerZählerstand) where ...
</syntaxhighlight>

Das Grundprinzip ist, dass man als Parameter den alten Status anhängt und den neuen mit dem Rückgabewert zusammen zurückgibt. Um sich Arbeit zu ersparen, kann man dieses Muster einfach in einen neuen Typen verpacken, der Parameter <code>s</code> des Types ist der Typ des Status, <code>a</code> ist der Parameter des Rückgabewertes:

<syntaxhighlight lang="haskell">
data Status s a = Status (s -> (a,s))

-- Beispiel:
hochzählen :: Int -> Status Int Int
hochzählen schrittweite = Status $ \zählerstand -> (zählerstand,zählerstand+schrittweite)
</syntaxhighlight>

Was man jetzt noch braucht, sind ein paar Funktionen, die den Status manipulieren können. Hier zum Beispiel eine Funktion, die den Status auf einen neuen setzt, und eine, die ihn ausliest:

<syntaxhighlight lang="haskell">
setStatus :: s -> Status s ()
setStatus s = Status $ \_ -> ((),s) -- Der alte Status wird ignoriert und durch den neuen ersetzt. Rückgabewert, da unnötig, ().

getStatus :: Status s s
getStatus = Status $ \s -> (s,s) -- Dupliziere den Status in den Rückgabewert.
</syntaxhighlight>

Dies ist schon fast alles, was nötig ist. Das einzige, was noch fehlt, ist die Möglichkeit mehrere statusverändernde Aktionen zu kombinieren, hier sind Monaden das Werkzeug der Wahl:

<syntaxhighlight lang="haskell">
instance Monad (Status s) where -- Die Typvariable s ist irrelevant für die Definition
--return :: a -> Status s a
return a = Status $ \s -> (a,s) -- Status bleibt unverändert
--(>>=) :: Status s a -> (a -> Status s b) -> Status s b
(Status aktion1) >>= f = Status $ \s -> aktion2 zwischenstatus where -- Status aus aktion1 in aktion2 einspeisen.
(rückgabe1,zwischenstatus) = aktion1 s -- aktion1 ausführen
Status aktion2 = f rückgabe1 -- Rückgabewert aus aktion1 in f einspeisen
</syntaxhighlight>

Mit diesen Funktionen und dem syntaktischen Zucker der do-Notation (der die monadischen Operationen vor uns versteckt) lässt sich das Beispiel dann folgendermaßen formulieren:

<syntaxhighlight lang="haskell">
hochzählen :: Int -> Status (Int,Int)
hochzählen schrittweite = do zählerstand <- getStatus -- Zählerstand ermitteln
setStatus (zählerstand + schrittweite) -- Zähler setzen
return zählerstand -- alten Zählerstand zurückgeben

-- Hier entzuckert
hochzählen schrittweite = getStatus >>= \zählerstand ->
setStatus (zählerstand + schrittweite) >>= \_ ->
return zählerstand
</syntaxhighlight>

<!-- gut wären noch Reader, Writer, Error, Continuation --> <!-- Nur zu! Soll ich alles alleine machen? (Aber *zu* viele Beispiele wären wahrscheinlich auch nicht gut) :) -->

== Andere Sprachen ==
LINQ-Abfrageausdrücke in [[C#]] sind direkt inspiriert von Haskells <code>do</code>-Notation.<ref>{{Literatur|Autor=Erik Meijer|Titel=The World According to LINQ|Online=http://queue.acm.org/detail.cfm?id=2024658}}</ref> Ein Analogon zur Typklasse <code>Monad</code> ist in C# jedoch nicht ausdrückbar; der Compiler übersetzt LINQ-Abfrage-Ausdrücke blind in Aufrufe von Methoden mit festgelegten Namen. Diese sind <code>Select</code> und <code>SelectMany</code>. Auch benutzerdefinierte Klassen können also mittels LINQ-Abfrageausdrücken angesprochen werden, wenn diese Methoden mit entsprechenden Namen zur Verfügung stellen.
Dieselbe Strategie verfolgt [[Scala (Programmiersprache)|Scala]] im Fall von <code>for</code>-Comprehensions.<ref>http://www.scala-lang.org/files/archive/spec/2.11/06-expressions.html</ref> Die Methoden heißen da <code>map</code> und <code>flatMap</code>.
In der Standardbibliothek von [[Java 8]] sind mindestens zwei Monaden vorhanden, die derselben Namenskonvention gehorchen: die Schnittstellen <code>Optional</code> und <code>Stream</code> definieren Methoden namens <code>map</code>, <code>flatMap</code> und <code>of</code>.

In allen drei Sprachen ist es nicht möglich, als Benutzer Funktionalität zu definieren, die mit allen Monaden umgehen kann, wie etwa Haskells
<code>sequence :: forall m a. Monad m => [m a] -> m [a]</code>. <!-- kann sein, dass sowas in C++ geht, da die Templaterei praktisch nicht getypt ist (also ohne Instanziierung kein Check von irgendwas) -->

== Weblinks ==
* [http://homepages.inf.ed.ac.uk/wadler/topics/monads.html Papers von Philip Wadler]
* [http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html You Could Have Invented Monads! (And Maybe You Already Have.)]
* [http://www.haskell.org/haskellwiki/What_a_Monad_is_not What a Monad is not]
* [http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf Brent Yorgey: ''Typeclassopedia''] (PDF; 722&nbsp;kB) in: ''The Monad.Reader Issue'' 13

=== Monaden in anderen Programmiersprachen ===
; [[Groovy|Groovy]]
* [http://groovyconsole.appspot.com/script/206001 Monads in Groovy]
; [[Ruby (Programmiersprache)|Ruby]]
* [http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html Monads in Ruby]
; [[Python (Programmiersprache)|Python]]
* [http://www.valuedlessons.com/2008/01/monads-in-python-with-nice-syntax.html Monads in Python]
; [[Scala (Programmiersprache)|Scala]]
* [http://lamp.epfl.ch/~emir/bqbase/2005/01/20/monad.html Monads in Scala]
; [[Clojure]]
* [https://github.com/khinsen/monads-in-clojure/blob/master/PART1.md Monads in Clojure]
; [[JavaScript]]
* [http://labs.mudynamics.com/2009/05/13/monadic-parser-in-javascript/ Monads in JavaScript]
; [[CSharp|C#]]
* {{internetquelle|url=http://blogs.msdn.com/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx|titel=The Marvels of Monads|zugriff=2013-03-21|hrsg=[[MSDN]] Blogs, [[Microsoft]]|autor=Wes Dyer|datum=2008-01-10|werk=Yet Another Language Geek}}
* {{internetquelle|url=http://mikehadlow.blogspot.co.at/2011/01/monads-in-c1-introduction.html|titel=Monads in C#|werk=Code Rant|autor=Mike Hadlow|datum=2011-01-09|zugriff=2013-03-21}}
* [[LINQ]]
* {{internetquelle|url=https://github.com/Muraad/Monad-CSharp|titel=Monads-CSharp|werk=GitHub|autor=Muraad Nofal |datum=2014-03-10 |zugriff=2013-03-21}}

== Einzelnachweise ==
<references />

[[Kategorie:Programmiersprache als Thema]]
[[Kategorie:Haskell (Programmiersprache)]]

Version vom 5. Oktober 2015, 12:26 Uhr

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Monade_(Informatik)&oldid=146701646“