Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2017 / Fortgeschrittene Funktionale Programmierung / Material / Zustands-Monade zu Fuss


Inhaltsbereich

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.)

Haskell source code icon 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


Funktionsleiste