On Tue, 2008-11-11 at 18:49 +0100, Peter Padawitz wrote:
At first a type of arithmetic expressions and its generic evaluator:
data Expr = Con Int | Var String | Sum [Expr] | Prod [Expr] | Expr :- Expr | Int :* Expr | Expr :^ Int
data ExprAlg a = ExprAlg {con :: Int -> a, var :: String -> a, sum_ :: [a] -> a, prod :: [a] -> a, sub :: a -> a -> a, scal :: Int -> a -> a, expo :: a -> Int -> a}
eval :: ExprAlg a -> Expr -> a eval alg (Con i) = con alg i eval alg (Var x) = var alg x eval alg (Sum es) = sum_ alg (map (eval alg) es) eval alg (Prod es) = prod alg (map (eval alg) es) eval alg (e :- e') = sub alg (eval alg e) (eval alg e') eval alg (n :* e) = scal alg n (eval alg e) eval alg (e :^ n) = expo alg (eval alg e) n
Secondly, a procedural version of eval (in fact based on continuations):
data Id a = Id {out :: a} deriving Show
instance Monad Id where (>>=) m = ($ out m); return = Id
peval :: ExprAlg a -> Expr -> Id a peval alg (Con i) = return (con alg i) peval alg (Var x) = return (var alg x) peval alg (Sum es) = do as <- mapM (peval alg) es; return (sum_ alg as) peval alg (Prod es) = do as <- mapM (peval alg) es; return (prod alg as) peval alg (e :- e') = do a <- peval alg e; b <- peval alg e'; return (sub alg a b) peval alg (n :* e) = do a <- peval alg e; return (scal alg n a) peval alg (e :^ n) = do a <- peval alg e; return (expo alg a n)
My question: Is peval less time- or space-consuming than eval? Or would ghc, hugs et al. optimize eval towards peval by themselves?
peval is not based on continuations. As you state, you are using the Id monad. (>>=) is just flip ($). Unless GHC has some trouble seeing through the Monad instance, it should simply inline the latter to the former since they are the exact same code.