Monad

Technische Universität München
Monads in Haskell
Seminar: Fortgeschrittene Konzepte der funktionalen Programmierung,
Sommersemester 2015
Lukas Fürmetz
Technische Universität München
Agenda

Grundlagen von Monaden

Umsetzung in Haskell

Anwendung von Monaden

Fazit
03.06.2015
2
Technische Universität München
Functor

Ein Functor ist eine Datenstruktur über die gemappt werden kann

In Haskell wird dieses Konzept über eine Typklasse umgesetzt:
class Functor f where
fmap
:: (a -> b) -> f a -> f b

Dabei müssen zwei Gesetze erfüllt sein:
– fmap id = id
– fmap (f . g) = fmap f . fmap g (Homomorphismus)
03.06.2015
3
Technische Universität München
Beispiel Functor
let xs = [1,2,3,4]
fmap (*2) xs = [2,4,6,8]
let x = Just 4
fmap even x = Just True
let dic = fromList [(1, "foo"), (2, "bar"),
(3, "baz")]
fmap reverse dic =
fromList [(1, "oof"), (1, "rab"), (1, "zab")]
03.06.2015
4
Technische Universität München
Applicative

Applicative ist eine Erweiterung von Functor

Operationen auf Containern können mithilfe dieser verbunden werden

Umsetzung erfolgt wiederum über eine Typklasse im Modul
Control.Applicative
class Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
03.06.2015
5
Technische Universität München
Applicative Beispiel
instance Applicative Maybe where
pure = Just
Nothing <*> _
Just f <*> m
= Nothing
= fmap f m
Just (/) <*> Just 42 <*> Just 3
-- = Just 14
03.06.2015
6
Technische Universität München
Applicative Laws

Identität:
pure id <*> v = v

Komposition:
pure ( . ) <*> u <*> v <*> w = u <*> (v <*> w)

Homomorphismus:
pure f <*> pure x = pure (f x)

Tausch:
u <*> pure y = pure ($ y) <*> u
03.06.2015
7
Technische Universität München
Monads

Eine Monade ist wiederum eine Erweiterung von Applicative

Mithilfe von Monaden können Operationen auf Containern aneinander
gehängt werden, wobei die Monade noch die Werte ändern kann
„programmierbares Semikolon“)
03.06.2015
8
Technische Universität München
Umsetzung durch eine Typklasse
class Applicative m => Monad m where
(>>=) :: forall a b. m a -> (a -> m b) -> m b
return :: a -> m a
return = pure
03.06.2015
9
Technische Universität München
Monad

„return“ nimmt einen Wert und tut ihn in den Kontext der Monade:
example :: Maybe Integer
example = return 3
-- = Just 3

Mithilfe von „>>=“, auch „bind“ genannt, können Operationen auf Monaden
aneinander gehängt werden
Just 1 >>= (\x -> return (x * 8))
>>= (\y -> return (y + 2))
-- = Just 10
03.06.2015
10
Technische Universität München
Monad Laws


„return“ arbeitet ähnlich wie ein „neutrales Element“:
–
(return x) >>= f
–
m >>= return
=
=
f x
m
„bind“ ist quasi assoziativ:
m a >>= f) >>= g
-- ist äquivalent zu
m a >>= (\a -> ((f a) >>= g))
03.06.2015
11
Technische Universität München
Die “do”-Notation

Um den Umgang mit Monaden zu vereinfachen, stellt „syntactic sugar“ für
die „bind“-Operation zu Verfügung:
Just 1 >>= (\x -> return (x * 8)
>>= (\y -> return (y + 2)))
kann umgeschrieben werden zu:
do x <- Just 1
y <- return (x * 8)
return (y + 2)
03.06.2015
12
Technische Universität München
Die Maybe-Monade
instance Monad Maybe where
(Just x) >>= k
= k x
Nothing >>= _
= Nothing
return
03.06.2015
= Just
13
Technische Universität München
Beispiel zur Maybe-Monade
Gegeben:
lookup :: Eq a => a -> [(a ,b)] -> Maybe b
table1 = [("Foo", 1), ( "Bar", 2), ("Baz", 3)]
table2 = [(1, 81476), (2, 81399), (4, 91232)]
Gesucht:
getPLZ :: String -> Maybe Integer
03.06.2015
14
Technische Universität München
Beispiel zur Maybe-Monade
getPLZ n = case lookup n table1 of
Nothing -> Nothing
Just id -> lookup id table2
getPLZ n = lookup n table1 >>=
(\id -> lookup id table2)
getPLZ n = do id <- lookup n table1
lookup id table2
03.06.2015
15
Technische Universität München
Die Maybe-Monade
Mithilfe der Maybe-Monade können Operationen, die vielleicht
ein Ergebnis zurückgeben, miteinander verbunden werden.
Sobald eine dieser Funktionen kein Ergebnis liefert, liefert die
gesamte Operation kein Ergebnis zurück.
03.06.2015
16
Technische Universität München
List


Die Maybe-Monade ist nützlich um Funktionen zu verbinden die 0 oder 1
Ergebnis haben.
Im Gegensatz dazu ist die List-Monade nützlich um Funktionen zu
verbinden, die 0 oder mehr Ergebnisse haben.
instance Monad []
m >>= k
return x
03.06.2015
where
= foldr ((++) . k) [] m
= [x]
17
Technische Universität München
Beispiel zur List-Monade
data Substance = Substance1 | Substance2 |
Substance3 | Substance4
deriving (Show, Eq)
react :: Substance -> Substance -> [Substance]
react Substance1 Substance2 =
[Substance4, Substance4]
react Substance3 Substance4 =
[Substance1, Substance2]
react _ _ = undefined
03.06.2015
18
Technische Universität München
Beispiel zur List-Monade
firstExperiment = react Substance1
secondExperiment = react Substance3
simulateExperiment :: [Substance]
simulateExperiment = do
secondResult <- firstExperiment Substance2
thirdResult <- secondExperiment secondResult
return thirdResult
„simulateExperiment“ ist damit äquivalent zu:
[Substance1,Substance2,Substance1,Substance2]
03.06.2015
19
Technische Universität München
List-Comprehension
„simulateExperiment“ als List-Comprehension:
simulateExperiment = [thirdResult |
secondResult <- firstExperiment Substance2,
thirdResult <- secondExperiment secondResult]
List-Comprehensions sind syntaktischer Zucker für die ListMonade:
example1 xs = [ x * x | x <- xs, even x]
example2 xs = do x <- xs
guard (even x)
return (x * x)
03.06.2015
20
Technische Universität München
State

Haskell ist eine rein funktionale Programmiersprache, also kann kein
Funktion etwas am globalem Zustand ändern

Für manche Probleme ist jedoch ein veränderbarer Zustand nützlich, z.B.
bei Spielen

Haskell stellt dafür die State-Monade zur Verfügung, welche bei dem
aktuellen GHC über einen Monad-Transformer implementiert ist
03.06.2015
21
Technische Universität München
State-Monad Beispiel
data Op = Pop | Push Integer | Add
type Stack = [Integer]
type OpStack = [Op]
add :: Stack -> Stack
add (x:y:xs) = (x + y) : xs
03.06.2015
22
Technische Universität München
State-Monad Beispiel
runStack :: OpStack -> State Stack Integer
runStack [] = do
xs <- get
return (head xs)
runStack (x:xs) = do
stack <- get
case x of
Pop -> put (tail stack)
Push i -> put (i : stack)
Add -> put (add stack)
runStack xs
03.06.2015
23
Technische Universität München
State-Monad Beispiel
initialStack = [2,5,3,8]
evalState (runStack [Add, Pop, Pop, Push 5, Add])
initialStack
≡
13
Die State-Monade kann als Abstraktion eine Funktion, welche ein Zustand
übergeben wird, und einen Wert und einen neuen Zustand zurück gibt,
interpretiert werden.
03.06.2015
24
Technische Universität München
IO-Monade

Mithilfe dieser Monade können IO-Operationen, wie z.B. der Zugriff auf
eine Datei, bewerkstelligt werden.

Haskell hat eigentlich keine Seiteneffekte. Widerspruch?
Man kann diese Monade aber als Beschreibung von Aktionen
sehen, welche dann von der Runtime-Umgebung ausgeführt
wird. Somit kann die Sprache an sich ohne Seiteneffekte
auskommen!

Alle Funktionen, welche die IO-Monade verwenden, haben „IO a“ in ihrer
Typsignatur, somit kann purer und unpurer Code sauber getrennt werden.
03.06.2015
25
Technische Universität München
IO-Monade Beispiel

Simple Implementierung des Unix-Programms „cat“:
main :: IO ()
main = do a <- getArgs
text <- readFile (head a)
print text

Implementierung von „wc –l“:
main :: IO ()
main = do a <- getArgs
text <- readFile (head a)
print (length $ lines text)
03.06.2015
26
Technische Universität München
Fazit

Monaden sind ein sehr nützliche Abstraktion, welche viele Anwendungen
hat, wie z.B. Fehlerbehandlung.

Durch Monaden kann Zustand und I/O in einer rein funktionalen Sprache,
wie Haskell, implementiert werden.

Mithilfe der „do“-Notation wird der Umgang mit Monaden sehr vereinfacht.
03.06.2015
27
Technische Universität München
Vielen Dank
noch Fragen?
03.06.2015
Lukas Fürmetz
28

Download Report