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 HaskellJoachim Breitner16. November 2010Haskell vs. KategorientheorieEine Monade in Haskell ist eine Typklasse mit zwei Methoden:class Monad m where(=) :: m a (a m b) m breturn :: a m awobei 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 wreclass Monad m wheremap :: (a b) m a m breturn :: a m ajoin :: m (m a) m awobei 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 kannmap 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/MATH198http://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 MonadenzooIm folgenden die bekanntesten Haskell-Monaden, in etwas liberalerer Syntax.Maybe(Modelliert: partielle Funktionen, Berechnungenmit Fehlerzustnden)data Maybe a = Just a | Nothinginstance Monad Maybe wherereturn = Just(Just x) = k = k xNothing = k = NothingEither e(Modelliert: Berechnungen mit Fehlermeldun-gen)data Either e a = Left e | Right ainstance Monad (Either e) wherereturn = Right(Left e) = k = Left e(Right x) = k = k x[](Liste. Modelliert: Nichtdeterminismus)data [a] = a:[a] | [ ]instance Monad [ ] wherereturn 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) wherereturn x = r xm = k = r k (m r) rWriter m(Schreiber-Monade. Modelliert: Protokollierung.(M,e,) muss ein Monoid sein.)type Writer m a = (m,a)instance Monoid m Monad Writer wherereturn 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 wherereturn x = s (x,s)m = k = s let (y, s) = m sin k y sCont r(Fortfhrungs-Monade. Modelliert Sprnge imProgrammablauf)type Cont r a = (a r) rinstance Monad (Cont r) wherereturn x = c c xm = k = c m (a k a c)Identity(Modelliert: reine Funktionen)type Identity a = ainstance Monad Identity wherereturn = idm = k = k mIO(Modelliert: Berechnungen, die mit der ech-ten Welt kommunizieren, etwa Dateizugriffe.Implementierung ist Compiler-Geheimnis!)type IO = ?instance Monad IO wherereturn = ?m = k = ?Do-NotationHaskell untersttzt eine spezielle Syntax frmonadische Berechnungen. So steht etwamain = do x getLineputStr ("You said " ++ x)return 3frmain = getLine = (x (putStr ("You said " ++ x) = (_ return 3))).