[Haskell-cafe] Variants of a recursive data structure

[tpledger at ihug.co.nz]

Klaus Ostermann wrote:
[...]
> 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.

One way, that I haven't spotted in any of the replies so
far, is to declare a composition type

    data BComp m n a = BC (m (n a))

as seen in
http://web.cecs.pdx.edu/~mpj/pubs/springschool.html , so
that

    type LabelledExp = Mu (BComp Labelled Exp)

See
http://haskell.cs.yale.edu/pipermail/haskell/2001-May/003942.html
for more crafty tricks, including making Eq instances for
such Mu-based recursive structures.

Regards,
Tom