[Haskell-cafe] Re: Cyclic data declarations

[Heinrich Apfelmus]

Michal D. wrote:
> I'm in the process of writing a toy compiler but I'm having some
> trouble trying to make my datatypes general. For example, using parsec
> I parse statements as:
> 
> data Stmt = SIf Test [Stmt] [Stmt]   |   ...
> 
> However, when it's time to create a control flow graph it would be
> nice to represent statements as (the Int's signify the node id's for
> either case of the if statement):
> 
> data Stmt = SIf Test Int Int   |   ...

(I recommend to replace  Int  with something more descriptive, like

    type Id = Int

)

> So, in a eureka moment I decided that this should be allowable with
> the following declaration:
> 
> data Stmt link = SIf Test link link   |   ...
> 
> Ofcourse, the problem is trying to declare the resulting type for
> parsing: "parse -> Stmt [Stmt [Stmt ....]]". Any hints on whether
> there is a way to accomplish what I'm trying to do or do I have to
> bite the bullet and declare two seperate datatypes? I tried being
> clever and declaring a 'helper' type as "type StmtRec = Stmt [StmtRec]"
> but to no avail... GHC won't let it slide: "Cycle in type synonym declarations"!

   newtype StmtRec = StmtRec (Stmt [StmtRec])

will do. More generally, you can use

   newtype Fix f = In { out :: f (Fix f) }

and define

   type StmtRec = Fix ([] `O` Stmt)

where  O  denotes composition of functors

   newtype O f g a = O (f (g a))


Introducing a parameter in  Stmt  like you did and tying the recursion
afterwards is a known technique, but I can't seem to find a wiki page
that concisely explains it right now.


Regards,
apfelmus

--
http://apfelmus.nfshost.com