[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
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
More information about the Haskell-Cafe
mailing list