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