Warum brauchen wir Monaden?

Question

In meiner bescheidenen Meinung versuchen die Antworten auf die berühmte Frage "Was ist ein Monoid?", insbesondere die am meisten bewerteten, zu erklären, was ein Monoid ist, ohne klar zu erklären, warum Monaden wirklich notwendig sind. Können sie als Lösung für ein Problem erklärt werden?

Answer 1

Warum brauchen wir Monaden?

1. Wir wollen nur Funktionen verwenden (schließlich funktionales Programmieren (FP)).

2. Dann haben wir ein erstes großes Problem. Das ist ein Programm:

   f(x) = 2 * x

   g(x,y) = x / y

   Wie können wir sagen, welches zuerst ausgeführt werden soll? Wie können wir eine geordnete Folge von Funktionen (d.h. ein Programm) bilden, nur unter Verwendung von Funktionen?

   Lösung: Funktionen komponieren. Wenn du zuerst g und dann f möchtest, schreibe einfach f(g(x,y)). Auf diese Weise ist "das Programm" auch eine Funktion: main = f(g(x,y)). OK, aber ...

3. Weitere Probleme: Manche Funktionen können fehlschlagen (z.B. g(2,0), durch 0 teilen). In FP haben wir keine "Ausnahmen" (eine Ausnahme ist keine Funktion). Wie lösen wir das?

   Lösung: Lassen wir Funktionen zwei Arten von Dingen zurückgeben: Anstatt g : Real,Real -> Real (Funktion von zwei reellen Zahlen in eine reelle Zahl), erlauben wir g : Real,Real -> Real | Nothing (Funktion von zwei reellen Zahlen in (reelle Zahl oder nichts)).

4. Aber Funktionen sollten (um einfacher zu sein) nur eine Sache zurückgeben.

   Lösung: Lassen wir einen neuen Datentyp erstellen, der zurückgegeben wird, ein "Boxing-Typ", der möglicherweise eine reelle Zahl umschließt oder einfach nichts ist. Daher können wir haben g : Real,Real -> Maybe Real. OK, aber ...

5. Was passiert jetzt mit f(g(x,y))? f ist nicht bereit, ein Maybe Real zu verarbeiten. Und wir möchten nicht jede Funktion ändern, die wir mit g verbinden könnten, um ein Maybe Real zu verarbeiten.

   Lösung: Lassen wir eine spezielle Funktion haben, um Funktionen zu "verbinden"/"zusammensetzen"/"verknüpfen". Auf diese Weise können wir hinter den Kulissen die Ausgabe einer Funktion anpassen, um die folgende zu versorgen.

   In unserem Fall: g >>= f (verbinden/komponieren g mit f). Wir möchten, dass >>= die Ausgabe von g erhält, sie überprüft und bei Bedarf einfach f nicht aufruft und Nothing zurückgibt; oder im Gegenteil, die eingepackte Real extrahiert und f damit versorgt. (Dieser Algorithmus ist einfach die Implementierung von >>= für den Maybe Typ). Beachte auch, dass >>= nur einmal pro "Boxing-Typ" geschrieben werden muss (verschiedene Box, unterschiedlicher Anpassungsalgorithmus).

6. Viele andere Probleme entstehen, die mit diesemselben Muster gelöst werden können: 1. Verwende eine "Box", um verschiedene Bedeutungen/Werte zu codieren/speichern, und habe Funktionen wie g, die diese "eingepackten Werte" zurückgeben. 2. Besitze einen Komponisten/Verknüpfer g >>= f, um dabei zu helfen, das Ausgabedaten von g mit dem Eingabedaten von f zu verbinden, damit wir überhaupt keine f ändern müssen.

7. Bemerkenswerte Probleme, die mit dieser Technik gelöst werden können, sind:

   • einen globalen Zustand zu haben, den jede Funktion in der Reihe von Funktionen ("das Programm") teilen kann: Lösung StateMonad.

   • Wir mögen keine "unreinen Funktionen": Funktionen, die für den gleichen Eingang unterschiedliche Ausgaben liefern. Daher markieren wir diese Funktionen, so dass sie ein markiertes/eingepacktes Wert zurückgeben: IO Monade.

Total glücklich!

Answer 2

Die Antwort ist natürlich "Wir tun es nicht". Wie bei allen Abstraktionen ist es nicht notwendig.

Haskell benötigt keine Monad-Abstraktion. Sie ist nicht erforderlich, um Ein-/Ausgabe in einer reinen Sprache durchzuführen. Der IO-Typ kümmert sich darum ganz alleine. Die bereits vorhandene monadische Desugaring von do-Blöcken könnte durch Desugaring zu bindIO, returnIO und failIOGHC.Base ersetzt werden. (Es handelt sich um ein nicht dokumentiertes Modul auf hackage, also muss ich auf seine Quelle für die Dokumentation verweisen.) Also nein, die Monad-Abstraktion wird nicht benötigt.

Also, wenn es nicht benötigt wird, warum existiert sie dann? Weil festgestellt wurde, dass viele Berechnungsmuster monadische Strukturen bilden. Die Abstraktion einer Struktur ermöglicht es, Code zu schreiben, der über alle Instanzen dieser Struktur hinweg funktioniert. Um es präziser auszudrücken - Code-Wiederverwendung.

In funktionalen Sprachen wurde das leistungsstärkste Werkzeug zur Code-Wiederverwendung in der Komposition von Funktionen gefunden. Der gute alte (.) :: (b -> c) -> (a -> b) -> (a -> c) Operator ist äußerst mächtig. Er vereinfacht es, winzige Funktionen zu schreiben und ohne minimalen syntaktischen oder semantischen Aufwand miteinander zu verbinden.

Aber es gibt Fälle, in denen die Typen nicht ganz richtig funktionieren. Was macht man, wenn man foo :: (b -> Maybe c) und bar :: (a -> Maybe b) hat? foo. bar passt nicht, weil b und Maybe b nicht der gleiche Typ sind.

Aber... es ist fast richtig. Man möchte nur ein wenig Spielraum haben. Man möchte Maybe bb. Es ist eine schlechte Idee, sie einfach direkt als den gleichen Typ zu behandeln, jedoch. Das entspricht mehr oder weniger dem gleichen wie Null-Zeiger, den Tony Hoare berühmt als den Milliarden-Dollar-Fehler bezeichnete. Also, wenn man sie nicht als den gleichen Typ behandeln kann, vielleicht findet man einen Weg, um den Kompositionsmechanismus, den (.) zur Verfügung stellt, zu erweitern.

In diesem Fall ist es wichtig, die Theorie hinter (.) wirklich zu untersuchen. Glücklicherweise hat das bereits jemand für uns getan. Es stellt sich heraus, dass die Kombination von (.) und id eine mathematische Konstruktion bildet, die als Kategorie bekannt ist. Aber es gibt andere Möglichkeiten, Kategorien zu bilden. Eine Kleisli-Kategorie erlaubt es beispielsweise, die zu komponierenden Objekte ein wenig zu erweitern. Eine Kleisli-Kategorie für Maybe würde aus (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c) und id :: a -> Maybe a bestehen. Das heißt, die Objekte in der Kategorie erweitern das (->) mit einem Maybe, so dass aus (a -> b) (a -> Maybe b) wird.

Und plötzlich haben wir die Leistung der Komposition auf Dinge ausgeweitet, auf die die traditionelle (.) Operation nicht funktioniert. Das ist eine Quelle für neue abstrakte Leistungsfähigkeit. Kleisli-Kategorien funktionieren mit mehr Typen als nur Maybe. Sie funktionieren mit jedem Typ, der eine ordentliche Kategorie zusammenstellen kann, unter Einhaltung der Kategoriegesetze.

1. Linke Identität: id . f = f
2. Rechte Identität: f . id = f
3. Assoziativität: f . (g . h) = (f . g) . h

Solange man beweisen kann, dass der Typ diese drei Gesetze einhält, kann man ihn in eine Kleisli-Kategorie umwandeln. Und was ist daran so besonders? Nun, es stellt sich heraus, dass Monaden genau dasselbe sind wie Kleisli-Kategorien. Das return der Monad ist dasselbe wie Kleisli-id. (>>=) der Monad ist nicht identisch mit Kleisli-(.), aber es stellt sich heraus, dass es sehr einfach ist, diese jeweils durch die andere zu schreiben. Und die Kategoriegesetze sind dieselben wie die Monadengesetze, wenn man sie über den Unterschied zwischen (>>=) und (.) übersetzt.

Also, warum der ganze Aufwand? Warum eine Monad-Abstraktion in der Sprache haben? Wie bereits angedeutet, ermöglicht sie die Code-Wiederverwendung. Sie ermöglicht sogar die Code-Wiederverwendung entlang zwei unterschiedlicher Dimensionen.

Die erste Dimension der Code-Wiederverwendung ergibt sich direkt aus der Präsenz der Abstraktion. Man kann Code schreiben, der über alle Instanzen der Abstraktion funktioniert. Es gibt das gesamte monad-loops-Paket, das aus Schleifen besteht, die mit jeder Instanz von Monad funktionieren.

Die zweite Dimension ist indirekt, sie ergibt sich jedoch aus der Existenz von Komposition. Wenn die Komposition einfach ist, ist es natürlich, Code in kleinen, wiederverwendbaren Stücken zu schreiben. Das ist dieselbe Art und Weise, wie der Operator (.) für Funktionen das Schreiben von kleinen, wiederverwendbaren Funktionen fördert.

Warum also existiert die Abstraktion? Weil sie sich als ein Werkzeug erwiesen hat, das mehr Komposition im Code ermöglicht, wodurch wieder verwendbarer Code geschaffen wird und die Schaffung von mehr wiederverwendbarem Code gefördert wird. Code-Wiederverwendung ist eines der großen Ziele des Programmierens. Die Monad-Abstraktion existiert, weil sie uns ein wenig näher an dieses große Ziel bringt.

Answer 3

Benjamin Pierce sagte in TAPL

Ein Typsystem kann als eine Art statische Approximation des Laufzeitverhaltens der Terme in einem Programm betrachtet werden.

Deshalb ist eine Sprache, die mit einem leistungsfähigen Typsystem ausgestattet ist, streng genommen ausdrucksstärker als eine schlecht typisierte Sprache. Man kann auch über Monaden in gleicher Weise nachdenken.

Wie @Carl und sigfpe betonen, können Sie einem Datentyp alle gewünschten Operationen ohne Rückgriff auf Monaden, Typklassen oder andere abstrakte Dinge ausstatten. Monaden ermöglichen es Ihnen jedoch nicht nur, wiederverwendbaren Code zu schreiben, sondern auch alle überflüssigen Details abstrahieren.

Zum Beispiel, wenn wir eine Liste filtern möchten. Der einfachste Weg ist die Verwendung der filter-Funktion: filter (> 3) [1..10], was gleich [4,5,6,7,8,9,10] ist.

Eine etwas kompliziertere Version von filter, die auch einen Akkumulator von links nach rechts übergibt, ist

swap (x, y) = (y, x)
(.*) = (.) . (.)

filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b]
filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

Um alle i zu erhalten, für die i <= 10, sum [1..i] > 4, sum [1..i] < 25 ist, können wir schreiben

filterAccum (\a x -> let a' = a + x in (a' > 4 && a' < 25, a')) 0 [1..10]

was gleich [3,4,5,6] ist.

Oder wir können die nub-Funktion neu definieren, die doppelte Elemente aus einer Liste entfernt, in Bezug auf filterAccum:

nub' = filterAccum (\a x -> (x `notElem` a, x:a)) []

nub' [1,2,4,5,4,3,1,8,9,4] ist gleich [1,2,4,5,3,8,9]. Hier wird eine Liste als Akkumulator übergeben. Der Code funktioniert, weil es möglich ist, die Listen-Monade zu verlassen, damit die gesamte Berechnung rein bleibt (notElem verwendet nicht wirklich >>=, aber es könnte). Es ist jedoch nicht möglich, die IO-Monade sicher zu verlassen (d.h. Sie können keine IO-Aktion ausführen und einen reinen Wert zurückgeben - der Wert wird immer in der IO-Monade verpackt sein). Ein weiteres Beispiel sind veränderbare Arrays: Nachdem Sie die ST-Monade verlassen haben, in der ein veränderbares Array lebt, können Sie das Array nicht mehr in konstanter Zeit aktualisieren. Daher benötigen wir ein monadisches Filtern aus dem Control.Monad-Modul:

filterM          :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM _ []     =  return []
filterM p (x:xs) =  do
   flg <- p x
   ys  <- filterM p xs
   return (if flg then x:ys else ys)

filterM führt eine monadische Aktion für alle Elemente einer Liste aus und liefert Elemente, für die die monadische Aktion True zurückgibt.

Ein Filterbeispiel mit einem Array:

nub' xs = runST $ do
        arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool)
        let p i = readArray arr i <* writeArray arr i False
        filterM p xs

main = print $ nub' [1,2,4,5,4,3,1,8,9,4]

druckt wie erwartet [1,2,4,5,3,8,9] aus.

Und eine Version mit der IO-Monade, die fragt, welche Elemente zurückgegeben werden sollen:

main = filterM p [1,2,4,5] >>= print where
    p i = putStrLn ("return " ++ show i ++ "?") *> readLn

Zum Beispiel

return 1? -- Ausgabe
True      -- Eingabe
return 2?
False
return 4?
False
return 5?
True
[1,5]     -- Ausgabe

Und als letzte Illustration kann filterAccum in Bezug auf filterM definiert werden:

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

mit der darunter liegenden Verwendung der StateT-Monade, die nur eine gewöhnliche Datentyp ist.

Dieses Beispiel zeigt, dass Monaden es nicht nur ermöglichen, den Berechnungskontext zu abstrahieren und sauberen wiederverwendbaren Code zu schreiben (aufgrund der Komponierbarkeit von Monaden, wie @Carl erklärt), sondern auch benutzerdefinierte Datentypen und eingebaute Primitive einheitlich zu behandeln.

Answer 4

Ich denke nicht, dass IO als besonders herausragender Monade angesehen werden sollte, aber für Anfänger ist es sicherlich eine der erstaunlicheren, daher werde ich es für meine Erklärung verwenden.

Naiv ein IO-System für Haskell aufbauen

Das einfachste denkbare IO-System für eine rein funktionale Sprache (und tatsächlich dasjenige, mit dem Haskell begonnen hat) ist dieses:

main :: String -> String
main _ = "Hallo Welt"

Mit Laziness ist diese einfache Signatur ausreichend, um tatsächlich interaktive Terminalprogramme zu erstellen – sehr eingeschränkt jedoch. Am frustrierendsten ist, dass wir nur Text ausgeben können. Was, wenn wir einige aufregendere Ausgabemöglichkeiten hinzufügen würden?

data Output = TxtOutput String
            | Beep Frequency

main :: String -> [Output]
main _ = [ TxtOutput "Hallo Welt"
          -- , Beep 440  -- zum Debuggen
          ]

Süß, aber natürlich wäre eine viel realistischere „alternative Ausgabe“ das Schreiben in eine Datei. Aber dann würden Sie auch irgendwie aus Dateien lesen wollen. Irgendeine Chance?

Nun, wenn wir unser main-Programm nehmen und einfach eine Datei an den Prozess weiterleiten (unter Verwendung der Betriebssystemfunktionen), haben wir im Grunde genommen das Einlesen von Dateien implementiert. Wenn wir diese Datei durch die Haskell-Sprache lesen könnten...

readFile :: Dateipfad -> (String -> [Output]) -> [Output]

Dies würde ein „interaktives Programm“ String->[Output] verwenden, ihm einen String aus einer Datei zuführen und ein nicht-interaktives Programm erzeugen, das einfach das gegebene ausführt.

Es gibt hier ein Problem: Wir haben nicht wirklich eine Vorstellung davon, wann die Datei gelesen wird. Die [Output]-Liste gibt zwar eine schöne Reihenfolge für die Ausgaben vor, aber wir erhalten keine Reihenfolge dafür, wann die Eingaben erledigt sein werden.

Lösung: Machen Sie Eingabe-Ereignisse auch zu Elementen in der Liste der durchzuführenden Aktionen.

data IO = TxtOut String
         | TxtIn (String -> [Output])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [Output])
         | Beep Double

main :: String -> [IO]
main _ = [ FileRead "/dev/null" $ \_ ->
             [TxtOutput "Hallo Welt"]
          ]

Ok, jetzt können Sie feststellen, dass ein Ungleichgewicht besteht: Sie können eine Datei lesen und die Ausgabe davon abhängig machen, aber Sie können den Dateiinhalt nicht verwenden, um z.B. auch eine andere Datei zu lesen. Offensichtliche Lösung: Machen Sie das Ergebnis der Eingabe-Ereignisse auch zu etwas vom Typ IO, nicht nur Output. Das umfasst sicherlich einfache Textausgaben, ermöglicht aber auch das Lesen zusätzlicher Dateien usw..

data IO = TxtOut String
         | TxtIn (String -> [IO])
         | FileWrite FilePath String
         | FileRead FilePath (String -> [IO])
         | Beep Double

main :: String -> [IO]
main _ = [ TxtIn $ \_ ->
             [TxtOut "Hallo Welt"]
          ]

Dies würde es Ihnen nun tatsächlich ermöglichen, in einem Programm beliebige Dateioperationen auszudrücken (wenn auch möglicherweise nicht mit guter Leistung), aber es ist etwas überkompliziert:

• main gibt eine ganze Liste von Aktionen zurück. Warum verwenden wir nicht einfach die Signatur :: IO, die dies als Spezialfall hat?

• Die Listen geben den Programmfluss nicht mehr wirklich zuverlässig wieder: Die meisten nachfolgenden Berechnungen werden nur als Ergebnis einer Eingabeoperation „angekündigt“. Wir könnten also genauso gut die Listenstruktur verwerfen und einfach für jede Ausgabeoperation ein „und dann tun“ anhängen.

  data IO = TxtOut String IO | TxtIn (String -> IO) | Terminate

  main :: IO main = TxtIn $ _ -> TxtOut "Hallo Welt" Terminate

Nicht schlecht!

Was hat das alles mit Monaden zu tun?

In der Praxis würden Sie nicht wollen, dass Sie normale Konstruktoren verwenden, um all Ihre Programme zu definieren. Es müsste eine gute Anzahl solcher grundlegenden Konstruktoren geben, aber für die meisten höheren Sachen möchten Sie wahrscheinlich eine Funktion mit einer schönen hochrangigen Signatur schreiben. Es stellt sich heraus, dass die meisten von diesen ziemlich ähnlich aussehen würden: Sie akzeptieren einen Wert mit einer bedeutungsvollen Typisierung und liefern eine IO-Aktion als Ergebnis.

getTime :: (UTCTime -> IO) -> IO
randomRIO :: Random r => (r,r) -> (r -> IO) -> IO
findFile :: RegEx -> (Maybe FilePath -> IO) -> IO

Es gibt offensichtlich ein Muster hier, und wir sollten es besser als

type IO a = (a -> IO) -> IO    -- Wenn Sie dabei an continuation-passing
                                  -- Stil erinnert werden, liegen Sie richtig.

getTime :: IO UTCTime
randomRIO :: Random r => (r,r) -> IO r
findFile :: RegEx -> IO (Maybe FilePath)

Jetzt fängt das schon vertraut auszusehen an, aber wir haben immer noch nur mit dünn verschleierten normalen Funktionen unter der Haube zu tun, und das ist riskant: Jede „Wert-Aktion“ hat die Verantwortung, die resultierende Aktion jeder enthaltenen Funktion tatsächlich weiterzuleiten (sonst kann der Kontrollfluss des gesamten Programms leicht durch eine ungezogene Aktion in der Mitte unterbrochen werden). Wir sollten diese Anforderung besser explizit machen. Nun, es stellt sich heraus, dass dies die Monadengesetze sind, obwohl ich mir nicht sicher bin, ob wir sie wirklich ohne die Standard-Bind/Joint-Operatoren formulieren können.

Zumindest haben wir jetzt eine Formulierung von IO erreicht, die eine ordentliche Monade-Instanz hat:

data IO a = TxtOut String (IO a)
           | TxtIn (String -> IO a)
           | TerminateWith a

txtOut :: String -> IO ()
txtOut s = TxtOut s $ TerminateWith ()

txtIn :: IO String
txtIn = TxtIn $ TerminateWith

instance Functor IO where
  fmap f (TerminateWith a) = TerminateWith $ f a
  fmap f (TxtIn g) = TxtIn $ fmap f . g
  fmap f (TxtOut s c) = TxtOut s $ fmap f c

instance Applicative IO where
  pure = TerminateWith
  (<*>) = ap

instance Monad IO where
  TerminateWith x >>= f = f x
  TxtOut s c >>= f = TxtOut s $ c >>= f
  TxtIn g >>= f = TxtIn $ (>>=f) . g

Offensichtlich handelt es sich hier nicht um eine effiziente Implementierung von IO, aber im Prinzip ist sie verwendbar.

Answer 5

Monaden dienen im Grunde dazu, Funktionen in einer Kette zusammenzusetzen. Punkt.

Der Weg, wie sie zusammengesetzt werden, unterscheidet sich je nach den vorhandenen Monaden, was zu unterschiedlichem Verhalten führt (z. B. zur Simulation von veränderlichem Zustand in der Zustandsmonade).

Die Verwirrung über Monaden besteht darin, dass sie so allgemein sind, d. h. ein Mechanismus zum Komponieren von Funktionen, dass sie für viele Dinge verwendet werden können und Menschen glauben lassen, dass Monaden etwas mit Zustand, Eingabe/Ausgabe usw. zu tun haben, wenn es nur darum geht, "Funktionen zu komponieren".

Eine interessante Sache an Monaden ist, dass das Ergebnis der Komposition immer vom Typ "M a" ist, d. h. ein Wert in einem mit "M" verschlossenen Umschlag. Diese Eigenschaft ist zum Beispiel sehr nützlich, um eine klare Trennung zwischen reinem und unreinem Code zu implementieren: Deklariere alle unreinen Aktionen als Funktionen vom Typ "IO a" und gebe keine Funktion an, wenn die IO-Monade definiert wird, um den "a"-Wert von innerhalb des "IO a" herauszunehmen. Das Ergebnis ist, dass keine Funktion rein sein kann und gleichzeitig einen Wert aus einem "IO a" herausnehmen kann, weil es keinen Weg gibt, einen solchen Wert zu entnehmen, während sie rein bleibt (die Funktion muss in der "IO" Monade sein, um einen solchen Wert zu verwenden). (ANMERKUNG: Nun, nichts ist perfekt, also kann die "IO Zwangsjacke" mit "unsafePerformIO : IO a -> a" gebrochen werden, was das, was eine reine Funktion sein sollte, verschmutzt, aber dies sollte sehr sparsam und nur dann verwendet werden, wenn man wirklich sicher ist, dass keine unreiner Code mit Nebenwirkungen eingeführt wird.