Hi Niklas,
thanks for your suggestion. Can you explain how your solution is better
On Thu, Aug 03, 2006 at 05:25:07PM +0200, Klaus Ostermann wrote: than
the very simple one, i.e.,
data Exp e = Num Int | Add e e data Labeled = L String e newtype SimpleExp = Exp SimpleExp newtype LabeledExp = Labelled (Exp LabeledExp)
hmm, I'm not sure it works, if at all. With the above definition how do you construct a vallue of SimpleExp? In hugs, I type Main> :t Num 1 Num 1 :: Exp a but then Main> Num 1 :: SimpleExp ERROR - Type error in type annotation *** Term : Num 1 *** Type : Exp a *** Does not match : SimpleExp Here is a solution to your original problem. The proper way is to do type level fixpoint
data Fix a = Fix (a (Fix a))
(which you called Mu), and also a sum type, which is explained below. So initially you want Exp
data Exp e = Num Int | Add e e
Now, Fix Exp becomes what you want for the simple expression.
type SimpleExp = Fix Exp
Here is a little evaluation function eval :: SimpleExp -> Int eval (Fix (Num i)) = i eval (Fix (Add e1 e2)) = eval e1 + eval e2 But this is not exactly versatile, you may want to extend the eval when you add new data constructors. Here is a better one
e eval (Num i) = i e eval (Add e1 e2) = eval e1 + eval e2
so to evaluate SimpleExp, you use
evalE :: SimpleExp -> Int evalE (Fix e1) = e evalE e1
evalE is actually a fixed point of e. Then you want to label the Exp, but without duplicating the Exp structure.
data Label e = Label String e
the eval for Labelled stuff is just
f eval (Label _ e) = eval e
By now, both Exp and Label are actually type level functions. To make Label as an extension to Exp type, you need the fixed point of the sum of them, i.e., this fixed point is both the fixed point of Exp and Label.
data Sum a b c = Lt (a c) | Rt (b c)
Fix (Sum Exp Label) is all you need!
type LabelledExp = Fix (Sum Exp Label)
eval for the LabelledExp is
g eval (Lt x) = e eval x g eval (Rt y) = f eval y
evalLE :: LabelledExp -> Int evalLE (Fix e1) = g evalLE e1
So we have achieved extending both original data type and evaluation function without modifying them. to easily construct data of LabelledExp, little helpers are handy
num = Fix . Lt . Num add x = Fix . Lt . (Add x) label l = Fix . Rt . (Label l)
here are a few examples of using them
t1 = num 1 t2 = add t1 t1 t1' = label "t1" t1 t2' = label "t2" (add t1' t1')
to convert from LabelledExp to SimpleExp is also easy
unlabel :: LabelledExp -> SimpleExp unlabel (Fix (Rt (Label _ e1))) = unlabel e1 unlabel (Fix (Lt (Num i))) = Fix (Num i) unlabel (Fix (Lt (Add e1 e2))) = Fix (Add (unlabel e1) (unlabel e2))
This solution perhaps isn't what you intended, as it doesn't enforce that there must be a Label for every LabelledExp value. But it is a nice way to show how to extend data types and their functions without modifying them. Regards, Paul Liu