[Haskell-cafe] compilation question

[Derek Elkins]

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.