Der Basisevaluierer mit Monaden hat die gleiche Datenstruktur:
data Term = Con Int |
Div Term TermDie Implementierung sieht wie folgt aus:
eval :: Monad m => Term -> m Int eval (Con x) = return x eval (Div t u) = do x <- eval t y <- eval u return (x `div` y)
Der Auswerter liefert ein monadisches Ergebnis zurück. Bei einer Konstanten wird der Wert der Konstanten zurückgeliefert. Bei einer Divison wird zuerst der linke Teilterm berechnet und an die Variable x gebunden, danach das rechte Teiltermergebnis an y gebunden und dann das Divisionsergebnis zurückgeliefert.
Die Struktur dieses Evaluierers ist komplexer als die des einfachen Evaluierers ohne Monad, doch sie ist wesentlich flexibler, was in den nächste Beispielen sichtbar wird.
Um nun einen Auswerter zu erstellen, der nur das Ergebnis berechnet (ohne zusätzliche Features), implementieren wir diesen mit dem ID-Monad. Dafür benötigen wir einen neuen Datentypen:
newtype Id a = MkId a
Nun müssen wir mit Id eine Instanz von dem Monad bilden. Wir schon
von dem IO Monad gelernt haben, müsen wir nur return und (>>=)
implementieren:
instance Monad Id where
return x = MkId x
(MkId x) >>= q = q x
Die Funktion return liefert mit Hilfe des Konstruktors
MkId ein Id zurück. Wird ein MkId x und eine
Funktion q mit dem Bind-Operator verknüpft, so wird die Funktion q mit dem
Wert x aufgerufen.
Da keine Änderungen an dem Basisevaluierers nötig sind, ist der Evaluierer der Basisevaluierers spezialisiert auf den Monad Id.
evalId :: Term -> Id Int evalId = eval
Da ein Int nicht das selbe ist wie ein Id Int,
benötigt man noch eine show-Funktion für ein Id a:
instance Show a => Show (Id a) where
show (MkId x) = "Ergebnis: " ++ show x
Auch die Datenstruktur des Evaluierers mit Exceptionbehandlung ist gleich geblieben:
data Exc a = Raise Exception | Return a type Exception = String
Wieder muss die Klasse Monad instanziiert werden:
instance Monad Exc where
return x = Return x
(Raise e) >>= q = Raise e
(Return x) >>= q = q x
Entscheident hierbei ist die Implementierung des Bind-Operators. Wird eine
ausgelöste Exception mit einer Funktion q kombiniert, so ist die Exception das
Ergebnis und die Funktion q wird nicht mehr aufgerufen. Darin besteht der
kontrollierte Programmabbruch. Wird jedoch ein gültiger Wert Return
x mit einer Funktion q kombiniert, wird die Funktion q mit dem Wert x
aufgerufen.
Nun wird noch eine spezifische Funktion für den Monad gebraucht, die eine Exception auslöst:
raise :: Exception -> Exc a raise e = Raise e
Der Basisevaluierer wird nun noch an einer Stelle modifiziert:
evalExc :: Term -> Exc Int evalExc (Con x) = return x evalExc (Div t u) = do x <- evalExc t y <- evalExc u if y == 0 then raise "division by zero" else return (x `div` y)
Nachdem beide Teilterme ausgewertet wurden, wird nun der linke auf null überprüft. Bei einer Division durch null wird eine Excption ausgelöst, ansonsten die Division ausgeführt.
Die Datenstruktur des Evaluierers mit Trace-Output ist wieder gleich geblieben:
newtype Out a = MkOut(Output,a) type Output = String
Wieder muss die Klasse Monad instanziiert werden:
instance Monad Out where
return x = MkOut("",x)
p >>= q = MkOut (ox ++ oy,y)
where MkOut (ox,x) = p
MkOut (oy,y) = q x
Hier kann man sehen, dass der geschachtelte Aufruf mit where aus
dem Evaluierer ohne Monad in diese Instanz genommen wurden. Werden zwei
Funktionen p und q mit dem Bindoperator verknüpft, dann wird p aufgerufen,
das ein Ergebnistupel mit einem String ox und einem Ergebnis x zurückliefert.
Die zweite Funktion wird dann mit dem Ergebnis x aufgerufen und liefert ein
anderes Ergebnistupel mit einem String oy und einem Ergebnis y. Das
Ergebnistupel dieses Ausdruckes ist dann die Konkatenation von ox und oy und
dem Ergebnis y.
Auch diesmal wird noch eine spezifische Funktion für den Monad zum Generieren des Outputs benötigt:
out :: Output -> Out() out ox = MkOut (ox,())
Und so sieht nun der modifizierte Evaluierer aus, der an zwei kleinen Stellen erweitert wurde:
evalOut :: Term -> Out Int evalOut (Con x) = do out(line(Con x)x) return x evalOut (Div t u) = do x <- evalOut t y <- evalOut u out(line(Div t u) (x `div` y)) return (x `div` y)
Bevor das Ergebnis der Konstanten und der Division zurückgeliefert werden, muss noch der String für den Output erstellt werden.
Die Datenstruktur des Evaluierers ist wieder gleich geblieben:
newtype St a = MkSt(State -> (a,State)) type State = Int
Wieder muss die Klasse Monad instanziiert werden:
instance Monad St where
return x = MkSt f where f s = (x,s)
p >>= q = MkSt f
where
f s = apply (q x) s'
where (x,s') = apply p s
Das Kommando return x liefert eine Funktion mit einem Parameter s,
dem Zustand, zurück. Das Ergebnis dieser Funktion ist ein Wertepaar mit dem
unverändertem Zustand s und dem Wert x.
Werden zwei Funktionen p und q mit dem Bind-Operator aufgerufen, wird zuerst p aufgerufen und das Ergebnis wird mit dem Parameter s, dem Zustand, aufgerufen. Das daraus resultierende Tupel mit einem Wert x und einem veränderten Zustand s' wird für den nächsten Aufruf genutzt. Zuerst wird die Funktion q mit dem Wert x und danach wird die Ergebnisfunktion mit dem veränderten Zustand s' aufgerufen.
Diese Struktur ist auch schon aus dem Evaluierer ohne Monad bekannt.
Nun muss noch eine spezifische Funktion für den Monad zum Inkrementieren des Zustands implmentiert werden:
tick :: St() tick = MkSt f where f s = ((),s+1)
Somit sieht der modifizierte Evaluierer wie folgt aus:
evalSt :: Term -> St Int evalSt (Con x) = return x evalSt (Div t u) = do x <- evalSt t y <- evalSt u tick return (x `div` y)
Der Evaluierer wurde nur an einer Stelle um eine Zeile Erweitert. Bevor das
Divisionsergebnis zurückgeliefert wird, muss noch der Zustand mit
tick inkrementiert werden.
Welche Vorteile hat der Monad?