[Haskell-cafe] Variants of a recursive data structure

[paul at theV.net]

On Thu, Aug 03, 2006 at 05:25:07PM +0200, Klaus Ostermann wrote:
> Hi Niklas,
>
> 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)

hmm, I'm not sure it works, if at all. With the above definition
how do you construct a vallue of SimpleExp? In hugs, I type

Main> :t Num 1
Num 1 :: Exp a

but then

Main> Num 1 :: SimpleExp
ERROR - Type error in type annotation
*** Term           : Num 1
*** Type           : Exp a
*** Does not match : SimpleExp

Here is a solution to your original problem. 

The proper way is to do type level fixpoint 

> data Fix a = Fix (a (Fix a))

(which you called Mu), and also a sum type, which is explained below.

So initially you want Exp

> data Exp e = Num Int | Add e e

Now, Fix Exp becomes what you want for the simple expression.

> type SimpleExp = Fix Exp

Here is a little evaluation function

 eval :: SimpleExp -> Int
 eval (Fix (Num i)) = i
 eval (Fix (Add e1 e2)) = eval e1 + eval e2

But this is not exactly versatile, you may want to
extend the eval when you add new data constructors.
Here is a better one 

> e eval (Num i) = i
> e eval (Add e1 e2) = eval e1 + eval e2

so to evaluate SimpleExp, you use

> evalE :: SimpleExp -> Int
> evalE (Fix e1) = e evalE e1

evalE is actually a fixed point of e.

Then you want to label the Exp, but without duplicating
the Exp structure.

> data Label e = Label String e

the eval for Labelled stuff is just

> f eval (Label _ e) = eval e

By now, both Exp and Label are actually type level functions.
To make Label as an extension to Exp type, you need the
fixed point of the sum of them, i.e., this fixed point
is both the fixed point of Exp and Label.

> data Sum a b c = Lt (a c)
>                | Rt (b c)

Fix (Sum Exp Label) is all you need!

> type LabelledExp = Fix (Sum Exp Label)

eval for the LabelledExp is

> g eval (Lt x) = e eval x
> g eval (Rt y) = f eval y
>
> evalLE :: LabelledExp -> Int
> evalLE (Fix e1) = g evalLE e1

So we have achieved extending both original data type and evaluation
function without modifying them.

to easily construct data of LabelledExp, little helpers are handy

> num = Fix . Lt . Num
> add x = Fix . Lt . (Add x)
> label l = Fix . Rt . (Label l)

here are a few examples of using them

> t1 = num 1
> t2 = add t1 t1
> t1' = label "t1" t1
> t2' = label "t2" (add t1' t1')

to convert from LabelledExp to SimpleExp is also easy

> unlabel :: LabelledExp -> SimpleExp
> unlabel (Fix (Rt (Label _ e1))) = unlabel e1
> unlabel (Fix (Lt (Num i))) = Fix (Num i)
> unlabel (Fix (Lt (Add e1 e2))) = Fix (Add (unlabel e1) (unlabel e2))

This solution perhaps isn't what you intended, as it doesn't enforce that
there must be a Label for every LabelledExp value. But it is a nice way
to show how to extend data types and their functions without modifying 
them.

Regards,
Paul Liu