Hello Klaus, Indeed I am reerring to the ICFP'06 paper. However after reading your other posts, it seems you want tags to be something that are guaranteed by the type. I wanted this too for my highlevel AST (but as you can see with the newtype stuff, it can be very unpretty). However once I had completely typed my input and added the necessary tagging to ensure everything was correct, I then moved onto a lower AST (namely ANF) where I used the proposed solution. However if you want the type-guaranteed labelling per node, this solution will not work. cheers Klaus Ostermann wrote:
Hi Christophe,
you are right of course. It works with a custom newtype.
I still wonder whether it is possible to do the same by reusing the "Mu" type constructor. It captures exactly the recursion structure you use for the LabeledExp type, hence it would be nice to reuse it here.
Thanks for the GADT suggestion. I assume you are referring to Bringert's ICFP'06 paper? I will take a look.
Klaus
-----Original Message----- From: Christophe Poucet [mailto:christophe.poucet@gmail.com] Sent: Thursday, August 03, 2006 1:02 PM To: Klaus Ostermann Cc: haskell-cafe@haskell.org Subject: Re: [Haskell-cafe] Variants of a recursive data structure
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
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
Klaus Ostermann wrote: 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
--------------------------------------------------------------------------------