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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
