Haskell, einfache Evaluator von Ausdrücken mit Monad Reader

Question

Ich habe einige funktionierende Evaluator von Ausdrücken geschrieben. Aber manchmal bekomme ich eine Ausnahme:

*** Exception: Maybe.fromJust: Nothing 

Ich weiß von was es ist. Ich kann es jedoch nicht wirklich lösen. Mein Ziel ist die Rückgabe in diesem Fall Nothing.

Können Sie mir dabei helfen?

type Var = String 

data Exp = EInt Int 
    | EOp Op Exp Exp 
    | EVar Var 
    | ELet Var Exp Exp -- let var = e1 in e2 

data Op = OpAdd | OpMul | OpSub 

evalExpM :: Exp -> Reader (Map.Map String Int) (Maybe Int) 
evalExpM (EInt n) = return $ Just n 
evalExpM (EVar var) = ask >>= (\x -> return (Map.lookup var x)) 
evalExpM (EOp OpAdd e1 e2) = ask >>= (\x -> return (Just ((fromJust (runReader (evalExpM e1) x)) + (fromJust (runReader (evalExpM e2) x))))) 

evalExpM (EOp OpMul e1 e2) = ask >>= (\x -> return (Just ((fromJust (runReader (evalExpM e1) x)) * (fromJust (runReader (evalExpM e2) x))))) 

evalExpM (EOp OpSub e1 e2) = ask >>= (\x -> return (Just ((fromJust (runReader (evalExpM e1) x)) - (fromJust (runReader (evalExpM e2) x))))) 

evalExpM (ELet var e1 e2) = ask >>= (\x -> (local (Map.insert var (fromJust (runReader (evalExpM e1) x))) (evalExpM e2)) >>= (\y -> return y)) 

evalExp :: Exp -> Int 
evalExp exp = fromJust $ runReader (evalExpM exp) Map.empty 

Answer 1

Zum einen die Art und Weise mit monadischen Berechnungen zu arbeiten, ist nicht zu „laufen“ die Berechnung jedes Mal, wenn Sie einen Wert in der Monade gewickelt begegnen (in diesem Fall Reader ..). Sie sollten den >>= Operator verwenden. Außerdem versuchen Sie, zwei monadische Effekte zu kombinieren: Reader und Maybe. Der "Standard" Weg, dies zu tun ist mit einem Monade-Transformator, aber zum Glück für Sie Reader (oder genauer ReaderT) ist selbst ein Monade-Transformator.

Darüber hinaus würden Sie von einer Abstraktion profitieren, das heißt:

import Control.Monad.Reader 
import qualified Data.Map as M 

type Env = M.Map String Int 

type EvalM = ReaderT (M.Map String Int) Maybe 

lookupEnv :: String -> EvalM Int 
lookupEnv x = ask >>= lift . M.lookup x 

withBind :: String -> Int -> EvalM a -> EvalM a 
withBind x v = local (M.insert x v) 

Diese Funktionen definieren eine Schnittstelle zum Arbeiten mit Umgebungen, in denen Lookup fehlschlagen kann. Sie sollten diese Funktionen einmal schreiben, anstatt ihre Definitionen einzufügen, wenn Sie sie brauchen. Nun ist die Basisfälle Ihrer Funktion sind trivial:

evalExpM :: Exp -> EvalM Int 
evalExpM (EInt n) = return n 
evalExpM (EVar v) = lookupEnv v 

Viele Leute (mich wahrscheinlich) würde applicative Betreiber für die rekursive Fällen verwenden, aber man kann die Suppe von Symbolen vermeiden:

evalExpM (EOp op e1 e2) = liftM2 
    (case op of 
    OpAdd -> (+) 
    OpMul -> (-) 
    OpSub -> (-) 
) (evalExpM e1) (evalExpM e2) 
evalExpM (ELet var e1 e2) = evalExpM e1 >>= \e -> withBind var e $ evalExpM e2 

Lauf Es ist das gleiche wie vorher - ändern Sie einfach runReader zu runReaderT - aber jetzt führen Sie nur eine Berechnung durch, wenn Sie wirklich mit dem Kontext fertig sind.

evalExp :: Exp -> Int 
evalExp e = maybe (error "evalExp") id $ runReaderT (evalExpM e) M.empty 

Answer 2

was Sie beabsichtigen, ist die Monade Maybe, verwenden, die automatisch die Nothing nach unten geht, so dass Sie das nicht manuell handhaben müssen.

so könnten Sie den Typ (ReaderT r Maybe)(a) anstelle von (Reader r)(Maybe a) verwenden.

aber ich denke, dass Sie dies schließlich zu r -> Maybe a vereinfachen möchten.

---

wie auch immer, das Sie verwenden Monad Reader r, die der Versorgung eines Parameters nur eine andere Art ist. weil r->a ist nur syntaktischer Zucker für (->) r a und (->) r ist bereits ein Reader Monad, können Sie stattdessen verwenden: Sie könnten sogar ersetzen ask mit id.

Sie wahrscheinlich nicht die alberne ask Funktion die ganze Zeit verwenden möchten, so können Sie reader verwenden, um einfach die Funktion zu heben.

evalExpM :: Exp -> Reader (Map.Map String Int) (Maybe Int) 
evalExpM (EVar var) = ask >>= (\x -> lift (Map.lookup var x)) 
evalExpM (EVar var) = reader $ \x -> Map.lookup var x 
evalExpM (EVar var) = reader $ Map.lookup var 

ist es bequemer Reader (oder ReaderT) nur zu verwenden, wenn Sie automatisch möchten die param an inneren Funktionen übergeben.Aber selbst dann können Sie einfach die Monad (->) r verwenden oder einfach einen Parameter übergeben. Sie erhalten ein besseres Gefühl dafür, wenn Sie immer die Monad (->) r und id anstelle von Reader r und ask verwenden. für ReaderT auf der anderen Seite, werden Sie sehen, ihre Notwendigkeit, wenn Sie einen Parameter an die meisten Funktionen übergeben müssen Sie in do Notation verwenden.

evalExp :: Exp -> Map.Map String Int -> Maybe Int 

evalExp (EOp OpSub e1 e2) = ask >>= (\x -> return (Just ((fromJust ({-runReader-} (evalExp e1) x)) - (fromJust ({-runReader-} (evalExp e2) x))))) 

evalExp (EOp OpSub e1 e2) = do -- Monad ((->) (Map.Map String Int)) 
    x <- id -- hehe, same as ask 
    return (Just ((fromJust ({-runReader-} (evalExp e1) x)) - (fromJust ({-runReader-} (evalExp e2) x)))) 

evalExp (EOp OpSub e1 e2) x = -- directly with param x 
    (Just ((fromJust ((evalExp e1) x)) - (fromJust ((evalExp e2) x)))) 

evalExp (EOp OpSub e1 e2) x = do -- Monad (Maybe) 
    let a = fromJust ((evalExp e1) x) 
    let b = fromJust ((evalExp e2) x) 
    Just $ a - b 

evalExp (EOp OpSub e1 e2) x = do -- Monad (Maybe) 
    a <- return $ fromJust ((evalExp e1) x) 
    b <- return $ fromJust ((evalExp e2) x) 
    Just $ a - b 

-- and without that bug: 
evalExp (EOp OpSub e1 e2) x = do -- because return=Just 
    a <- evalExp e1 x 
    b <- evalExp e2 x 
    return $ a - b 

evalExp (EOp OpSub e1 e2) = runReaderT $ do -- Monad (ReaderT (Map...) Maybe) 
    a <- ReaderT $ evalExp e1 
    b <- ReaderT $ evalExp e2 -- this is a nice example to use ReaderT 
    return $ a - b 

-- this is ugly unless we need that param wrapped quite often: 
evalExpM :: Exp -> ReaderT (Map.Map String Int) Maybe Int 
evalExpM exp = ReaderT $ evalExp exp