Zustands-Monade zu Fuss
In der Vorlesung am 23.05.2017 haben wir schrittweise Monade für Berechnungen-in-einem-veränderlichen-Kontext von Grund auf aufgebaut. Dies ist das kommentierte Ergebnis.
(Hinweis: Nächste Vorlesung sehen wir uns an, wie wir dies mit Bibliotheksfunktionen schneller erreichen.)
zustand.hs
—
Haskell source code,
5 KB (5267 bytes)
Dateiinhalt
import Control.Monad (ap, liftM) {- Live programmiert in der FFP Vorlesung am 23.05.2017 von Steffen Jost. Wir zeigen, wie wir schrittweise eine Zustands-Monade von Grund auf aufbauen. -} -- Zuerst wählen wir einen beliebigen gewöhnlichen Typen für den Zustand. -- Welchen Zustand man benötigt, hängt natürlich von der Anwendung ab -- und könnte auch leicht parametrisiert werden. -- type Zustand = Data.Map.Map String Int -- Abbildung von String nach Int, d.h. beliebig viele Int-Variablen type Zustand = (Int,Bool,Double) -- Drei Veränderliche mit verschiedenen Typen. -- ANMERKUNG: Hier wäre Record-Syntax sehr hilfreich, wird aber erst später in der Vorlesung behandelt {- Zuerst haben wir eine paar primitive Operationen auf dem Zustand gebaut: putInt :: Int -> Zustand -> Zustand -- den Int-Wert des Zustands setzen putInt i (_,b,d) = (i,b,d) getInt :: Zustand -> Zustand -- den Int-Wert des Zustands auslesen getInt (i,_,_) = i Diese wurden später zu den primitiven Operationen der Monade umgebaut: -} putInt :: Int -> ZM () putInt i = ZM $ \(_,b,d) -> ((),(i,b,d)) getInt :: ZM Int getInt = ZM $ \(i,b,d) -> (i,(i,b,d)) putBool :: Bool -> ZM () putBool b = ZM $ \(i,_,d) -> ((),(i,b,d)) getBool :: ZM Bool getBool = ZM $ \z@(_,b,_) -> (b,z) putDbl :: Double -> ZM () putDbl d = ZM $ \(i,b,_) -> ((),(i,b,d)) getDbl :: ZM Double getDbl = ZM $ \z@(_,_,d) -> (d,z) -- Jetzt definieren wir einen Typ für unsere Zustandsmonade. -- Eine Zustands-abhängige Berechnung eines Typen a ist eine Berechnung, -- welche einen Anfangszustand bekommt und dann am Ende ein Ergebnis -- des Typs a liefert und den Endzustand, also -- Zustand -> (a,Zustand) -- Um für diesen Typ einen Monaden-Instanz zu erstellen, müssen wir -- ihn zu einem frischen Typen machen. Wir verwenden den newtype-Trick (siehe Folien). -- (Man könnte auch anstatt "newtype" "data" schreiben, was zu geringfügig ineffizienteren Code führt.) -- In jedem Fall benötigen wir einen frischen Konstruktor, hier "ZM" (also zufällig gleicher Bezeichner wie der Typ "ZM") newtype ZM a = ZM (Zustand -> (a, Zustand)) {- Wer es lieber gleich allgemeiner haben will, könnte auch so etwas definieren: newtype ZMpar s a = ZM ( s -> (a, s )) type ZM a = ZMpar Zustand a -} -- Auch hier wäre Record-Syntax nützlich -- Stattdessen definieren wir uns folgende Funktion: getZM :: ZM a -> (Zustand -> (a, Zustand)) getZM (ZM op) = op -- wegen newtype gibt es diese Funktion nach dem Kompilieren nicht mehr instance Monad ZM where -- return :: a -> ZM a -- return :: a -> (Zustand -> (a, Zustand) return a = ZM $ \zustand1 -> (a, zustand1) -- (>>=) :: ZM a -> (a -> ZM b) -> ZM b -- (>>=) :: (Zustand -> (a,Zustand)) -> (a -> (Zustand -> (b,Zustand))) -- -> (Zustand -> (b,Zustand)) (>>=) (ZM sa) sf = ZM $ \zustand1 -> let (a, zustand2) = sa zustand1 in let (ZM sb) = sf a in let (b, zustand3) = sb zustand2 in (b,zustand3) -- Diesen imperativ anmutenden Code haben wir uns schrittweise hergeleitet aus dem Typ. -- Vereinfacht könnte man auch schreiben: {- ma >>= fmb = ZM $ \zustand1 -> let (a,zustand2) = getZM ma zustand1 in getZM (fmb a) zustand2 -} -- Eine Monaden-Instanz setzt eine Applicative-Instanz voraus. -- Dies kürzen wir ab, da nach der Vorlesung die Monade den Applikativen Funktor bereits impliziert. instance Applicative ZM where pure = return (<*>) = ap -- Eine Applicative-Instanz setzt eine Functor-Instanz voraus. -- Dies kürzen wir ab, da nach der Vorlesung die Monade den Funktor bereits impliziert. instance Functor ZM where fmap = liftM -- Jetzt brauchen wir noch eine Start-Funktion, welche einen Anfangszustand -- und eine Berechnung-im-Zustand nimmt, und diese ausführt: runZustand :: Zustand -> ZM a -> (a,Zustand) runZustand zustand0 (ZM sa) = sa zustand0 -- Hier haben wir jetzt eine solche Berechnung-im-Zustand demo :: ZM String -- Zustand -> (a,Zustand) demo = do x <- getInt y <- getDbl let gr = (fromIntegral x) > y putBool gr putInt $ 2 * x z <- getInt x <- getInt putInt $ 2 * x return $ (show x ++ "|" ++ show y ++ "|" ++ show z) -- In der Vorlesung wurde ungefähr folgender Code mit GHCI ausgeführt: main :: IO () main = do putStrLn $ "Erste Ausführung:" print $ runZustand (3,False,1.1) demo putStrLn $ "Zweite Ausführung:" print $ runZustand (3,False,1.1) demo putStrLn $ "Dritte Ausführung:" print $ runZustand (4,True,43.2) demo putStrLn $ "Vierte Ausführung:" print $ runZustand (3,False,1.1) demo2 putStrLn $ "Fünfte Ausführung:" print $ runZustand (3,False,1.1) demo -- Wir sehen: der Zustand gilt jeweils nur innerhalb der monadischen Operationen! -- Noch irgendeine Berechnung-im-Zustand zum Vergleich: demo2 :: ZM Double demo2 = do x <- getInt y <- getDbl let z = (fromIntegral x) + y putDbl $ 2.0 * z return z
Artikelaktionen