Transcript
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
