[Haskell-cafe] Variants of a recursive data structure

[Klaus Ostermann]

Hi Christophe,

you are right of course. It works with a custom newtype.

I still wonder whether it is possible to do the same by reusing the "Mu"
type constructor. It captures exactly the recursion structure you use for
the LabeledExp type, hence it would be nice to reuse it here.

Thanks for the GADT suggestion. I assume you are referring to Bringert's
ICFP'06 paper? I will take a look.

Klaus

-----Original Message-----
From: Christophe Poucet [mailto:christophe.poucet at gmail.com] 
Sent: Thursday, August 03, 2006 1:02 PM
To: Klaus Ostermann
Cc: haskell-cafe at haskell.org
Subject: Re: [Haskell-cafe] Variants of a recursive data structure

Hello,

I have had similar difficulties.  My first approach (for my AST) was to use
indirect composite.  You seem to have the beginnings of that.  However it
would require a custom newtype for each AST form:

data Exp e = Num Int | Add e e

newtype SimpleExp = Exp SimpleExp
newtype LabeledExp = Labelled (Exp LabeledExp)


For my reduced AST, however, I switched to a different principle.  I
combined the idea of tagging with the concepts of GADTs and this worked
quite succesfully.  It even makes it very easy to remove any tagging:

data Exp_;

data Exp :: * -> *
  Num :: Int -> Exp a 
  Exp :: Exp a -> Exp a -> Exp a
  Tag :: a -> Exp a -> Exp a

I have combined this with bringert's GADT paper and that worked quite
successfully.  (However in my case it is a GADT with two parameters as I
don't only have Exp's, so it would look more like this:

data Exp_;
data Var_;
data Value_;
data Exp :: * -> * -> * where
  VDef   :: String -> Exp Var_ tag
  VVar   :: Exp Var_ tag -> Exp Value_ tag
  EValue :: Exp Value_ tag -> Exp Exp_ tag
  EAdd   :: Exp Exp_ tag -> Exp Exp_ tag -> Exp Exp_ tag
  Tag    :: tag -> Exp a tag -> Exp a tag

)

Hope this helps,

Cheers

Klaus Ostermann wrote:
> 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.
> 
> I tried it using a fixed point operator for types like this:
> 
> 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. I also wonder whether it is possible to
> curry type constructors.
> 
> The icing on the cake would be if it would also be possible to have a
> function
> 
> unlabel :: LabeledExp -> Exp
> 
> that does *not* need to know about the full structure of expressions.
> 
> So, what options do I have to address this problem in Haskell?
> 
> Klaus
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 


-- 
Christophe Poucet
Ph.D. Student
DESICS - DDT

Phone:+32 16 28 87 20
E-mail: Christophe (dot) Poucet (at) imec (dot) be
IMEC vzw - Register of Legal Entities Leuven VAT BE 0425.260.668 -
Kapeldreef 75, B-3001 Leuven, Belgium - http://www.imec.be
----------------------------------------------------------------------------
----
<IMEC e-mail disclaimer: http://www.imec.be/wwwinter/email-disclaimer.shtml>