[Haskell-cafe] Variants of a recursive data structure

[Matthias Fischmann]

On Thu, Aug 03, 2006 at 12:51:01PM +0200, Klaus Ostermann wrote:
> To: haskell-cafe at haskell.org
> From: Klaus Ostermann <ostermann at informatik.tu-darmstadt.de>
> Date: Thu, 3 Aug 2006 12:51:01 +0200
> Subject: [Haskell-cafe] Variants of a recursive data structure
> 
> 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.

if you don't need to enforce that an exp is either completely labelled
or not at all, how about this?:

data Exp = Num Int | Add Exp Exp | Label Exp String

this allows you to attach labels wherever you want, at the cost of an
extra case each time you take an expression apart, which can be done
in a separate function:

unlabel :: Exp -> Exp
unlabel (Label e _) = unlabel e
unlabel (Add e e')  = Add (unlabel e) (unlabel e')

> The icing on the cake would be if it would also be possible to have a
> function
> 
> unlabel :: LabeledExp -> Exp

that function is almost identical to the one above.


cheers,
matthias