[Haskell-cafe] Variants of a recursive data structure

tpledger at ihug.co.nz tpledger at ihug.co.nz
Mon Aug 7 06:34:07 EDT 2006

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

    type LabelledExp = Mu (BComp Labelled Exp)

for more crafty tricks, including making Eq instances for
such Mu-based recursive structures.


More information about the Haskell-Cafe mailing list