Hello, I have had similar difficulties. My first approach (for my AST) was to use indirect composite. You seem to have the beginnings of that. However it would require a custom newtype for each AST form:
data Exp e = Num Int | Add e e newtype SimpleExp = Exp SimpleExp newtype LabeledExp = Labelled (Exp LabeledExp) For my reduced AST, however, I switched to a different principle. I combined the idea of tagging with the concepts of GADTs and this worked quite succesfully. It even makes it very easy to remove any tagging: data Exp_; data Exp :: * -> * Num :: Int -> Exp a Exp :: Exp a -> Exp a -> Exp a Tag :: a -> Exp a -> Exp a I have combined this with bringert's GADT paper and that worked quite successfully. (However in my case it is a GADT with two parameters as I don't only have Exp's, so it would look more like this: data Exp_; data Var_; data Value_; data Exp :: * -> * -> * where VDef :: String -> Exp Var_ tag VVar :: Exp Var_ tag -> Exp Value_ tag EValue :: Exp Value_ tag -> Exp Exp_ tag EAdd :: Exp Exp_ tag -> Exp Exp_ tag -> Exp Exp_ tag Tag :: tag -> Exp a tag -> Exp a tag ) Hope this helps, Cheers Klaus Ostermann wrote: > Hi all, > > I have a problem which is probably not a problem at all for Haskell experts, > but I am struggling with it nevertheless. > > I want to model the following situation. I have ASTs for a language in two > variatns: A "simple" form and a "labelled" form, e.g. > > data SimpleExp = Num Int | Add SimpleExp SimpleExp > > data LabelledExp = LNum Int String | LAdd LabelledExp LabelledExp String > > I wonder what would be the best way to model this situation without > repeating the structure of the AST. > > I tried it using a fixed point operator for types like this: > > data Exp e = Num Int | Add e e > > data Labelled a = L String a > > newtype Mu f = Mu (f (Mu f)) > > type SimpleExp = Mu Exp > > type LabelledExp = Mu Labelled Exp > > The "SimpleExp" definition works fine, but the LabeledExp definition doesn't > because I would need something like "Mu (\a -> Labeled (Exp a))" where "\" > is a type-level lambda. > > However, I don't know how to do this in Haskell. I'd need something like the > "." operator on the type-level. I also wonder whether it is possible to > curry type constructors. > > The icing on the cake would be if it would also be possible to have a > function > > unlabel :: LabeledExp -> Exp > > that does *not* need to know about the full structure of expressions. > > So, what options do I have to address this problem in Haskell? > > Klaus > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Christophe Poucet Ph.D. Student DESICS - DDT Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – http://www.imec.be -------------------------------------------------------------------------------- <IMEC e-mail disclaimer: http://www.imec.be/wwwinter/email-disclaimer.shtml> _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe