[Haskell-cafe] Variants of a recursive data structure
ostermann at informatik.tu-darmstadt.de
Thu Aug 3 06:51:01 EDT 2006
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
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?
More information about the Haskell-Cafe