[Haskell-cafe] Variants of a recursive data structure

[Klaus Ostermann]

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