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)
|
| |
--
--
module Expr1 where
import Control.Monad ()
data Expr = Const Int
| Binary BinOp Expr Expr
deriving (Show)
data BinOp = Add | Sub | Mul | Div | Mod
deriving (Eq, Show)
data Result a
= Val { val :: a }
deriving (Show)
instance Monad Result where
return = Val
(Val v) >>= g = g v
eval :: Expr -> Result Int
eval (Const i)
= return i
eval (Binary op l r)
= do
mf <- lookupMft op
mf (eval l) (eval r)
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)
]
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)
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.
|
Funktionale Programmierung: Nichtdeterministische Ausdrucksauswertung mit der Listen-Monade
