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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
