haskell - zustand - monads

Was ist eine Monade? (20)

Haskell kurz betrachtet, was wäre eine kurze, prägnante, praktische Erklärung, was eine Monade im Wesentlichen ist?

Ich habe die meisten Erklärungen gefunden, die mir ziemlich unzugänglich erschienen und denen es an praktischen Einzelheiten mangelt.

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


The application operator $ of functions

forall a b. a -> b

is canonically defined

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

infixr 0 $

in terms of Haskell-primitive function application fx ( infixl 10 ). Composition . is defined in terms of $ as

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

infixr 9 .

and satisfies the equivalences forall fg h.

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

. is associative, and id is its right and left identity.

The Kleisli triple

In programming, a monad is functor type constructor with an instance of the monad type class. There are several equivalent variants of definition and implementation, each carrying slightly different intuitions about the monad abstraction.

A functor is a type constructor f of kind * -> * with an instance of the functor type class.

{-# LANGUAGE KindSignatures #-}

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

In addition to following statically enforced type protocol, instances of the functor type class must obey the algebraic functor laws 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

Functor computations have the type

forall f t. Functor f => f t

A computation cr consists in results r within context c .

Unary monadic functions or Kleisli arrows have the type

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

Kleisi arrows are functions that take one argument a and return a monadic computation mb .

Monads are canonically defined in terms of the Kleisli triple forall m. Functor m =>

(m, return, (=<<))

implemented as the type class

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

infixr 1 =<<

The Kleisli identity return is a Kleisli arrow that promotes a value t into monadic context m . Extension or Kleisli application =<< applies a Kleisli arrow a -> mb to results of a computation ma .

Kleisli composition <=< is defined in terms of extension as

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

infixr 1 <=<

<=< composes two Kleisli arrows, applying the left arrow to results of the right arrow's application.

Instances of the monad type class must obey the monad laws , most elegantly stated in terms of Kleisli composition: forall fg h.

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

<=< is associative, and return is its right and left identity.


The identity type

type Id t = t

is the identity function on types

Id :: * -> *

Interpreted as a functor,

   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)

In canonical Haskell, the identity monad is defined

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


An option type

data Maybe t = Nothing | Just t

encodes computation Maybe t that may not yield a result t , computation that may “fail”. The option monad is defined

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 is applied only if Maybe a yields a result.

newtype Nat = Nat Int

The natural numbers can be encoded as those integers greater than or equal to zero.

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

The natural numbers are not closed under subtraction.

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

infixl 6 -?

The option monad covers a basic form of exception handling.

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


The list monad, over the list type

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

infixr 5 :

and its additive monoid operation “append”

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

infixr 5 ++

encodes nonlinear computation [t] yielding a natural amount 0, 1, ... of results 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
   _ =<< []       = []

Extension concatenates ++ all result lists [b] from applications fx of a Kleisli arrow a -> [b] to elements of [a] into a single result list [b] .

Let the proper divisors of a positive integer n be

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

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


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

In defining the monad type class, instead of extension =<< , the Haskell standard uses its flip, the bind operator >>= .

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

   fail :: String -> m a
   fail s = errorWithoutStackTrace s

For simplicitys sake, this explanation uses the type class hierarchy

class              Functor f
class Functor m => Monad m

In Haskell, the current standard hierarchy is

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

because not only is every monad a functor, but every applicative is a functor and every monad an applicative, too.

Using the list monad, the imperative pseudocode

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

roughly translates to the do block

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

the equivalent monad comprehension

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

and the expression

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

Do notation and monad comprehensions are syntactic sugar for nested bind expressions. The bind operator is used for local name binding of monadic results.

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


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

infixl 0 &

The guard function is defined

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

where the unit type or “empty tuple”

data () = ()

Additive monads that support choice and failure can be abstracted over using a type class

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 = []
   (<|>) = (++)

where fail and <|> form a monoid forall kl m.

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

and fail is the absorbing/annihilating zero element of additive monads

_ =<< fail  =  fail

If in

guard (even p) >> return p

even p is true, then the guard produces [()] , and, by the definition of >> , the local constant function

\ _ -> return p

is applied to the result () . If false, then the guard produces the list monad's fail [] , which yields no result for a Kleisli arrow to be applied >> to.


Infamously, monads are used to encode stateful computation.

A state processor is a function

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

that transitions a state st and yields a result t . The state st can be anything. Nothing, flag, count, array, handle, machine, world.

The type of state processors is usually called

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

The state processor monad is the kinded * -> * functor State st . Kleisli arrows of the state processor monad are functions

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

In canonical Haskell, the lazy version of the state processor monad is defined

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

A state processor is run by supplying an initial state:

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

State access is provided by primitives get and put , methods of abstraction over stateful monads:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

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

m -> st declares a functional dependency of the state type st on the monad m ; that a State t , for example, will determine the state type to be t uniquely.

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

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

with the unit type used analogously to 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 is often used with record field accessors.

The state monad equivalent of the variable threading

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

where s0 :: Int , is the equally referentially transparent, but infinitely more elegant and practical

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

modify (+ 1) is a computation of type State Int () , except for its effect equivalent to return () .

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

The monad law of associativity can be written in terms of >>= forall mf g.

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


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                 }
}                    }

Like in expression-oriented programming (eg Rust), the last statement of a block represents its yield. The bind operator is sometimes called a “programmable semicolon”.

Iteration control structure primitives from structured imperative programming are emulated monadically

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


data World

The I/O world state processor monad is a reconciliation of pure Haskell and the real world, of functional denotative and imperative operational semantics. A close analogue of the actual strict implementation:

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

Interaction is facilitated by impure primitives

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

The impurity of code that uses IO primitives is permanently protocolized by the type system. Because purity is awesome, what happens in IO , stays in IO .

unsafePerformIO :: IO t -> t

Or, at least, should.

The type signature of a Haskell program

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

expands to

World -> ((), World)

A function that transforms a world.


The category whiches objects are Haskell types and whiches morphisms are functions between Haskell types is, “fast and loose”, the category Hask .

A functor T is a mapping from a category C to a category D ; for each object in C an object in D

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

and for each morphism in C a morphism in D

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

where X , Y are objects in C . HomC(X, Y) is the homomorphism class of all morphisms X -> Y in C . The functor must preserve morphism identity and composition, the “structure” of 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

The Kleisli category of a category C is given by a Kleisli triple

<T, eta, _*>

of an endofunctor

T : C -> C

( f ), an identity morphism eta ( return ), and an extension operator * ( =<< ).

Each Kleisli morphism in Hask

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

by the extension operator

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

is given a morphism in Hask 's Kleisli category

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

Composition in the Kleisli category .T is given in terms of extension

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

and satisfies the category axioms

       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

which, applying the equivalence transformations

     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 terms of extension are canonically given

               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

Monads can also be defined in terms not of Kleislian extension, but a natural transformation mu , in programming called join . A monad is defined in terms of mu as a triple over a category C , of an endofunctor

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

and two natural tranformations

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

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

satisfying the equivalences

       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

The monad type class is then defined

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

The canonical mu implementation of the option monad:

instance Monad Maybe where
   return = Just

   join (Just m) = m
   join Nothing  = Nothing

The concat function

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

is the join of the list monad.

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

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

Implementations of join can be translated from extension form using the equivalence

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

The reverse translation from mu to extension form is given by

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

But why should a theory so abstract be of any use for programming?

The answer is simple: as computer scientists, we value abstraction ! When we design the interface to a software component, we want it to reveal as little as possible about the implementation. We want to be able to replace the implementation with many alternatives, many other 'instances' of the same 'concept'. When we design a generic interface to many program libraries, it is even more important that the interface we choose have a variety of implementations. It is the generality of the monad concept which we value so highly, it is because category theory is so abstract that its concepts are so useful for programming.

It is hardly suprising, then, that the generalisation of monads that we present below also has a close connection to category theory. But we stress that our purpose is very practical: it is not to 'implement category theory', it is to find a more general way to structure combinator libraries. It is simply our good fortune that mathematicians have already done much of the work for us!

from Generalising Monads to Arrows by John Hughes

"Was ist eine Monade" zu erklären, ist ein bisschen wie "Was ist eine Nummer?" Wir benutzen immer Nummern. Aber stell dir vor, du hast jemanden getroffen, der nichts über Zahlen wusste. Wie zum Teufel würdest du erklären, was Zahlen sind? Und wie würdest du überhaupt anfangen zu beschreiben, warum das nützlich sein könnte?

Was ist eine Monade? Die kurze Antwort: Es ist eine spezielle Art, Operationen miteinander zu verketten.

Im Wesentlichen schreiben Sie Ausführungsschritte und verknüpfen sie mit der "Bindefunktion". (In Haskell heißt es >>= .) Sie können die Aufrufe für den Bindeoperator selbst schreiben, oder Sie können die Syntax Zucker verwenden, wodurch der Compiler diese Funktionsaufrufe für Sie einfügt. Wie auch immer, jeder Schritt wird durch einen Aufruf dieser Bindefunktion getrennt.

Also ist die Bindefunktion wie ein Semikolon; Es trennt die Schritte in einem Prozess. Der Job der Bind-Funktion besteht darin, die Ausgabe des vorherigen Schritts zu übernehmen und sie in den nächsten Schritt einzufügen.

Das klingt nicht zu schwer, oder? Aber es gibt mehr als eine Art von Monade. Warum? Wie?

Nun, die Bindefunktion kann das Ergebnis nur aus einem Schritt übernehmen und es dem nächsten Schritt zuführen. Aber wenn das alles ist, macht die Monade ... das ist eigentlich nicht sehr nützlich. Und das ist wichtig zu verstehen: Jede nützliche Monade macht etwas anderes, als nur eine Monade zu sein. Jede nützliche Monade hat eine "besondere Kraft", die sie einzigartig macht.

(Eine Monade, die nichts Besonderes macht, wird "Identitätsmonade" genannt. Ähnlich wie die Identitätsfunktion klingt dies wie eine absolut sinnlose Sache, stellt sich jedoch heraus, nicht zu sein ... Aber das ist eine andere Geschichte ™.)

Grundsätzlich hat jede Monade ihre eigene Implementierung der Bind-Funktion. Und Sie können eine Bindefunktion schreiben, so dass zwischen den Ausführungsschritten Dinge gebohrt werden. Beispielsweise:

  • Wenn jeder Schritt einen Erfolgs- / Fehlerindikator zurückgibt, können Sie den nächsten Schritt nur ausführen, wenn der vorherige Schritt erfolgreich war. Auf diese Weise bricht ein fehlgeschlagener Schritt die gesamte Sequenz "automatisch" ab, ohne dass Sie eine bedingte Prüfung von Ihnen durchführen müssen. (Die Fehler-Monade .)

  • Erweitern Sie diese Idee, können Sie "Ausnahmen" implementieren. (Die Fehler-Monade oder die Ausnahme-Monade .) Da Sie sie selbst definieren und nicht als Sprachfunktion, können Sie ihre Funktionsweise definieren. (Vielleicht möchten Sie die ersten beiden Ausnahmen ignorieren und nur abbrechen, wenn eine dritte Ausnahme ausgelöst wird.)

  • Sie können dafür sorgen, dass bei jedem Schritt mehrere Ergebnisse zurückgegeben werden und dass die Bindefunktion über sie verläuft, sodass Sie für jeden Schritt den nächsten Schritt ausführen können. Auf diese Weise müssen Sie nicht ständig Schleifen schreiben, wenn Sie mit mehreren Ergebnissen arbeiten. Die Bindefunktion "automatisch" erledigt das alles für Sie. (Die Liste Monade .)

  • Sie können nicht nur ein "Ergebnis" von einem Schritt an einen anderen übergeben, sondern Sie können auch zusätzliche Daten durch die Bindefunktion übergeben . Diese Daten werden jetzt nicht in Ihrem Quellcode angezeigt, Sie können jedoch von überall auf sie zugreifen, ohne sie manuell an jede Funktion übergeben zu müssen. (Der Leser Monad .)

  • Sie können es so einrichten, dass die "Extra-Daten" ersetzt werden können. Dadurch können Sie destruktive Aktualisierungen simulieren , ohne dass destruktive Aktualisierungen vorgenommen werden. (Die staatliche Monade und ihr Cousin der Schriftsteller Monad .)

  • Da Sie nur destruktive Updates simulieren , können Sie Dinge tun, die mit echten destruktiven Updates unmöglich wären. Sie können beispielsweise die letzte Aktualisierung rückgängig machen oder zu einer älteren Version zurückkehren .

  • Sie können eine Monade erstellen, in der Berechnungen angehalten werden können. So können Sie Ihr Programm pausieren, mit internen Statusdaten arbeiten und daran arbeiten und es dann fortsetzen.

  • Sie können "Fortsetzungen" als Monade implementieren. Dies ermöglicht es Ihnen, die Köpfe der Menschen zu brechen!

All das und mehr ist mit Monaden möglich. All dies ist natürlich auch ohne Monaden möglich. Es ist nur drastisch einfacher mit Monaden.

Eine Monade ist ein Datentyp mit zwei Operationen: >>= (aka bind ) und return (aka unit ). return nimmt einen beliebigen Wert und erzeugt damit eine Instanz der Monade. >>= nimmt eine Instanz der Monade und bildet eine Funktion darüber ab. (Sie können bereits sehen, dass eine Monade eine seltsame Art von Datentyp ist, da Sie in den meisten Programmiersprachen keine Funktion schreiben können, die einen beliebigen Wert annimmt und daraus einen Typ erzeugt. Monaden verwenden eine Art parametrischen Polymorphismus .)

In der Haskell-Notation wird die Monad-Schnittstelle geschrieben

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

Diese Operationen sollen bestimmten "Gesetzen" gehorchen, aber das ist nicht besonders wichtig: Die "Gesetze" kodifizieren nur die Art und Weise, wie sich sinnvolle Implementierungen der Operationen verhalten sollten (im Grunde sollten sich >>= und return darauf einigen, wie Werte transformiert werden in Monaden Instanzen und das >>= ist assoziativ).

Bei Monaden geht es nicht nur um Zustand und E / A: Sie abstrahieren ein allgemeines Berechnungsmuster, das die Arbeit mit Zustand, E / A, Ausnahmen und Nicht-Determinismus umfasst. Die wahrscheinlich einfachsten Monaden sind Listen und Optionstypen:

instance Monad [ ] where
    []     >>= k = []
    (x:xs) >>= k = k x ++ (xs >>= k)
    return x     = [x]

instance Monad Maybe where
    Just x  >>= k = k x
    Nothing >>= k = Nothing
    return x      = Just x

Dabei sind [] und : die Listenkonstruktoren, ++ ist der Verkettungsoperator und Just und Nothing sind die Maybe Konstruktoren. Diese beiden Monaden kapseln gemeinsame und nützliche Berechnungsmuster für ihre jeweiligen Datentypen ein (beachten Sie, dass nichts mit Nebenwirkungen oder E / A zu tun hat).

Sie müssen wirklich herumspielen und einen nicht-trivialen Haskell-Code schreiben, um zu verstehen, worum es bei Monaden geht und warum sie nützlich sind.

Erstens: Der Begriff Monade ist etwas leer, wenn Sie kein Mathematiker sind. Ein alternativer Begriff ist der Berechnungsgenerator, der ein wenig beschreibender ist für das, wofür er tatsächlich nützlich ist.

Sie fragen nach praktischen Beispielen:

Beispiel 1: Listenverständnis :

[x*2 | x<-[1..10], odd x]

Dieser Ausdruck gibt das Doppelte aller ungeraden Zahlen im Bereich von 1 bis 10 zurück. Sehr nützlich!

Es stellt sich heraus, dass dies wirklich nur syntaktischer Zucker für einige Operationen innerhalb der List-Monade ist. Das gleiche Listenverständnis kann geschrieben werden als:

   x <- [1..10]
   if odd x 
       then [x * 2] 
       else []

Oder auch:

[1..10] >>= (\x -> if odd x then [x*2] else [])

Beispiel 2: Eingabe / Ausgabe :

   putStrLn "What is your name?"
   name <- getLine
   putStrLn ("Welcome, " ++ name ++ "!")

Beide Beispiele verwenden Monaden, AKA-Berechnungs-Builder. Das gemeinsame Thema ist, dass die Monade Operationen auf eine bestimmte, nützliche Weise kettet. Im Listenverständnis sind die Operationen verkettet, so dass, wenn eine Operation eine Liste zurückgibt, die folgenden Operationen für jedes Element in der Liste ausgeführt werden. Die IO-Monade hingegen führt die Operationen sequentiell aus, übergibt jedoch eine "versteckte Variable", die "den Zustand der Welt" darstellt, was es uns ermöglicht, I / O-Code in einer rein funktionalen Weise zu schreiben.

Es stellt sich heraus, dass das Verkettungsmuster sehr nützlich ist und in Haskell für viele verschiedene Dinge verwendet wird.

Ein anderes Beispiel sind Ausnahmen: Mit der Error Monade werden Operationen verkettet, so dass sie sequentiell ausgeführt werden, außer wenn ein Fehler ausgelöst wird. In diesem Fall wird der Rest der Kette abgebrochen.

Sowohl die Liste-Verständnis-Syntax als auch die Do-Notation sind syntaktische Zucker für Verkettungsoperationen unter Verwendung des >>= -Operators. Eine Monade ist im Grunde nur ein Typ, der den >>= Operator unterstützt.

Beispiel 3: Ein Parser

Dies ist ein sehr einfacher Parser, der entweder einen String in Anführungszeichen oder eine Zahl analysiert:

parseExpr = parseString <|> parseNumber

parseString = do
        char '"'
        x <- many (noneOf "\"")
        char '"'
        return (StringValue x)

parseNumber = do
    num <- many1 digit
    return (NumberValue (read num))

Die Operationen char , digit usw. sind ziemlich einfach. Sie stimmen entweder überein oder stimmen nicht überein. Die Magie ist die Monade, die den Kontrollfluss verwaltet: Die Operationen werden sequenziell ausgeführt, bis eine Übereinstimmung fehlschlägt. In diesem Fall rückt die Monade zum letzten <|> und versucht die nächste Option. Wieder eine Verkettung von Operationen mit einigen nützlichen Semantiken.

Beispiel 4: Asynchrone Programmierung

Die obigen Beispiele sind in Haskell, aber es stellt sich heraus, dass F# auch Monaden unterstützt. Dieses Beispiel wurde von Don Syme gestohlen:

let AsyncHttp(url:string) =
    async {  let req = WebRequest.Create(url)
             let! rsp = req.GetResponseAsync()
             use stream = rsp.GetResponseStream()
             use reader = new System.IO.StreamReader(stream)
             return reader.ReadToEnd() }

Diese Methode ruft eine Webseite ab. Die Pointe ist die Verwendung von GetResponseAsync - sie wartet auf die Antwort in einem separaten Thread, während der Hauptthread von der Funktion zurückkehrt. Die letzten drei Zeilen werden auf dem erzeugten Thread ausgeführt, wenn die Antwort empfangen wurde.

In den meisten anderen Sprachen müssten Sie explizit eine separate Funktion für die Zeilen erstellen, die die Antwort verarbeiten. Die async Monade kann den Block selbst "aufteilen" und die Ausführung der zweiten Hälfte verschieben. (Die Syntax async {} gibt an, dass der Kontrollfluss im Block durch die async Monade definiert ist.)

Wie sie arbeiten

Wie kann also eine Monade all diese phantastischen Kontrollfluss-Dinge tun? Was tatsächlich in einem Do-Block (oder einem Berechnungsausdruck, wie sie in F # genannt werden) passiert, ist, dass jede Operation (im Grunde jede Zeile) in eine separate anonyme Funktion eingeschlossen ist. Diese Funktionen werden dann mit dem bind kombiniert (buchstabiert >>= in Haskell). Da die bind Funktionen kombiniert, kann sie sie so ausführen, wie sie es für richtig halten: nacheinander, mehrmals, in umgekehrter Reihenfolge, einige verwerfen, einige in einem separaten Thread ausführen, wenn es sich anfühlt und so weiter.

Als Beispiel ist dies die erweiterte Version des IO-Codes aus Beispiel 2:

putStrLn "What is your name?"
>>= (\_ -> getLine)
>>= (\name -> putStrLn ("Welcome, " ++ name ++ "!"))

Das ist hässlicher, aber es ist auch offensichtlicher, was eigentlich vor sich geht. Der >>= Operator ist die magische Zutat: Er nimmt einen Wert (auf der linken Seite) und kombiniert ihn mit einer Funktion (auf der rechten Seite), um einen neuen Wert zu erzeugen. Dieser neue Wert wird dann vom nächsten >>= Operator übernommen und erneut mit einer Funktion kombiniert, um einen neuen Wert zu erzeugen. >>= kann als Mini-Evaluator angesehen werden.

Beachten Sie, dass >>= für verschiedene Typen überladen ist, also hat jede Monade eine eigene Implementierung von >>= . (Alle Operationen in der Kette müssen vom Typ der gleichen Monade sein, ansonsten funktioniert der >>= Operator nicht.)

Die einfachste mögliche Implementierung von >>= nimmt nur den Wert auf der linken Seite und wendet ihn auf die Funktion auf der rechten Seite an und gibt das Ergebnis zurück, aber wie gesagt, macht das ganze Muster nützlich, wenn etwas in der monad's Umsetzung von >>= .

Es gibt einige zusätzliche Klugheit darin, wie die Werte von einer Operation zur nächsten weitergegeben werden, aber dies erfordert eine tiefere Erklärung des Haskell-Typ-Systems.


In Haskell-Termen ist eine Monade ein parametrisierter Typ, der eine Instanz der Monad-Typklasse ist, die >>= zusammen mit einigen anderen Operatoren definiert. Für Laien ist eine Monade nur ein Typ, für den die Operation >>= definiert ist.

An sich >>= ist nur eine mühsame Art der Verkettung von Funktionen, aber mit der Anwesenheit der Do-Notation, die die "Klempnerarbeit" verbirgt, erweist sich die monadische Operation als eine sehr nette und nützliche Abstraktion, nützlich viele Orte in der Sprache , und nützlich für die Erstellung Ihrer eigenen Mini-Sprachen in der Sprache.

Warum sind Monaden hart?

Für viele Haskell-Lernende sind Monaden ein Hindernis, das sie wie eine Ziegelmauer treffen. Es ist nicht so, dass Monaden selbst komplex sind, sondern dass die Implementierung auf vielen anderen erweiterten Haskell-Funktionen wie parametrisierten Typen, Typklassen usw. basiert. Das Problem ist, dass Haskell I / O auf Monaden basiert, und I / O ist wahrscheinlich eines der ersten Dinge, die Sie beim Lernen einer neuen Sprache verstehen wollen - schließlich macht es nicht viel Spaß, Programme zu erstellen, die keine erzeugen Ausgabe. Ich habe keine unmittelbare Lösung für dieses Henne-und-Ei-Problem, außer I / O wie "Magie passiert hier" zu behandeln, bis Sie genug Erfahrung mit anderen Teilen der Sprache haben. Es tut uns leid.

Ausgezeichneter Blog auf Monaden: http://adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html

Nach langem Bemühen glaube ich, die Monade zu verstehen. Nachdem ich meine eigene langwierige Kritik an der überwältigend gut gewählten Antwort noch einmal gelesen habe, werde ich diese Erklärung anbieten.

Es gibt drei Fragen, die beantwortet werden müssen, um Monaden zu verstehen:

  1. Warum brauchst du eine Monade?
  2. Was ist eine Monade?
  3. Wie wird eine Monade implementiert?

Wie ich in meinen ursprünglichen Kommentaren angemerkt habe, werden zu viele Monade-Erklärungen in Frage Nr. 3, ohne und vor der richtigen Beantwortung von Frage 2 oder Frage 1, aufgegriffen.

Warum brauchst du eine Monade?

Reine funktionale Sprachen wie Haskell unterscheiden sich von imperativen Sprachen wie C oder Java darin, dass ein reines funktionales Programm nicht notwendigerweise in einer bestimmten Reihenfolge Schritt für Schritt ausgeführt wird. Ein Haskell-Programm ähnelt eher einer mathematischen Funktion, in der Sie die "Gleichung" in einer beliebigen Anzahl potentieller Ordnungen lösen können. Dies bringt eine Reihe von Vorteilen, unter anderem, dass es die Möglichkeit bestimmter Arten von Fehlern beseitigt, insbesondere solche, die sich auf Dinge wie "Staat" beziehen.

Es gibt jedoch bestimmte Probleme, die mit dieser Art der Programmierung nicht so einfach zu lösen sind. Manche Dinge, wie die Konsolenprogrammierung und Datei-E / A, müssen in einer bestimmten Reihenfolge ausgeführt werden oder müssen den Status beibehalten. Eine Möglichkeit, mit diesem Problem umzugehen, besteht darin, eine Art Objekt zu erstellen, das den Status einer Berechnung darstellt, und eine Reihe von Funktionen, die ein Zustandsobjekt als Eingabe annehmen und ein neues modifiziertes Zustandsobjekt zurückgeben.

So let's create a hypothetical "state" value, that represents the state of a console screen. exactly how this value is constructed is not important, but let's say it's an array of byte length ascii characters that represents what is currently visible on the screen, and an array that represents the last line of input entered by the user, in pseudocode. We've defined some functions that take console state, modify it, and return a new console state.

consolestate MyConsole = new consolestate;

So to do console programming, but in a pure functional manner, you would need to nest a lot of function calls inside eachother.

consolestate FinalConsole = print(input(print(myconsole, "Hello, what's your name?")),"hello, %inputbuffer%!");

Programming in this way keeps the "pure" functional style, while forcing changes to the console to happen in a particular order. But, we'll probably want to do more than just a few operations at a time like in the above example. Nesting functions in that way will start to become ungainly. What we want, is code that does essentially the same thing as above, but is written a bit more like this:

consolestate FinalConsole = myconsole:
                            print("Hello, what's your name?"):
                            print("hello, %inputbuffer%!");

This would indeed be a more convenient way to write it. How do we do that though?

What is a monad?

Once you have a type (such as consolestate ) that you define along with a bunch of functions designed specifically to operate on that type, you can turn the whole package of these things into a "monad" by defining an operator like : (bind) that automatically feeds return values on its left, into function parameters on its right, and a lift operator that turns normal functions, into functions that work with that specific kind of bind operator.

How is a monad implemented?

See other answers, that seem quite free to jump into the details of that.

Sie sollten zuerst verstehen, was ein Funktor ist. Vorher verstehen Sie Funktionen höherer Ordnung.

Eine Funktion höherer Ordnung ist einfach eine Funktion, die eine Funktion als Argument verwendet.

Ein Funktor ist eine beliebige Typkonstruktion T für die eine Funktion höherer Ordnung existiert, nennen wir sie map , die eine Funktion vom Typ a -> b (gegeben durch zwei beliebige Typen a und b ) in eine Funktion T a -> T b transformiert. Diese map Funktion muss auch die Gesetze der Identität und Zusammensetzung beachten, damit die folgenden Ausdrücke für alle x , p und q (Haskell-Notation) wahr sind:

map id = id
map (p . q) = map p . map q

Zum Beispiel ist ein Typenkonstruktor namens List ein Funktor, wenn er mit einer Funktion vom Typ (a -> b) -> List a -> List b die den oben genannten Gesetzen entspricht. Die einzige praktische Implementierung ist offensichtlich. Die resultierende Funktion List a -> List b iteriert über die angegebene Liste, ruft die Funktion (a -> b) für jedes Element auf und gibt die Liste der Ergebnisse zurück.

Eine Monade ist im Wesentlichen nur ein Funktor T mit zwei zusätzlichen Methoden, join , vom Typ T (T a) -> T a , und unit (manchmal als return , fork oder pure ) vom Typ a -> T a . Für Listen in Haskell:

join :: [[a]] -> [a]
pure :: a -> [a]

Warum ist das nützlich? Weil Sie beispielsweise eine Liste mit einer Funktion map die eine Liste zurückgibt. Join nimmt die resultierende Liste von Listen und verkettet sie. List ist eine Monade, weil das möglich ist.

Sie können eine Funktion schreiben, die map und dann join . Diese Funktion heißt bind oder flatMap oder (>>=) oder (=<<) . Normalerweise wird eine Monad-Instanz in Haskell angegeben.

Eine Monade muss bestimmte Gesetze erfüllen, nämlich dass join assoziativ sein muss. Das heißt, wenn Sie einen Wert x vom Typ [[[a]]] dann sollte join (join x) gleich join (map join x) . Und pure muss eine Identität für join so sein, dass join (pure x) == x .

Monads Are Not Metaphors , but a practically useful abstraction emerging from a common pattern, as Daniel Spiewak explains.

A monad is a way of combining computations together that share a common context. It is like building a network of pipes. When constructing the network, there is no data flowing through it. But when I have finished piecing all the bits together with 'bind' and 'return' then I invoke something like runMyMonad monad data and the data flows through the pipes.

A monad is, effectively, a form of "type operator". It will do three things. First it will "wrap" (or otherwise convert) a value of one type into another type (typically called a "monadic type"). Secondly it will make all the operations (or functions) available on the underlying type available on the monadic type. Finally it will provide support for combining its self with another monad to produce a composite monad.

The "maybe monad" is essentially the equivalent of "nullable types" in Visual Basic / C#. It takes a non nullable type "T" and converts it into a "Nullable<T>", and then defines what all the binary operators mean on a Nullable<T>.

Side effects are represented simillarly. A structure is created that holds descriptions of side effects alongside a function's return value. The "lifted" operations then copy around side effects as values are passed between functions.

They are called "monads" rather than the easier-to-grasp name of "type operators" for several reasons:

  1. Monads have restrictions on what they can do (see the definiton for details).
  2. Those restrictions, along with the fact that there are three operations involved, conform to the structure of something called a monad in Category Theory, which is an obscure branch of mathematics.
  3. They were designed by proponents of "pure" functional languages
  4. Proponents of pure functional languages like obscure branches of mathematics
  5. Because the math is obscure, and monads are associated with particular styles of programming, people tend to use the word monad as a sort of secret handshake. Because of this no one has bothered to invest in a better name.

I am still new to monads, but I thought I would share a link I found that felt really good to read (WITH PICTURES!!): http://www.matusiak.eu/numerodix/blog/2012/3/11/monads-for-the-layman/ (no affiliation)

Basically, the warm and fuzzy concept that I got from the article was the concept that monads are basically adapters that allow disparate functions to work in a composable fashion, ie be able to string up multiple functions and mix and match them without worrying about inconsistent return types and such. So the BIND function is in charge of keeping apples with apples and oranges with oranges when we're trying to make these adapters. And the LIFT function is in charge of taking "lower level" functions and "upgrading" them to work with BIND functions and be composable as well.

I hope I got it right, and more importantly, hope that the article has a valid view on monads. If nothing else, this article helped whet my appetite for learning more about monads.

I wrote this mostly for me but I hope others find it useful :)

In Summary

A monad is merely custom function composition utilizing a wrapping type to hold stateful/meta information that guides the composition. Interestingly, imperative execution is itself function composition wherein the wrapping type holds whether an exception has occurred, the presence of which aborts further composition. The monadic laws serve to ensure a monad only performs the equivalent of function composition over the wrapped value.

A Little Context

Imperative code is a sequence of instructions performed consecutively while functional code is actually an expression whose order of evaluation is ultimately on an as needed basis. Consequently, an imperative program evaluates each statement fully before proceeding to the next one while a functional program catalogs any preceding subexpression then evaluates the last one to generate a result, at which point any necessary preceding subexpressions are evaluated. (Most functional languages do resolve subexpressions into values as they are encountered with a few, notably Haskell, being the exception).

What Does That Have To Do With Monads

It turns out that imperative evaluation and "expression" evaluation are equivalent. Namely, the performance of an evaluation of an expression at any specific time can be described as the sequential evaluation of its subexpressions. Similarly, any sequential execution of statements can be considered an instance of such an expression being evaluated especially if you generalize the notion of return value to be any modification to the application state as oppose to merely formal return values. To the point, all imperative code can be considered a specific ordered evaluation of some equivalent expression (over the application state).

Still, What Does All That Have To Do With Monads

An expression is a composition of functions and a monad is a technique for customizing the composition of functions. Per convention, it is a function called, bind , that composes (binds) two functions ( bind fg = (x) => g(fx) ) within some umbrella type that holds a context or state guiding the binding process. This context allows the associated implementation of bind to massage the composition. In the case of, Result 'a , context that hold an error message or a actual value it would permit the bind to log errors of the preceding result and aborts or continue the composition with a default value, depending on design. Selective application of the subsequent function to be composed is the key facility of monads in that the application process is not blind, unlike silly imperative code. :)

In a monad, the functions to be composed are defined to receive a non-monadic or unwrapped value but return a monadic or wrapped value. An example of one such naturally occurring function is the division operator ( / ) which accepts numbers but may return undefined if the divisor is 0 . Since undefined is not a number, \ , actually returns a type whose value range is large than a number since it includes all numbers plus undefined .

I suspect this asymmetry, where operators require valid values but may return invalid ones, is a key pragmatic aspect of monads that make them useful but difficult to explain and justify; while imperative coders accept constant result checking as a necessary evil, functional coders use bind over a suitable wrapper type to detect and manage exceptions or invalid results

While being a composition function, nonetheless, for pragmatic reasons bind is described as receiving the result of the first function, a wrapped value, that it then selectively applies to the second function whose result it then collects and returns as its result. Consequently, binds can themselves be composed.

For a complex example, a monad can take a sequence of asynchronous results as a preceding value and apply each to the provided composing function in parallel with respect to the available processors, then collect and return their results as they occur, for instance. All this functionality is in that specific implementation of that monad's bind function; however, there are typically ancillary functions that cooperate, in particular lift with wraps a value into a default instance of the monadic type such as, lift 1 = Just 1 in the case of the Maybe monad, for participation in monadic expressions. (In Haskell, a monad is strongly associated with the wrapper type because monads are implemented using its type class mechanisms whereas in F# the implementation uses defined computations expression instances)

Are you saying that...

...a monad is just custom function composition using a wrapping type to hold stateful information that the bind or composing function or operator uses in determining whether and how to perform the application of the next function. Ja.

What About The Monadic Laws?

The monadic laws only seek to ensure that a monad implementation only performs the equivalent of function composition over the wrapped type. It does that by ensuring certain equivalences hold per the expectation of composing those two functions over the wrapped type.

That's it I think. Hope it helps some.

I believe this is nice a nice treatment in another of response .

In addition to the excellent answers above, let me offer you a link to the following article (by Patrick Thomson) which explains monads by relating the concept to the JavaScript library jQuery (and its way of using "method chaining" to manipulate the DOM): jQuery is a Monad

The jQuery documentation itself doesn't refer to the term "monad" but talks about the "builder pattern" which is probably more familiar. This doesn't change the fact that you have a proper monad there maybe without even realizing it.

In the context of Scala you will find the following to be the simplest definition. Basically flatMap (or bind) is 'associative' and there exists an identity.

trait M[+A] {
  def flatMap[B](f: A => M[B]): M[B] // AKA bind

  // Pseudo Meta Code
  def isValidMonad: Boolean = {
    // for every parameter the following holds
    def isAssociativeOn[X, Y, Z](x: M[X], f: X => M[Y], g: Y => M[Z]): Boolean =
      x.flatMap(f).flatMap(g) == x.flatMap(f(_).flatMap(g))

    // for every parameter X and x, there exists an id
    // such that the following holds
    def isAnIdentity[X](x: M[X], id: X => M[X]): Boolean =
      x.flatMap(id) == x


// These could be any functions
val f: Int => Option[String] = number => if (number == 7) Some("hello") else None
val g: String => Option[Double] = string => Some(3.14)

// Observe these are identical. Since Option is a Monad 
// they will always be identical no matter what the functions are
scala> Some(7).flatMap(f).flatMap(g)
res211: Option[Double] = Some(3.14)

scala> Some(7).flatMap(f(_).flatMap(g))
res212: Option[Double] = Some(3.14)

// As Option is a Monad, there exists an identity:
val id: Int => Option[Int] = x => Some(x)

// Observe these are identical
scala> Some(7).flatMap(id)
res213: Option[Int] = Some(7)

scala> Some(7)
res214: Some[Int] = Some(7)

NOTE Strictly speaking the definition of a Monad in functional programming is not the same as the definition of a Monad in Category Theory , which is defined in turns of map and flatten . Though they are kind of equivalent under certain mappings. This presentations is very good: http://www.slideshare.net/samthemonad/monad-presentation-scala-as-a-category

Monoid appears to be something that ensures that all operations defined on a Monoid and a supported type will always return a supported type inside the Monoid. Eg, Any number + Any number = A number, no errors.

Whereas division accepts two fractionals, and returns a fractional, which defined division by zero as Infinity in haskell somewhy(which happens to be a fractional somewhy)...

In any case, it appears Monads are just a way to ensure that your chain of operations behaves in a predictable way, and a function that claims to be Num -> Num, composed with another function of Num->Num called with x does not say, fire the missiles.

On the other hand, if we have a function which does fire the missiles, we can compose it with other functions which also fire the missiles, because our intent is clear -- we want to fire the missiles -- but it won't try printing "Hello World" for some odd reason.

In Haskell, main is of type IO (), or IO [()], the distiction is strange and I will not discuss it but here's what I think happens:

If I have main, I want it to do a chain of actions, the reason I run the program is to produce an effect -- usually though IO. Thus I can chain IO operations together in main in order to -- do IO, nothing else.

If I try to do something which does not "return IO", the program will complain that the chain does not flow, or basically "How does this relate to what we are trying to do -- an IO action", it appears to force the programmer to keep their train of thought, without straying off and thinking about firing the missiles, while creating algorithms for sorting -- which does not flow.

Basically, Monads appear to be a tip to the compiler that "hey, you know this function that returns a number here, it doesn't actually always work, it can sometimes produce a Number, and sometimes Nothing at all, just keep this in mind". Knowing this, if you try to assert a monadic action, the monadic action may act as a compile time exception saying "hey, this isn't actually a number, this CAN be a number, but you can't assume this, do something to ensure that the flow is acceptable." which prevents unpredictable program behavior -- to a fair extent.

It appears monads are not about purity, nor control, but about maintaining an identity of a category on which all behavior is predictable and defined, or does not compile. You cannot do nothing when you are expected to do something, and you cannot do something if you are expected to do nothing (visible).

The biggest reason I could think of for Monads is -- go look at Procedural/OOP code, and you will notice that you do not know where the program starts, nor ends, all you see is a lot of jumping and a lot of math,magic,and missiles. You will not be able to maintain it, and if you can, you will spend quite a lot of time wrapping your mind around the whole program before you can understand any part of it, because modularity in this context is based on interdependant "sections" of code, where code is optimized to be as related as possible for promise of efficiency/inter-relation. Monads are very concrete, and well defined by definition, and ensure that the flow of program is possible to analyze, and isolate parts which are hard to analyze -- as they themselves are monads. A monad appears to be a "comprehensible unit which is predictable upon its full understanding" -- If you understand "Maybe" monad, there's no possible way it will do anything except be "Maybe", which appears trivial, but in most non monadic code, a simple function "helloworld" can fire the missiles, do nothing, or destroy the universe or even distort time -- we have no idea nor have any guarantees that IT IS WHAT IT IS. A monad GUARANTEES that IT IS WHAT IT IS. which is very powerful.

All things in "real world" appear to be monads, in the sense that it is bound by definite observable laws preventing confusion. This does not mean we have to mimic all the operations of this object to create classes, instead we can simply say "a square is a square", nothing but a square, not even a rectangle nor a circle, and "a square has area of the length of one of it's existing dimensions multiplied by itself. No matter what square you have, if it's a square in 2D space, it's area absolutely cannot be anything but its length squared, it's almost trivial to prove. This is very powerful because we do not need to make assertions to make sure that our world is the way it is, we just use implications of reality to prevent our programs from falling off track.

Im pretty much guaranteed to be wrong but I think this could help somebody out there, so hopefully it helps somebody.

My favorite Monad tutorial:


(out of 170,000 hits on a Google search for "monad tutorial"!)

@Stu: The point of monads is to allow you to add (usually) sequential semantics to otherwise pure code; you can even compose monads (using Monad Transformers) and get more interesting and complicated combined semantics, like parsing with error handling, shared state, and logging, for example. All of this is possible in pure code, monads just allow you to abstract it away and reuse it in modular libraries (always good in programming), as well as providing convenient syntax to make it look imperative.

Haskell already has operator overloading[1]: it uses type classes much the way one might use interfaces in Java or C# but Haskell just happens to also allow non-alphanumeric tokens like + && and > as infix identifiers. It's only operator overloading in your way of looking at it if you mean "overloading the semicolon" [2]. It sounds like black magic and asking for trouble to "overload the semicolon" (picture enterprising Perl hackers getting wind of this idea) but the point is that without monads there is no semicolon, since purely functional code does not require or allow explicit sequencing.

This all sounds much more complicated than it needs to. sigfpe's article is pretty cool but uses Haskell to explain it, which sort of fails to break the chicken and egg problem of understanding Haskell to grok Monads and understanding Monads to grok Haskell.

[1] This is a separate issue from monads but monads use Haskell's operator overloading feature.

[2] This is also an oversimplification since the operator for chaining monadic actions is >>= (pronounced "bind") but there is syntactic sugar ("do") that lets you use braces and semicolons and/or indentation and newlines.

The two things that helped me best when learning about there were:

Chapter 8, "Functional Parsers," from Graham Hutton's book Programming in Haskell . This doesn't mention monads at all, actually, but if you can work through chapter and really understand everything in it, particularly how a sequence of bind operations is evaluated, you'll understand the internals of monads. Expect this to take several tries.

The tutorial All About Monads . This gives several good examples of their use, and I have to say that the analogy in Appendex I worked for me.

This answer begins with a motivating example, works through the example, derives an example of a monad, and formally defines "monad".

Consider these three functions in pseudocode:

f(<x, messages>) := <x, messages "called f. ">
g(<x, messages>) := <x, messages "called g. ">
wrap(x)          := <x, "">

f takes an ordered pair of the form <x, messages> and returns an ordered pair. It leaves the first item untouched and appends "called f. " to the second item. Same with g .

You can compose these functions and get your original value, along with a string that shows which order the functions were called in:

= f(g(<x, "">))
= f(<x, "called g. ">)
= <x, "called g. called f. ">

You dislike the fact that f and g are responsible for appending their own log messages to the previous logging information. (Just imagine for the sake of argument that instead of appending strings, f and g must perform complicated logic on the second item of the pair. It would be a pain to repeat that complicated logic in two -- or more -- different functions.)

You prefer to write simpler functions:

f(x)    := <x, "called f. ">
g(x)    := <x, "called g. ">
wrap(x) := <x, "">

But look at what happens when you compose them:

= f(g(<x, "">))
= f(<<x, "">, "called g. ">)
= <<<x, "">, "called g. ">, "called f. ">

The problem is that passing a pair into a function does not give you what you want. But what if you could feed a pair into a function:

  feed(f, feed(g, wrap(x)))
= feed(f, feed(g, <x, "">))
= feed(f, <x, "called g. ">)
= <x, "called g. called f. ">

Read feed(f, m) as "feed m into f ". To feed a pair <x, messages> into a function f is to pass x into f , get <y, message> out of f , and return <y, messages message> .

feed(f, <x, messages>) := let <y, message> = f(x)
                          in  <y, messages message>

Notice what happens when you do three things with your functions:

First: if you wrap a value and then feed the resulting pair into a function:

  feed(f, wrap(x))
= feed(f, <x, "">)
= let <y, message> = f(x)
  in  <y, "" message>
= let <y, message> = <x, "called f. ">
  in  <y, "" message>
= <x, "" "called f. ">
= <x, "called f. ">
= f(x)

That is the same as passing the value into the function.

Second: if you feed a pair into wrap :

  feed(wrap, <x, messages>)
= let <y, message> = wrap(x)
  in  <y, messages message>
= let <y, message> = <x, "">
  in  <y, messages message>
= <x, messages "">
= <x, messages>

That does not change the pair.

Third: if you define a function that takes x and feeds g(x) into f :

h(x) := feed(f, g(x))

and feed a pair into it:

  feed(h, <x, messages>)
= let <y, message> = h(x)
  in  <y, messages message>
= let <y, message> = feed(f, g(x))
  in  <y, messages message>
= let <y, message> = feed(f, <x, "called g. ">)
  in  <y, messages message>
= let <y, message> = let <z, msg> = f(x)
                     in  <z, "called g. " msg>
  in <y, messages message>
= let <y, message> = let <z, msg> = <x, "called f. ">
                     in  <z, "called g. " msg>
  in <y, messages message>
= let <y, message> = <x, "called g. " "called f. ">
  in <y, messages message>
= <x, messages "called g. " "called f. ">
= feed(f, <x, messages "called g. ">)
= feed(f, feed(g, <x, messages>))

That is the same as feeding the pair into g and feeding the resulting pair into f .

You have most of a monad. Now you just need to know about the data types in your program.

What type of value is <x, "called f. "> ? Well, that depends on what type of value x is. If x is of type t , then your pair is a value of type "pair of t and string". Call that type M t .

M is a type constructor: M alone does not refer to a type, but M _ refers to a type once you fill in the blank with a type. An M int is a pair of an int and a string. An M string is a pair of a string and a string. Etc.

Congratulations, you have created a monad!

Formally, your monad is the tuple <M, feed, wrap> .

A monad is a tuple <M, feed, wrap> where:

  • M is a type constructor.
  • feed takes a (function that takes a t and returns an M u ) and an M t and returns an M u .
  • wrap takes a v and returns an M v .

t , u , and v are any three types that may or may not be the same. A monad satisfies the three properties you proved for your specific monad:

  • Feeding a wrapped t into a function is the same as passing the unwrapped t into the function.

    Formally: feed(f, wrap(x)) = f(x)

  • Feeding an M t into wrap does nothing to the M t .

    Formally: feed(wrap, m) = m

  • Feeding an M t (call it m ) into a function that

    • passes the t into g
    • gets an M u (call it n ) from g
    • feeds n into f

    ist das gleiche wie

    • feeding m into g
    • getting n from g
    • feeding n into f

    Formally: feed(h, m) = feed(f, feed(g, m)) where h(x) := feed(f, g(x))

Typically, feed is called bind (AKA >>= in Haskell) and wrap is called return .