Howdy. I've been working with this stuff pretty intimately in the last few days; here's what I came up with. It's similar to Josef's except let's us have many labels. "Type-level currying" requires newtypes because any appearance of a type synonym must be fulled applied. newtypes relax that restraint. -- An annotated functor is the applied functor with a label newtype Anno f l x = Anno (f x, l) anno f_x l = Anno (f_x, l) unAnno (Anno (f_x, _)) = f_x getAnno (Anno (_, l)) = l -- it keeps it functor property instance Functor f => Functor (Anno f l) where fmap f (Anno (f_x, l)) = Anno (fmap f f_x, l) -- An annotated AST is created by annotating the functor before fixing. newtype AnnoAST f l = AnnoAST { unAnnoAST :: Fix (Anno f l) } -- this function takes a normal term and annotates it with all () fromAST :: Functor f => Fix f -> AnnoAST f () fromAST = AnnoAST . cata phi where phi = inn . (`anno` ()) toAST :: Functor f => AnnoAST f lab -> Fix f toAST = cata phi . unAnnoAST where phi = inn . unAnno cata phi = phi . fmap (cata phi) . out -- finally, your request is served data Exp x = Num Integer | Add x x type SimpleExp = Fix Exp type LabelledExp = AnnoAST Exp String unLabel term = toAST term I'm a little late on this post, but I think this is the general form of labeling (within the solution involving explicit functors and fixed points). Now you could, for instance, label your AST with types instead of just strings--anything for that matter. To take it one step further (this is what I just spent the last couple days coding so it works for any language constructed this way), check out: "Comonadic functional attribute evaluation" by Tarmo Uustalu and Varmo Vene It's pretty cool. HTH, Nick On 8/3/06, Josef Svenningsson <josef.svenningsson@gmail.com> wrote:
Klaus,
You've gotten many fine answers to your question. I have yet another one which is believe is closest to what you had in mind. The key to the solution is to add an extra type parameter to Labelled like so:
data Labelled f a = L String (f a)
Now you can use it to form new recursive type with Mu:
type LabelledExp = Mu (Labelled Exp)
And it is also possible to write an unlabel function which knows very little about the structure of Exp:
unlabel :: Functor f => Mu (Labelled f) -> Mu f unlabel (Mu (L _ r)) = Mu (fmap unlabel r)
Another bonus is that it's all Haskell98.
The name I came up with for the trick of adding a higher-kinded type parameter to Labelled is "Functor Transformer". "Transformer" - because it transforms the type it is applied to (in this case Exp), and "Functor" - because when using Mu to tie the recursive knot one often require the types to be instances of functor, as I'm sure you're aware of.
Good luck with whatever it is you need this for.
Josef
On 8/3/06, Klaus Ostermann <ostermann@informatik.tu-darmstadt.de> 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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe