[Haskell-cafe] Variants of a recursive data structure

[Niklas Broberg]

On 8/3/06, Klaus Ostermann <ostermann at informatik.tu-darmstadt.de> wrote:
> thanks for your suggestion. Can you explain how your solution is better than
> the very simple one, i.e.,
>
> data Exp e = Num Int | Add e e
> data Labeled  = L String e
> newtype SimpleExp = Exp SimpleExp
> newtype LabeledExp = Labelled (Exp LabeledExp)

I'm not sure it *is* better, I guess it's a matter of taste, and just
what you want to do with it. I also realize that it's not quite what
you wanted in your first post, since my definition will not require
every subexpression to be labelled, and there can be labels on already
labelled expressions. None of this is possible with the two-tier
indirect composite you show above, but on the other hand it will
guarantee that it follows a given structure (this guarantee could be
added to my data type with more type class hackery though).

The main advantage I can see is that functions written to work over
full expressions, Exp a, automatically work on simple expressions,
since it's the same data type. For instance, if you write

 eval :: Exp a -> Int
 eval (Num n) = n
 eval (Add e1 e2) = eval e1 + eval e2
 eval (Label _ e) = eval e

you could use eval on terms of type SimpleExp without further ado. But
if you have no use for this functionality, then it won't be an
advantage to you. Something that could be considered a disadvantage is
that it requires the use of GADTs, which are only supported by GHC,
and that support is still somewhat shaky.

Hope this helps you in deciding what to use! :-)

/Niklas