Tue Nov 11 12:49:11 EST 2008

```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?

Peter
```