Monaden in Haskell - ? Monaden in Haskell Joachim Breitner 16.November2010 Haskell vs. Kategorientheorie

Download Monaden in Haskell - ? Monaden in Haskell Joachim Breitner 16.November2010 Haskell vs. Kategorientheorie

Post on 14-Sep-2018

212 views

Category:

Documents

0 download

TRANSCRIPT

  • Monaden in Haskell

    Joachim Breitner

    16. November 2010

    Haskell vs. Kategorientheorie

    Eine Monade in Haskell ist eine Typklasse mit zwei Methoden:

    class Monad m where(=) :: m a (a m b) m breturn :: a m a

    wobei die folgenden Beziehungen gelten sollten:

    return x = f f xa = return a

    (a = f) = g a = (x f x = g).

    Eine Formulierung der blichen Monaden-Definition fr Haskell wre

    class Monad m wheremap :: (a b) m a m breturn :: a m ajoin :: m (m a) m a

    wobei m Typen auf Typen abbildet, also zusammen mit map einen FunktorHask Hask definiert.Es entspricht weiter return dem und join dem .

    Aus den Bedingungen dass und natrliche Transformationen sind, sowie den zwei definierendenkommutativen Diagrammen erhalten wir in Haskell-Schreibweise folgende Eigenschaften:

    map g return return gmap g join join map (map g)

    join map join join joinjoin return join map return id.

    Die beiden Definitionen sind quivalent. Man kann

    map f = (a a = (return f))join a = a = id bzw. a = f = join (map f a)

    definieren und nachrechnen, dass die obigen Bedingungen ineinander bergehen.

    Quellen: http://www.haskell.org/haskellwiki/Category_theory/Monadshttp://www.haskell.org/haskellwiki/User:Michiexile/MATH198

    http://www.haskell.org/all_about_monads/http://comonad.com/reader/

    http://www.haskell.org/haskellwiki/Category_theory/Monadshttp://www.haskell.org/haskellwiki/User:Michiexile/MATH198http://www.haskell.org/all_about_monads/http://comonad.com/reader/

  • Ein kleiner Monadenzoo

    Im folgenden die bekanntesten Haskell-Monaden, in etwas liberalerer Syntax.

    Maybe(Modelliert: partielle Funktionen, Berechnungenmit Fehlerzustnden)

    data Maybe a = Just a | Nothinginstance Monad Maybe where

    return = Just(Just x) = k = k xNothing = k = Nothing

    Either e(Modelliert: Berechnungen mit Fehlermeldun-gen)

    data Either e a = Left e | Right ainstance Monad (Either e) where

    return = Right(Left e) = k = Left e(Right x) = k = k x

    [](Liste. Modelliert: Nichtdeterminismus)

    data [a] = a:[a] | [ ]instance Monad [ ] where

    return x = [x][ ] = k = [ ](x:xs) = k = k x ++ (xs = k)

    Reader r(Leser-Monade. Modelliert: Kontextinformatio-nen)

    type Reader r a = r ainstance Monad (Reader r) where

    return x = r xm = k = r k (m r) r

    Writer m(Schreiber-Monade. Modelliert: Protokollierung.(M,e,) muss ein Monoid sein.)

    type Writer m a = (m,a)instance Monoid m Monad Writer where

    return x = (e, x)m = k = let (m, y) = m

    (m, z) = k ain (m m, z)

    State s(Zustands-Monade. Modelliert: Berechnungenmit Zustand)

    type State s a = s (a,s)instance State s where

    return x = s (x,s)m = k = s let (y, s) = m s

    in k y s

    Cont r(Fortfhrungs-Monade. Modelliert Sprnge imProgrammablauf)

    type Cont r a = (a r) rinstance Monad (Cont r) where

    return x = c c xm = k = c m (a k a c)

    Identity(Modelliert: reine Funktionen)

    type Identity a = ainstance Monad Identity where

    return = idm = k = k m

    IO(Modelliert: Berechnungen, die mit der ech-ten Welt kommunizieren, etwa Dateizugriffe.Implementierung ist Compiler-Geheimnis!)

    type IO = ?instance Monad IO where

    return = ?m = k = ?

    Do-NotationHaskell untersttzt eine spezielle Syntax frmonadische Berechnungen. So steht etwa

    main = do x getLineputStr ("You said " ++ x)return 3

    fr

    main = getLine = (x (putStr ("You said " ++ x) = (_ return 3))).