On Thu, Aug 03, 2006 at 05:25:07PM +0200, Klaus Ostermann wrote: > Hi Niklas, > > thanks for your suggestion. Can you explain how your solution is better 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
