Was ist eine Monade?

Question

Nachdem ich mich kürzlich kurz mit Haskell beschäftigt habe, was wäre ein kurz, prägnant, praktisch eine Erklärung, was eine Monade im Wesentlichen ist?

Die meisten Erklärungen, auf die ich gestoßen bin, waren ziemlich unzugänglich und enthielten keine praktischen Details.

Answer 1

(Siehe auch die Antworten unter Was ist eine Monade? )

Eine gute Motivation zu Monaden ist sigfpe (Dan Piponi)'s Du hättest die Monaden erfinden können! (Und vielleicht haben Sie das schon) . Es gibt eine MENGE anderer Monaden-Tutorials die in vielen Fällen fälschlicherweise versuchen, Monaden in "einfachen Begriffen" zu erklären, indem sie verschiedene Analogien verwenden: dies ist die Irrtum des Monadenunterrichts zu vermeiden.

Wie DR MacIver sagt in Sag uns, warum deine Sprache schlecht ist :

Also, Dinge, die ich an Haskell hasse:

Fangen wir mit dem Offensichtlichen an. Monaden-Tutorials. Nein, nicht Monaden. Genauer gesagt, die Tutorials. Sie sind endlos, aufgeblasen und, mein Gott, sind sie langweilig. Außerdem habe ich noch nie einen überzeugenden Beweis dafür gesehen, dass sie tatsächlich helfen. Lesen Sie die Klassendefinition, schreiben Sie etwas Code, überwinden Sie den gruseligen Namen.

Sie sagen, Sie verstehen die Maybe-Monade? Gut, Sie sind auf dem richtigen Weg. Fangen Sie einfach an, andere Monaden zu benutzen und früher oder später werden Sie verstehen, was Monaden im Allgemeinen sind.

[Wenn Sie mathematisch veranlagt sind, können Sie die Dutzenden von Tutorials ignorieren und die Definition lernen, oder Sie folgen Vorlesungen in Kategorientheorie :) Der wichtigste Teil der Definition ist, dass eine Monade M einen "Typkonstruktor" beinhaltet, der für jeden existierenden Typ "T" einen neuen Typ "M T" definiert, und einige Möglichkeiten, zwischen "normalen" Typen und "M"-Typen hin und her zu wechseln].

Überraschenderweise ist eine der besten Einführungen in Monaden eine der frühen akademischen Abhandlungen, die Monaden einführen, nämlich Philip Wadler's Monaden für die funktionale Programmierung . Es hat tatsächlich praktisch, nicht trivial motivierende Beispiele, anders als viele der künstlichen Tutorials, die es gibt.

Answer 2

Monaden sind für den Kontrollfluss das, was abstrakte Datentypen für Daten sind.

Mit anderen Worten, viele Entwickler sind mit der Idee von Sets, Listen, Dictionaries (oder Hashes oder Maps) und Trees vertraut. Innerhalb dieser Datentypen gibt es viele Sonderfälle (z. B. InsertionOrderPreservingIdentityHashMap).

Wenn sie jedoch mit Programm-"Flow" konfrontiert werden, haben viele Entwickler nicht viel mehr Konstrukte als if, switch/case, do, while, goto (grr) und (vielleicht) closures kennengelernt.

Eine Monade ist also einfach ein Kontrollfluss-Konstrukt. Ein besserer Ausdruck, um Monade zu ersetzen, wäre "Kontrolltyp".

Eine Monade als solche hat Slots für Kontrolllogik, Anweisungen oder Funktionen - das Äquivalent in Datenstrukturen wäre, dass einige Datenstrukturen es erlauben, Daten hinzuzufügen und zu entfernen.

Zum Beispiel die "if"-Monade:

if( clause ) then block

hat in seiner einfachsten Form zwei Slots - eine Klausel und einen Block. Die if Monade wird in der Regel so aufgebaut, dass sie das Ergebnis der Klausel auswertet, und wenn es nicht falsch ist, den Block auswertet. Viele Entwickler werden nicht in Monaden eingeführt, wenn sie "if" lernen, und es ist einfach nicht notwendig, Monaden zu verstehen, um effektive Logik zu schreiben.

Monaden können komplizierter werden, genauso wie Datenstrukturen komplizierter werden können, aber es gibt viele breite Kategorien von Monaden, die eine ähnliche Semantik, aber unterschiedliche Implementierungen und Syntax haben können.

Genauso wie Datenstrukturen iteriert oder traversiert werden können, können Monaden natürlich auch ausgewertet werden.

Compiler können benutzerdefinierte Monaden unterstützen, müssen es aber nicht. Haskell hat sie sicherlich. Ioke hat einige ähnliche Fähigkeiten, obwohl der Begriff Monade in dieser Sprache nicht verwendet wird.

Answer 3

Mein Lieblings-Monad-Tutorial:

http://www.haskell.org/haskellwiki/All_About_Monads

(von 170.000 Treffern bei einer Google-Suche nach "monad tutorial"!)

@Stu: Der Sinn von Monaden ist, dass man (normalerweise) sequentielle Semantik zu ansonsten reinem Code hinzufügen kann; man kann sogar Monaden zusammensetzen (mit Monad Transformers) und eine interessantere und kompliziertere kombinierte Semantik erhalten, wie z.B. Parsing mit Fehlerbehandlung, gemeinsamem Zustand und Logging. All dies ist in reinem Code möglich, Monaden erlauben es Ihnen lediglich, es zu abstrahieren und in modularen Bibliotheken wiederzuverwenden (was in der Programmierung immer gut ist), und sie bieten eine bequeme Syntax, um es zwingend aussehen zu lassen.

Haskell verfügt bereits über Operatorüberladung[1]: Es verwendet Typklassen, ähnlich wie man Schnittstellen in Java oder C# verwenden könnte, aber Haskell erlaubt zufällig auch nicht-alphanumerische Zeichen wie + && und > als Infix-Bezeichner. Es ist nur dann eine Operatorüberladung, wenn Sie "Überladung des Semikolons" [2] meinen. Es klingt nach schwarzer Magie und Ärger, das Semikolon zu "überladen" (stellen Sie sich vor, dass findige Perl-Hacker von dieser Idee Wind bekommen), aber der Punkt ist, dass ohne Monaden gibt es kein Semikolon, da rein funktionaler Code keine explizite Sequenzierung erfordert oder erlaubt.

Das hört sich alles viel komplizierter an, als es sein müsste. sigfpes Artikel ist ziemlich cool, verwendet aber Haskell, um es zu erklären, was das Henne-Ei-Problem, Haskell zu verstehen, um Monads zu verstehen, und Monads zu verstehen, um Haskell zu verstehen, nicht lösen kann.

[1] Dies ist ein anderes Thema als Monaden, aber Monaden verwenden Haskells Operator-Überladefunktion.

[2] Dies ist auch eine starke Vereinfachung, da der Operator für die Verkettung monadischer Aktionen >>= (ausgesprochen "bind") ist, aber es gibt syntaktischen Zucker ("do"), der die Verwendung von geschweiften Klammern und Semikolons und/oder Einrückungen und Zeilenumbrüchen ermöglicht.

Answer 4

Ich kenne mich noch nicht so gut mit Monaden aus, aber ich dachte, ich würde einen Link weitergeben, den ich gefunden habe und der wirklich gut zu lesen war (MIT BILDERN!!): http://www.matusiak.eu/numerodix/blog/2012/3/11/monads-for-the-layman/ (keine Zugehörigkeit)

Im Grunde genommen war das Konzept, das ich aus dem Artikel mitgenommen habe, das Konzept, dass Monaden im Grunde genommen Adapter sind, die es ermöglichen, dass unterschiedliche Funktionen auf eine zusammensetzbare Art und Weise funktionieren, d.h. dass man mehrere Funktionen aneinanderreihen und mischen kann, ohne sich Gedanken über inkonsistente Rückgabetypen und dergleichen zu machen. Die BIND-Funktion ist also dafür zuständig, Äpfel mit Äpfeln und Orangen mit Orangen zu vergleichen, wenn wir versuchen, diese Adapter zu erstellen. Und die LIFT-Funktion ist dafür zuständig, Funktionen auf "niedrigerer Ebene" zu nehmen und sie "aufzurüsten", damit sie mit BIND-Funktionen zusammenarbeiten und auch zusammensetzbar sind.

Ich hoffe, dass ich es richtig verstanden habe und, was noch wichtiger ist, hoffe, dass der Artikel eine gültige Sicht auf Monaden hat. Zumindest hat dieser Artikel meinen Appetit geweckt, mehr über Monaden zu lernen.

Answer 5

Tl;dr

{-# LANGUAGE InstanceSigs #-}

newtype Id t = Id t

instance Monad Id where
   return :: t -> Id t
   return = Id

   (=<<) :: (a -> Id b) -> Id a -> Id b
   f =<< (Id x) = f x

Prolog

Der Betreiber der Anwendung $ von Funktionen

forall a b. a -> b

ist kanonisch definiert

($) :: (a -> b) -> a -> b
f $ x = f x

infixr 0 $

im Sinne der Anwendung der Haskell-Primitivfunktion f x ( infixl 10 ).

Zusammensetzung . ist definiert als $ als

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \ x -> f $ g x

infixr 9 .

und erfüllt die Äquivalenzen forall f g h.

     f . id  =  f            :: c -> d   Right identity
     id . g  =  g            :: b -> c   Left identity
(f . g) . h  =  f . (g . h)  :: a -> d   Associativity

. ist assoziativ, und id ist seine rechte und linke Identität.

Das Kleisli-Triple

In der Programmierung ist eine Monade ein Funktortypkonstruktor mit einer Instanz der Monadentypklasse. Es gibt mehrere äquivalente Definitions- und Implementierungsvarianten, die jeweils leicht unterschiedliche Intuitionen über die Monadenabstraktion vermitteln.

Ein Funktor ist ein Typkonstruktor f von Art * -> * mit einer Instanz der Funktypklasse.

{-# LANGUAGE KindSignatures #-}

class Functor (f :: * -> *) where
   map :: (a -> b) -> (f a -> f b)

Zusätzlich zu den statisch erzwungenen Typprotokollen müssen Instanzen der Funktortypklasse den algebraischen Funktorengesetze forall f g.

       map id  =  id           :: f t -> f t   Identity
map f . map g  =  map (f . g)  :: f a -> f c   Composition / short cut fusion

Faktor Berechnungen haben den Typ

forall f t. Functor f => f t

Eine Berechnung c r besteht in Ergebnisse r innerhalb Kontext c .

Unäre monadische Funktionen oder Kleisli-Pfeile haben den Typ

forall m a b. Functor m => a -> m b

Kleisi-Pfeile sind Funktionen, die ein Argument benötigen a und eine monadische Berechnung zurückgeben m b .

Monaden sind kanonisch definiert in Form der Kleisli dreifach forall m. Functor m =>

(m, return, (=<<))

implementiert als die Typklasse

class Functor m => Monad m where
   return :: t -> m t
   (=<<)  :: (a -> m b) -> m a -> m b

infixr 1 =<<

El Kleisli Identität return ist ein Kleisli-Pfeil, der einen Wert fördert t in monadischen Kontext m . Erweiterung o Kleisli-Anwendung =<< wendet einen Kleisli-Pfeil an a -> m b zu Ergebnissen einer Berechnung m a .

Kleisli Zusammensetzung <=< ist in Bezug auf die Erweiterung definiert als

(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
f <=< g = \ x -> f =<< g x

infixr 1 <=<

<=< setzt zwei Kleisli-Pfeile zusammen, wobei der linke Pfeil auf die Ergebnisse der Anwendung des rechten Pfeils angewendet wird.

Instanzen der Monadentypklasse müssen der Monadengesetze am elegantesten im Sinne der Kleisli-Komposition: forall f g h.

   f <=< return  =  f                :: c -> m d   Right identity
   return <=< g  =  g                :: b -> m c   Left identity
(f <=< g) <=< h  =  f <=< (g <=< h)  :: a -> m d   Associativity

<=< ist assoziativ, und return ist seine rechte und linke Identität.

Identität

Der Identitätstyp

type Id t = t

ist die Identitätsfunktion für Typen

Id :: * -> *

Interpretiert als ein Funktor,

   return :: t -> Id t
=      id :: t ->    t

    (=<<) :: (a -> Id b) -> Id a -> Id b
=     ($) :: (a ->    b) ->    a ->    b

    (<=<) :: (b -> Id c) -> (a -> Id b) -> (a -> Id c)
=     (.) :: (b ->    c) -> (a ->    b) -> (a ->    c)

Im kanonischen Haskell ist die Identitätsmonade wie folgt definiert

newtype Id t = Id t

instance Functor Id where
   map :: (a -> b) -> Id a -> Id b
   map f (Id x) = Id (f x)

instance Monad Id where
   return :: t -> Id t
   return = Id

   (=<<) :: (a -> Id b) -> Id a -> Id b
   f =<< (Id x) = f x

Option

Ein Optionstyp

data Maybe t = Nothing | Just t

verschlüsselt die Berechnungen Maybe t das nicht unbedingt zu einem Ergebnis führt t Berechnungen, die "fehlschlagen" können. Die Optionsmonade ist definiert

instance Functor Maybe where
   map :: (a -> b) -> (Maybe a -> Maybe b)
   map f (Just x) = Just (f x)
   map _ Nothing  = Nothing

instance Monad Maybe where
   return :: t -> Maybe t
   return = Just

   (=<<) :: (a -> Maybe b) -> Maybe a -> Maybe b
   f =<< (Just x) = f x
   _ =<< Nothing  = Nothing

a -> Maybe b wird nur dann auf ein Ergebnis angewendet, wenn Maybe a führt zu einem Ergebnis.

newtype Nat = Nat Int

Die natürlichen Zahlen können als ganze Zahlen größer oder gleich Null kodiert werden.

toNat :: Int -> Maybe Nat
toNat i | i >= 0    = Just (Nat i)
        | otherwise = Nothing

Die natürlichen Zahlen sind bei der Subtraktion nicht geschlossen.

(-?) :: Nat -> Nat -> Maybe Nat
(Nat n) -? (Nat m) = toNat (n - m)

infixl 6 -?

Die Optionsmonade deckt eine grundlegende Form der Ausnahmebehandlung ab.

(-? 20) <=< toNat :: Int -> Maybe Nat

Liste

Die Listenmonade, über den Listentyp

data [] t = [] | t : [t]

infixr 5 :

und seine additive monoide Operation "append"

(++) :: [t] -> [t] -> [t]
(x : xs) ++ ys = x : xs ++ ys
[]       ++ ys = ys

infixr 5 ++

kodiert nichtlinear Berechnung [t] was eine natürliche Menge ergibt 0, 1, ... der Ergebnisse t .

instance Functor [] where
   map :: (a -> b) -> ([a] -> [b])
   map f (x : xs) = f x : map f xs
   map _ []       = []

instance Monad [] where
   return :: t -> [t]
   return = (: [])

   (=<<) :: (a -> [b]) -> [a] -> [b]
   f =<< (x : xs) = f x ++ (f =<< xs)
   _ =<< []       = []

Erweiterung =<< verkettet ++ alle Listen [b] die sich aus Anwendungen ergeben f x eines Kleisli-Pfeils a -> [b] zu Elementen von [a] in eine einzige Ergebnisliste [b] .

Es seien die richtigen Teiler einer positiven ganzen Zahl n sein

divisors :: Integral t => t -> [t]
divisors n = filter (`divides` n) [2 .. n - 1]

divides :: Integral t => t -> t -> Bool
(`divides` n) = (== 0) . (n `rem`)

dann

forall n.  let { f = f <=< divisors } in f n   =   []

Bei der Definition der Monadentypklasse wird anstelle der Erweiterung =<< verwendet der Haskell-Standard seine Umkehrung, das binden Betreiber >>= .

class Applicative m => Monad m where
   (>>=) :: forall a b. m a -> (a -> m b) -> m b

   (>>) :: forall a b. m a -> m b -> m b
   m >> k = m >>= \ _ -> k
   {-# INLINE (>>) #-}

   return :: a -> m a
   return = pure

Der Einfachheit halber wird in dieser Erklärung die Hierarchie der Typklassen verwendet

class              Functor f
class Functor m => Monad m

In Haskell ist die aktuelle Standardhierarchie

class                  Functor f
class Functor p     => Applicative p
class Applicative m => Monad m

denn nicht nur jede Monade ist ein Funktor, sondern auch jeder Applikativ ist ein Funktor und jede Monade ist ein Applikativ.

Unter Verwendung der Listenmonade wird der imperative Pseudocode

for a in (1, ..., 10)
   for b in (1, ..., 10)
      p <- a * b
      if even(p)
         yield p

entspricht in etwa dem sperren ,

do a <- [1 .. 10]
   b <- [1 .. 10]
   let p = a * b
   guard (even p)
   return p

das Äquivalent Monadenverständnis ,

[ p | a <- [1 .. 10], b <- [1 .. 10], let p = a * b, even p ]

und der Ausdruck

[1 .. 10] >>= (\ a ->
   [1 .. 10] >>= (\ b ->
      let p = a * b in
         guard (even p) >>       -- [ () | even p ] >>
            return p
      )
   )

Do-Notation und Monadenverständnisse sind syntaktischer Zucker für verschachtelte Bind-Ausdrücke. Der bind-Operator wird für die lokale Namensbindung von monadischen Ergebnissen verwendet.

let x = v in e    =   (\ x -> e)  $  v   =   v  &  (\ x -> e)
do { r <- m; c }  =   (\ r -> c) =<< m   =   m >>= (\ r -> c)

wobei

(&) :: a -> (a -> b) -> b
(&) = flip ($)

infixl 0 &

Die Schutzfunktion ist definiert als

guard :: Additive m => Bool -> m ()
guard True  = return ()
guard False = fail

wo die Einheitentyp oder "leeres Tupel"

data () = ()

Additive Monaden die Unterstützung Auswahl y Ausfall kann durch eine Typklasse abstrahiert werden

class Monad m => Additive m where
   fail  :: m t
   (<|>) :: m t -> m t -> m t

infixl 3 <|>

instance Additive Maybe where
   fail = Nothing

   Nothing <|> m = m
   m       <|> _ = m

instance Additive [] where
   fail = []
   (<|>) = (++)

donde fail y <|> ein Monoid bilden forall k l m.

     k <|> fail  =  k
     fail <|> l  =  l
(k <|> l) <|> m  =  k <|> (l <|> m)

y fail ist das absorbierende/annihilierende Nullelement der additiven Monaden

_ =<< fail  =  fail

Wenn in

guard (even p) >> return p

even p wahr ist, erzeugt der Wächter [()] und, nach der Definition von >> die lokale konstante Funktion

\ _ -> return p

wird auf das Ergebnis angewendet () . Wenn false, dann produziert der Guard die Liste monad's fail ( [] ), was zu keinem Ergebnis für einen anzuwendenden Kleisli-Pfeil führt >> zu, so dass diese p wird übersprungen.

Staat

Berüchtigterweise werden Monaden zur Kodierung zustandsabhängiger Berechnungen verwendet.

A Statusprozessor ist eine Funktion

forall st t. st -> (t, st)

die einen Zustand übergeht st und führt zu einem Ergebnis t . Die Staat st kann alles sein. Nichts, Flagge, Anzahl, Array, Griff, Maschine, Welt.

Die Art der Statusprozessoren wird gewöhnlich als

type State st t = st -> (t, st)

Die Zustandsprozessormonade ist die geartete * -> * Funktor State st . Kleisli-Pfeile der Zustandsprozessormonade sind Funktionen

forall st a b. a -> (State st) b

Im kanonischen Haskell ist die träge Version der Zustandsprozessormonade wie folgt definiert

newtype State st t = State { stateProc :: st -> (t, st) }

instance Functor (State st) where
   map :: (a -> b) -> ((State st) a -> (State st) b)
   map f (State p) = State $ \ s0 -> let (x, s1) = p s0
                                     in  (f x, s1)

instance Monad (State st) where
   return :: t -> (State st) t
   return x = State $ \ s -> (x, s)

   (=<<) :: (a -> (State st) b) -> (State st) a -> (State st) b
   f =<< (State p) = State $ \ s0 -> let (x, s1) = p s0
                                     in  stateProc (f x) s1

Ein Zustandsprozessor wird gestartet, indem ein Anfangszustand vorgegeben wird:

run :: State st t -> st -> (t, st)
run = stateProc

eval :: State st t -> st -> t
eval = fst . run

exec :: State st t -> st -> st
exec = snd . run

Der Zugriff auf den Zustand wird durch Primitive ermöglicht get y put Methoden der Abstraktion über zustandsabhängig Monaden:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

class Monad m => Stateful m st | m -> st where
   get :: m st
   put :: st -> m ()

m -> st erklärt eine Funktionsabhängigkeit des Zustandstyps st über die Monade m dass ein State t wird zum Beispiel der Zustandstyp t Einzigartig.

instance Stateful (State st) st where
   get :: State st st
   get = State $ \ s -> (s, s)

   put :: st -> State st ()
   put s = State $ \ _ -> ((), s)

wobei der Einheitentyp analog zu void in C.

modify :: Stateful m st => (st -> st) -> m ()
modify f = do
   s <- get
   put (f s)

gets :: Stateful m st => (st -> t) -> m t
gets f = do
   s <- get
   return (f s)

gets wird häufig mit Datensatzfeldzugriffsgeräten verwendet.

Das Äquivalent der Zustandsmonade für die Variable Threading

let s0 = 34
    s1 = (+ 1) s0
    n = (* 12) s1
    s2 = (+ 7) s1
in  (show n, s2)

donde s0 :: Int ist das ebenso transparente, aber unendlich viel elegantere und praktischere

(flip run) 34
   (do
      modify (+ 1)
      n <- gets (* 12)
      modify (+ 7)
      return (show n)
   )

modify (+ 1) ist eine Berechnung des Typs State Int () mit Ausnahme seiner Wirkung gleichbedeutend mit return () .

(flip run) 34
   (modify (+ 1) >>
      gets (* 12) >>= (\ n ->
         modify (+ 7) >>
            return (show n)
      )
   )

Das Monadengesetz der Assoziativität kann wie folgt formuliert werden >>= forall m f g.

(m >>= f) >>= g  =  m >>= (\ x -> f x >>= g)

oder

do {                 do {                   do {
   r1 <- do {           x <- m;                r0 <- m;
      r0 <- m;   =      do {            =      r1 <- f r0;
      f r0                 r1 <- f x;          g r1
   };                      g r1             }
   g r1                 }
}                    }

Wie in der ausdrucksorientierten Programmierung (z.B. Rust) stellt die letzte Anweisung eines Blocks dessen Ergebnis dar. Der Bind-Operator wird manchmal als "programmierbares Semikolon" bezeichnet.

Iterationskontrollstruktur-Primitive aus der strukturierten imperativen Programmierung werden monadisch emuliert

for :: Monad m => (a -> m b) -> [a] -> m ()
for f = foldr ((>>) . f) (return ())

while :: Monad m => m Bool -> m t -> m ()
while c m = do
   b <- c
   if b then m >> while c m
        else return ()

forever :: Monad m => m t
forever m = m >> forever m

Eingabe/Ausgabe

data World

Die E/A-Weltzustandsprozessormonade ist eine Versöhnung von reinem Haskell und der realen Welt, von funktionaler denotativer und imperativer operativer Semantik. Ein nahes Analogon der tatsächlichen strikten Implementierung:

type IO t = World -> (t, World)

Interaktion wird durch unreine Primitive erleichtert

getChar         :: IO Char
putChar         :: Char -> IO ()
readFile        :: FilePath -> IO String
writeFile       :: FilePath -> String -> IO ()
hSetBuffering   :: Handle -> BufferMode -> IO ()
hTell           :: Handle -> IO Integer
. . .              . . .

Die Unreinheit von Code, der IO Primitive ist durch das Typsystem permanent protokolliert. Weil Reinheit großartig ist, passiert das, was in IO , bleibt in IO .

unsafePerformIO :: IO t -> t

Oder sollte es zumindest.

Die Typsignatur eines Haskell-Programms

main :: IO ()
main = putStrLn "Hello, World!"

erweitert sich auf

World -> ((), World)

Eine Funktion, die eine Welt transformiert.

Epilog

Die Kategorie, deren Objekte Haskell-Typen sind und deren Morphismen Funktionen zwischen Haskell-Typen sind, ist, "kurz und knapp", die Kategorie Hask .

Ein Funktor T ist eine Abbildung aus einer Kategorie C zu einer Kategorie D für jedes Objekt in C ein Objekt in D

Tobj :  Obj(C) -> Obj(D)
   f :: *      -> *

und für jeden Morphismus in C ein Morphismus in D

Tmor :  HomC(X, Y) -> HomD(Tobj(X), Tobj(Y))
 map :: (a -> b)   -> (f a -> f b)

donde X , Y sind Objekte in C . HomC(X, Y) es el Homomorphismenklasse aller Morphismen X -> Y in C . Der Funktor muss Morphismusidentität und Komposition bewahren, die "Struktur" von C , in D .

                    Tmor    Tobj

      T(id)  =  id        : T(X) -> T(X)   Identity
T(f) . T(g)  =  T(f . g)  : T(X) -> T(Z)   Composition

El Kategorie Kleisli einer Kategorie C ist gegeben durch ein Kleisli-Tripel

<T, eta, _*>

eines Endofunktors

T : C -> C

( f ), ein Identitätsmorphismus eta ( return ), und ein Erweiterungsoperator * ( =<< ).

Jeder Kleisli-Morphismus in Hask

      f :  X -> T(Y)
      f :: a -> m b

durch den Nebenstellenbetreiber

   (_)* :  Hom(X, T(Y)) -> Hom(T(X), T(Y))
  (=<<) :: (a -> m b)   -> (m a -> m b)

ist ein Morphismus in Hask Die Kategorie Kleisli

     f* :  T(X) -> T(Y)
(f =<<) :: m a  -> m b

Zusammensetzung in der Kategorie Kleisli .T ist gegeben in Form der Erweiterung

 f .T g  =  f* . g       :  X -> T(Z)
f <=< g  =  (f =<<) . g  :: a -> m c

und erfüllt die Kategorie-Axiome

       eta .T g  =  g                :  Y -> T(Z)   Left identity
   return <=< g  =  g                :: b -> m c

       f .T eta  =  f                :  Z -> T(U)   Right identity
   f <=< return  =  f                :: c -> m d

  (f .T g) .T h  =  f .T (g .T h)    :  X -> T(U)   Associativity
(f <=< g) <=< h  =  f <=< (g <=< h)  :: a -> m d

die unter Anwendung der Äquivalenztransformationen

     eta .T g  =  g
     eta* . g  =  g               By definition of .T
     eta* . g  =  id . g          forall f.  id . f  =  f
         eta*  =  id              forall f g h.  f . h  =  g . h  ==>  f  =  g

(f .T g) .T h  =  f .T (g .T h)
(f* . g)* . h  =  f* . (g* . h)   By definition of .T
(f* . g)* . h  =  f* . g* . h     . is associative
    (f* . g)*  =  f* . g*         forall f g h.  f . h  =  g . h  ==>  f  =  g

in Bezug auf die Erweiterung sind kanonisch gegeben

               eta*  =  id                 :  T(X) -> T(X)   Left identity
       (return =<<)  =  id                 :: m t -> m t

           f* . eta  =  f                  :  Z -> T(U)      Right identity
   (f =<<) . return  =  f                  :: c -> m d

          (f* . g)*  =  f* . g*            :  T(X) -> T(Z)   Associativity
(((f =<<) . g) =<<)  =  (f =<<) . (g =<<)  :: m a -> m c

Monaden können auch nicht durch die Kleislsche Erweiterung, sondern durch eine natürliche Transformation definiert werden mu in der Programmierung genannt join . Eine Monade ist definiert durch die Begriffe mu als ein Tripel über einer Kategorie C eines Endofunktors

     T :  C -> C
     f :: * -> *

und zwei natürliche Umformungen

   eta :  Id -> T
return :: t  -> f t

    mu :  T . T   -> T
  join :: f (f t) -> f t

die die Äquivalenzen erfüllen

       mu . T(mu)  =  mu . mu               :  T . T . T -> T . T   Associativity
  join . map join  =  join . join           :: f (f (f t)) -> f t

      mu . T(eta)  =  mu . eta       =  id  :  T -> T               Identity
join . map return  =  join . return  =  id  :: f t -> f t

Die Monadentypklasse wird dann definiert

class Functor m => Monad m where
   return :: t -> m t
   join   :: m (m t) -> m t

Die kanonische mu Implementierung der Optionsmonade:

instance Monad Maybe where
   return = Just

   join (Just m) = m
   join Nothing  = Nothing

El concat Funktion

concat :: [[a]] -> [a]
concat (x : xs) = x ++ concat xs
concat []       = []

ist die join der Listenmonade.

instance Monad [] where
   return :: t -> [t]
   return = (: [])

   (=<<) :: (a -> [b]) -> ([a] -> [b])
   (f =<<) = concat . map f

Implementierungen von join kann aus der Erweiterungsform mit Hilfe der Äquivalenz übersetzt werden

     mu  =  id*           :  T . T -> T
   join  =  (id =<<)      :: m (m t) -> m t

Die umgekehrte Übersetzung von mu in die Erweiterungsform ist gegeben durch

     f*  =  mu . T(f)     :  T(X) -> T(Y)
(f =<<)  =  join . map f  :: m a -> m b

---

• Philip Wadler: Monaden für die funktionale Programmierung

• Simon L. Peyton Jones, Philip Wadler: Imperative funktionale Programmierung

• Jonathan M. D. Hill, Keith Clarke: _Eine Einführung in die Kategorientheorie, kategorientheoretische Monaden und ihre Beziehung zur funktionalen Programmierung_ '

• Kategorie Kleisli

• Eugenio Moggi: Begriffe des Rechnens und der Monaden

• Was eine Monade nicht ist

Aber warum sollte eine so abstrakte Theorie für die Programmierung von Nutzen sein?

Die Antwort ist einfach: Als Informatiker müssen wir Wertabstraktion ! Wenn wir die Schnittstelle zu einer Softwarekomponente entwerfen, müssen wir wollen es soll so wenig wie möglich über die Umsetzung verraten werden. Wir wollen in der Lage sein, die Implementierung durch viele Alternativen, viele andere "Instanzen" desselben "Konzepts" zu ersetzen. Wenn wir eine generische Schnittstelle zu vielen Programmbibliotheken entwerfen, ist es sogar noch wichtiger, dass die von uns gewählte Schnittstelle eine Vielzahl von Implementierungen hat. Es ist die Allgemeingültigkeit des Monadenkonzepts, die wir so sehr schätzen, es ist denn Die Kategorientheorie ist so abstrakt, dass ihre Konzepte für die Programmierung sehr nützlich sind.

Es ist daher kaum überraschend, dass die Verallgemeinerung der Monaden, die wir im Folgenden vorstellen, auch eine enge Verbindung zur Kategorientheorie hat. Wir betonen jedoch, dass unser Ziel sehr praktisch ist: Es geht nicht darum, die Kategorientheorie zu "implementieren", sondern einen allgemeineren Weg zur Strukturierung von Kombinator-Bibliotheken zu finden. Es ist einfach unser Glück, dass Mathematiker bereits einen Großteil der Arbeit für uns erledigt haben!

von Verallgemeinerung von Monaden auf Pfeile von John Hughes