Die Listen-Monade ist die Monade, die auf Listen als Datentyp aufbaut. Ihr Kontext ist „mehrere mögliche Werte“: Eine Liste repräsentiert die Menge aller möglichen Ergebnisse einer Berechnung. Die Listen-Monade ist damit das Standardbeispiel für Nichtdeterminismus in der funktionalen Programmierung.
bind als concatMap
Der bind-Operator der Listen-Monade entspricht genau concatMap (in anderen Sprachen flatMap oder SelectMany):
xs >>= f = concat (map f xs)Jede Funktion f liefert für jedes Element eine eigene Liste; die Teillisten werden zu einer einzigen Liste konkateniert. Während map eine Funktion auf jedes Element anwendet und eine Liste gleicher Länge liefert, kann concatMap pro Element beliebig viele Ergebnisse erzeugen — oder auch keins.
Beispiel: Alle Kombinationen
Ein klassisches Beispiel sind alle Paare aus zwei Listen:
[(x, y) | x <- [1, 2, 3], y <- [1, 2, 3]]Diese List-Comprehension ist in Haskell nur syntaktischer Zucker für die Listen-Monade: Jede Generator-Zeile entspricht einem bind, jede Bedingung einem Filter. Dieselbe Ausdruckskraft steckt in Pythons List-Comprehensions und in der flatMap-Kombination von JavaScript.
Anwendungen
Die Listen-Monade eignet sich für Backtracking und Suche: Man erzeugt systematisch Kandidaten und filtert sie mit Bedingungen. Ein Sudoku-Löser lässt sich damit als kompakte Folge von „erzeuge Kandidat, prüfe Bedingung“-Schritten schreiben. Auch Kombinatorik-Aufgaben, etwa alle Permutationen oder Teilmengen, sind natürliche Anwendungen.
Einordnung
Listen sind zugleich ein Funktor und ein Applicative-Functor. Als Monade sind sie ein Spezialfall der allgemeinen Monade; die Maybe-Monade modelliert dagegen genau einen möglichen Wert, der fehlen kann — die Listen-Monade modelliert viele Werte gleichzeitig.
Verwandte Grundlagen: Funktor, Applicative-Functor, Maybe-Monade, Backtracking, Funktionale Programmierung, Haskell-Befehle, Python-Befehle.