Funktionale Programmierung: Nichtdeterministische Ausdrucksauswertung mit der Listen-Monade

Nichtdeterministische Ausdrucksauswertung	und die Listen-Monade
Gegeben	Eine einfache Datenstruktur für arithmetische Ausdrücke mit ganzen Zahlen in monadischer Form (Beispiel: Interpretierer für die Auswertung arithmetischer Ausdrücke)

{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE TypeSynonymInstances #-} -- The following compiler options are neccessary -- for the extension concerning the error handling -- they are not required for this simple example -- ---------------------------------------- -- -- Monadic version of simple expression -- evaluator. -- No extensions, same semantics as in Expr0 -- -- ---------------------------------------- module Expr1 where import Control.Monad () -- ---------------------------------------- -- syntactic domains data Expr = Const Int \| Binary BinOp Expr Expr deriving (Show) data BinOp = Add \| Sub \| Mul \| Div \| Mod deriving (Eq, Show) -- ---------------------------------------- -- semantic domains data Result a = Val { val :: a } deriving (Show) -- ---------------------------------------- -- the identity monad instance Monad Result where return = Val (Val v) >>= g = g v -- ---------------------------------------- -- the meaning of an expression eval :: Expr -> Result Int eval (Const i) = return i eval (Binary op l r) = do mf <- lookupMft op mf (eval l) (eval r) -- ---------------------------------------- -- the meaning of binary operators type MF = Result Int -> Result Int -> Result Int lookupMft :: BinOp -> Result MF lookupMft op = case lookup op mft of Nothing -> error "operation not implemented" Just mf -> return mf mft :: [(BinOp, MF)] mft = [ (Add, liftM2 (+)) , (Sub, liftM2 (-)) , (Mul, liftM2 (*)) , (Div, liftM2 div) ] -- defined in Control.Monad liftM2 :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r liftM2 f m1 m2 = do x1 <- m1 x2 <- m2 return (f x1 x2) -- ---------------------------------------- -- sample expressions e1 = Binary Mul (Binary Add (Const 2) (Const 4) ) (Const 7) e2 = Binary Div (Const 1) (Const 0) e3 = Binary Mod (Const 1) (Const 0) [v1,v2,v3] = map eval [e1, e2, e3] -- ----------------------------------------
Die Quelle

Erweiterung	Die Menge der Operatoren soll um einen neuen Operator +- (PlusMinus) erweitert werden.
	data BinOp = ... \| PlusMinus
	Diese Operation soll für zwei Werte x und y die beiden Ergebnisse x+y und x-y liefern. Damit kann ein Ausdruck zwei oder mehrere Resultate liefern, das Auswerten berechnet also eine ganze Liste von Werten.
	Dieses erfordert eine Erweiterung des Result-Datentyps, eine Zahl reicht hier nicht mehr, sondern eine Liste von Zahlen
	newtype Result a = Val { val :: [a] }
Monadischer Stil	Durch den monadischen Stil des Interpretiers kann diese Erweiterung lokal durch Veränderung der Monade und durch eine zusätzliche Bedeutungsfunktion für den neuen Operator realisiert werden.
`MonadPlus`	Das Ansammeln von mehreren Resultaten kann nicht nur mit Listen gemacht werden, sondern auch mit anderen Monaden. Hierfür gibt es eine einheitliche Schnittstelle, die MonadPlus-Klasse. Implementiert man diese Schnittstelle für Result, so kann man dadurch auch den Konstruktor von Result vor dem Interpretierer verstecken.

1. Aufgabe	Erweitern Sie das Programm so, dass nicht mehr mit der Identität sonder mit der Listen-Monade gearbeitet wird. Hierzu muss der Result-Typ erweitert werden, die Instanz für Monad verändert werden, und der neue Operator implementiert werden. Implementieren Sie auch eine Instanz für MonadPlus und nutzen diese für den PlusMinus-Operator.
2. Aufgabe	Erweitern Sie die Lösung so, dass das Programm auch die Fehlersituationen aus der ersten Monadenaufgabe richtig behandelt. Als Resultat ist also nicht nur eine Liste von Werten sinnvoll, sondern auch eine Ausnahme.
?	Gibt es verschiedene sinnvolle Definitionen für (>>=)?
	Ja. Wenn an einer Stelle ein Fehler auftritt, ist die gesammte Berechnung fehlerhaft Wenn ein Argument einen Fehler liefert, so wird dieses Argument vergessen, nur wenn alle Argumente Fehler liefern, wird der (werden die) Fehler propagiert.

Nichtdeterministische Ausdrucksauswertung mit der Listen-Monade

Aufgabe 1