[Haskell-cafe] Variants of a recursive data structure
paul at theV.net
paul at theV.net
Fri Aug 4 01:57:24 EDT 2006
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
More information about the Haskell-Cafe
mailing list