Funktionale Programmierung: Monaden

Literatur	LYAH: A Fistful of Monads
	LYAH: Input and Output

Sequenz	von Berechnungen komponieren

?	Gibt es neben fmap, pure und (<*>) noch andere gleiche Eigenschaften (Operationen) für verschiedene Typkonstruktoren
	Ja, das hintereinander Ausführen von Berechnungen.
Beispiele	für einstellige Typkonstruktoren (Konstruktoren mit einem Typparameter)
	Maybe . [.] Either String . data D a = ... newtype StateT a = ST ( State -> (a, State ) ) newtype Parser a = P ( String -> (a, String) )

	Ähnlichkeiten mit den Beispielen für die Funktoren sind nicht rein zufällig.
1. Beispiel
Maybe	-- gegeben f1, f2, f3 f1 :: a -> Maybe b f2 :: b -> Maybe c f3 :: c -> Maybe d

Wunsch	aber leider kein korrektes Programm
	f :: a -> Maybe d f x = f3 (f2 (f1 x)) -- oder f = f3 . f2 . f1

Realität	f x = case f1 x of Nothing -> Nothing Just x1 -> case f2 x1 of Nothing -> Nothing Just x2 -> f3 x2

?	Problem bei der Kombination der Berechnungen f1, f2, f3?
	Es wird neben der reinen Komposition noch etwas mehr gemacht.

2. Beispiel	Zustandsbehaftete Berechnung
	Jede Funktion arbeitet zusätzlich zu den Parametern auf einem Programmzustand, d.h. in der Funktion wird ein Zustand (ein Wert) gelesen (genutzt) und als zusätzliches Resultat ein neuer Zustand berechnet.
gegeben	type State = ... -- oder data State = ... f1 :: a -> State -> (b, State) f2 :: b -> State -> (c, State) f3 :: c -> State -> (d, State)

gesucht	f :: a -> State -> (d, State)

Wunsch	aber falsch:
	f x = \ s0 -> f3 (f2 (f1 x s0)) f x = \ s0 -> (f3 . f2 . f1 x) s0

Realität	f x = \ s0 -> let (x1, s1) = f1 x s0 in let (x2, s2) = f2 x1 s1 in f3 x2 s2

Ziel	Das Hintereinanderausführen, das Komponieren, aus dem 1. und 2. Beispiel nach dem gleichen Schema realisieren.
1. Schritt	Vereinheitlichung der Struktur der Signaturen aus dem 1. und 2. Beispiel
neuer Typ	data State = ... newtype StateT a = ST { unST :: State -> (a, State) } f1 :: a -> StateT b f2 :: b -> StateT c f3 :: c -> StateT d

	StateT ist wie Maybe ein Typkonstruktor mit einem Typ-Parameter.
Wunsch	aber immer noch falsch
	f :: a -> StateT d f x = \ s -> f3 . f2 . f1 x $ s

Realität	f x = ST $ \ s0 -> let (x1, s1) = unST (f1 x ) s0 in let (x2, s2) = unST (f2 x1) s1 in unST (f3 x2) s2

	Der Zustand (s0, s1, s2) wird durch die Berechnung durchgefädelt.

3.Beispiel
Ein-/Ausgabe	Gedankenmodell: Es gibt einen einzigen großen Wert, der zu einem Zeitpunkt den momentaten Weltzustand repräsentiert.
Weltzustand	Alles was es bei der Ausführung eines Haskell-Programms außerhalb des Prozesses gibt
	data World = ... newtype IO a = IO (World -> (a, World)) putChar :: Char -> IO () getChar :: IO Char main :: IO () main = putChar . getChar -- SO NICHT !!!

	Die Aktionen auf diesem Weltzustand besitzen die gleiche Struktur wie eine zustandsbehaftete Berechnung.
	Die Struktur des Weltzustands World bleibt verborgen (ist abstrakt).
?	Unterschied zu expliziter zustandsbehafteter Berechnung?
	Der Weltzustand kann nicht zwischengespeichtert und zurückgesetzt werden!
	Es gibt im Haskell-Laufzeitsystem Aktionen (Funktionen), die Teile des Weltzustandes lesen und verändern.
	getChar, putChar, main, ...
?	Warum die Deklaration getChar :: IO Char und nicht getChar :: Char
	getChar verändert den Weltzustand im allgemeinen gilt nicht: getChar == getChar

Aufgabe	Kombinator für das Hintereinanderausführen von Berechnungen mit zusätzlichen Effekten.
Eine Lösung	Monaden
Definition	class Applicative m => Monad m where return :: a -> m a (>>=) :: m a -> (a -> m b) -> m b -- nicht wesentlich aber nützlich (>>) :: m a -> m b -> m b f >> g = f >>= ( \ _ -> g ) -- nicht wesentlich aber nützlich -- monadische Funktionskomposition (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c) f >=> g = \ x -> f x >>= g

	Die Variable m steht für einen Typkonstruktor mit einem Typ-Parameter, nicht für einen einfachen Typ.
Kandidaten	Maybe [] StateT IO
Maybe	1. Beispiel
	instance Monad Maybe where return x = Just x Nothing >>= f = Nothing (Just x) >>= f = f x

Reformulierung	der Beispielfunktion f
	f :: a -> Maybe d f x = f1 x >>= \ x1 -> f2 x1 >>= \ x2 -> f3 x2 -- kürzer f x = f1 x >>= f2 >>= f3 -- kürzer f = f1 >=> f2 >=> f3

	Die Verzweigung über Nothing und Just wird einmal in der Monade beschrieben und bei jeder Benutzung von >>= wiederverwendet.
	In der Definition von f werden nur noch Operatoren aus der Monad-Klasse verwendet, keine speziellen Eigenschaften von Maybe.
	Die Funktion könnte also auch für andere Monaden verwendet werden, wenn f1, f2 und f3 entsprechend verallgemeinert werden.
Beweis	der Äquivalenz der Definitionen von f
Explizite Definition	f x = case f1 x of Nothing -> Nothing Just x1 -> case f2 x1 of Nothing -> Nothing Just x2 -> f3 x2
1. Schritt	f x = case f1 x of Nothing -> Nothing Just x1 -> f2 x1 >>= \ x2 -> f3 x2
2. Schritt	f x = f1 x >>= \ x1 -> f2 x1 >>= \ x2 -> f3 x2 -- kürzer f x = f1 x >>= f2 >>= f3
	Komposition der Funktionen f1, f2 und f3 mit Hilfe von >>= erreicht.

StateT	2. Beispiel: Zustandsmonade
Definition	instance Monad StateT where return x = ST $ \ s -> (x, s) f >>= g = ST $ \ s -> let (x1, s1) = (unST f ) s in let f2 = g x1 in (unST f2) s1 -- kürzer f >>= g = ST $ \ s -> let (x1, s1) = unST f s in unST (g x1) s1
Reformulierung	der Beispielfunktion f
	f x = f1 x >>= \ x1 -> f2 x1 >>= \ x2 -> f3 x2 -- kürzer f x = f1 x >>= f2 >>= f3 -- oder f = f1 >=> f2 >=> f3
	Das Durchfädeln des Zustands wird einmal in der Monade beschrieben und bei jeder Benutzung von >>= wiederverwendet.
	In der Definition von f werden nur noch Operatoren aus der Monad-Klasse verwendet, keine speziellen Eigenschaften von StateT.
	Die Funktion könnte also auch für andere Monaden verwendet werden, wenn f1, f2 und f3 entsprechend verallgemeinert werden.
Beweis	der Äquivalenz der Definitionen von f
Explizite Definition	f x = ST $ \ s -> let (x1, s1) = unST (f1 x ) s in let (x2, s2) = unST (f2 x1) s1 in unST (f3 x2) s2
1. Schritt	Globale Variable aus 2. let zu Parametern machen.
	f x = ST $ \ s -> let (x1, s1) = unST (f1 x ) s in unST (g x1) s1 where g x1' = ST $ \ s1' -> let (x2, s2) = unST (f2 x1') s1' in unST (f3 x2) s2
2. Schritt	g mit >>= formulieren.
	f x = ST $ \ s -> let (x1, s1) = unST (f1 x ) s in unST (g x1) s1 where g x1' = f2 x1' >>= \ x2 -> f3 x2
3. Schritt	f mit >>= und g formulieren.
	f x = f1 x >>= \ x1 -> g x1 where g x1' = f2 x1' >>= \ x2 -> f3 x2
4. Schritt	g einsetzen.
	f x = f1 x >>= \ x1 -> f2 x1 >>= \ x2 -> f3 x2 -- kürzer f x = f1 x >>= f2 >>= f3
	Komposition der Funktionen f1, f2 und f3 mit Hilfe von >>= erreicht.

?	Wie startet man eine zustandsbehaftete Berechnung?
	runState :: StateT a -> State -> (a, State) runState f initialState = let (res, finalState) = (unST f) initialState in (res, finalState) -- kürzer runState = unST evalState :: StateT a -> State -> a evalState = fst . runState execState :: StateT a -> State -> State execState = snd . runState
?	Wie startet man eine Berechnung in der Maybe-Monade?
	runMaybe :: Maybe a -> Maybe a runMaybe = id
Ein-/Ausgabe	3. Beispiel: Mit World und IO.
	IO besitzt die gleiche Struktur wie die Zustandsmonade, also gilt die Lösung für das Beispiel 2 hier auch.
Einschränkung	Der Datetyp World wird vollständig vom Haskell-Laufzeitsystem übernommen und ist nicht nach außen sichtbar.
Einschränkung	Nur vordefinierte IO-Operationen manipulieren diesen Zustand.
?	Wie startet man eine IO Berechnung?
	-- gibt es nur im Laufzeitsystem runIO :: IO () -> World -> ((), World) -- Ausführung eines Programms runIO main currentWorld
	data World = ... newtype IO a = IO (World -> (a, World)) putChar :: Char -> IO () getChar :: IO Char main :: IO () main = getChar >>= \ c -> putChar c -- kürzer main = getChar >>= putChar
	Was hat die IO-Monade mit Kuchen backen zu tun?

do	(nur) syntaktischer Zucker zur Erhöhung der Lesbarkeit von Programmen mit monadischen Berechnungen.
Beispiel	f x = f1 x >>= \ x1 -> f2 x1 >>= \ x2 -> f3 x2
Reformulierung	f x = do x1 <- f1 x x2 <- f2 x1 f3 x2
Reformulierung	ohne signifikantes Einrücken
	f x = do { x1 <- f1 x ; x2 <- f2 x1 ; f3 x2 }
Beispiel	main = getChar >>= \ c -> putChar c
Reformulierung	main = do c <- getChar putChar c
Reformulierung	ohne signifikantes Einrücken
	main = do { c <- getChar ; putChar c }
Transformationsschema	do { f } = f do { v <- f ; <stmts> } = f >>= \ v -> do { <stmts> } do { f ; <stmts> } = f >> do { <stmts> }
Gesetze	für Monaden
	return x >>= f = f x c >>= return = c (c >>= f) >>= g = c >>= (\ x -> f x >>= g) (c1 >> c2) >> c3 = c1 >> (c2 >> c3)
?	Was sagen diese Gesetze aus?
	Regel 1 und 2 return ist neutrales Element bezüglich >>= Regel 3 und 4 >>= und >> sind assoziativ, d.h. Teilsequenzen können ausgeklammert werden und zu eigenen Funktionen gemacht werden.
Gesetze	für Monaden formuliert mit monadischer Funktionskomposition
	return >=> f = f f >=> return = f f >=> (g >=> h) = (f >=> g) >=> h
Gesetze	in do-Notation
	do w <- return x f w = do f x
	do v <- c return v = do c
	do w <- do v <- c f v g w = do v <- c w <- f v g w

	Jede Monade ist auch ein Funktor.
	fmap :: (a -> b) -> (m a -> m b) fmap f c = do x <- c return (f x) -- oder kürzer fmap f c = c >>= return . f -- mit infix-Operator <$> aus Data.Functor analog zu $ f <$> c = fmap f c
	Angenehm bei IO-Aktionen, deren Resultat konvertiert werden muss.
	Jede Monade ist auch ein Applikativer Funktor.
	pure = return (<*>) = ap mit ap :: m (a -> b) -> m a -> m b ap mf mx = do f <- mf x <- mx return (f x)
?	Der wesentliche Punkt beim Arbeiten mit Monaden?
	Wiederverwendung! Mit Hilfe von Monaden wird es möglich, Programmteile (eigene Kontrollstrukturen) zu entwickeln, die mit allen Monaden arbeiten. Mit Hilfe von Monaden wird es möglich, Programmteile (eigene Kontrollstrukturen) zu entwickeln, die mit unterschiedlichen Datentypen arbeiten.

Kontrollstruktur	für die Ausführung einer Liste von Berechnungen
sequence	sequence :: (Monad m) => [m a] -> m [a] sequence [] = return [] sequence (c : cs) = do v <- c vs <- sequence cs return (v : vs)
oder	sequence :: (Monad m) => [m a] -> m [a] sequence [] = return [] sequence (c : cs) = c >>= \ v -> sequence cs >>= \ vs -> return (v : vs)
mit foldr	sequence :: (Monad m) => [m a] -> m [a] sequence ms = foldr k (return []) ms where k m1 m2 = do x <- m1 xs <- m2 return (x:xs)
mit <*>	sequence :: (Applicative m, Monad m) => [m a] -> m [a] sequence [] = return [] sequence (m1 : ms) = (:) <$> m1 <*> sequence ms
mit foldr und <*>	sequence :: (Applicative m, Monad m) => [m a] -> m [a] sequence = foldr (\ m1 m2 -> (:) <$> m1 <*> m2) (return [])
Anwendungen	putStr :: String -> IO () putStr s = do sequence $ map putChar s return () putStrLn :: String -> IO () putStrLn s = do sequence $ map putStr $ [s, "\n"]
	getLine :: IO String print :: Show a => a -> IO () print = putStrLn . show main = sequence [ getLine , getLine , getLine ] >>= print
forM	Eine eigene `foreach`-Schleife
	forM :: (Monad m) => [a] -> (a -> m b) -> m [b] forM cs f = sequence $ map f cs
Anwendung	main = forM [1..10] $ \ x -> putStrLn . concat $ ["Das ", show x, ". Mal"]
sequence_, forM_	sequence_ :: (Monad m) => [m a] -> m () sequence_ [] = return () sequence_ (c : cs) = c >> sequence_ cs -- kuerzer sequence_ ms = foldr (>>) (return ()) ms forM_ :: (Monad m) => [a] -> (a -> m b) -> m () forM_ cs f = sequence_ $ map f cs
when	Bedingte Auführung von Berechnungen. Eigene `if-then`-Anweisung
	when :: (Monad m) => Bool -> m () -> m () when p x = if p then x else return ()
ein monadisches if	Eigene monadische `if-then-else`-Anweisung
	ifM :: (Monad m) => m Bool -> m a -> m a -> m a ifM p t e = do b <- p if b then t else e
liftM	Liften von Funktionen
	liftM :: (Monad m) => (a -> b) -> (m a -> m b) liftM f c = do v <- c return (f v) -- oder liftM f c = c >>= return . f -- oder liftM f c = fmap f c -- oder liftM f c = f <$> c -- oder liftM = (<$>)
	liftM2 :: (Monad m) => ( a -> b -> c) -> (m a -> m b -> m c) liftM2 f c1 c2 = do v <- c1 w <- c2 return (f v w) -- oder liftM2 f c1 c2 = f <$> c1 <> c2 -- mit (<>) aus Control.Applicative
Beispiele	für kleine monadische Funktionen mit allgemein einsetzbaren monadischen Berechnungen

Fragen
?	Beziehung zwischen Monaden und Funktoren?
	Jede Monade ist auch ein Funktor instance (Monad m) => Functor m where fmap f x = do r <- x return (f r) -- oder fmap f x = x >>= return . f
?	Ist IO ein Funktor?
	Ja: Siehe erste Frage.
?	Gibt es noch weitere interessante Monaden?
	Ja: Listen, Reader, Writer, Parser, ...
?	Kombination von Monaden: Sinnvoll, von praktischem Nutzen?
	Ja: Beispiel: Zustand und IO, Zustand, IO, Maybe
?	Kombination von Monaden: Wie?
	Monaden-Transformer
?	Einfachste Monade?
	newtype Identity a = Identity a instance Monad Identity where return = Identity Identity x >>= f = f x
?	Listen-Monade?
	instance Monad [] where return :: a -> [a] return x = [x] (>>=) :: [a] -> (a -> [b]) -> [b] xs >>= f = concat (map f xs) -- oder xs >>= f = concat [f x \| x <- xs]
?	Nutzen dieser Monade?
	Als Anfangsmonade bei der Anwendung von Monaden-Transformern!

Monaden

Verallgemeinerte Funktionskomposition

Monaden

do-Notation

Eigene Kontrollstrukturen

Anwendungen und Erweiterungen