[Haskell-cafe] Cyclic data declarations

Jason Dagit dagit at codersbase.com
Sun Aug 2 01:50:57 EDT 2009

On Sat, Aug 1, 2009 at 10:25 PM, Michal D. <michal.dobrogost at gmail.com>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]   |   ...

One of your types could be:
newtype Block = Block [Stmt]

Then you could have:
data Stmt = SIf Test Block Block | ...

> 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   |   ...

Depending on the amount of code duplication, I think I'd actually make two
separate data types.

data GStmt = GIf Test Int Int | ...

And have a function:
toFlowGraph :: Stmt -> GStmt

> So, in a eureka moment I decided that this should be allowable with
> the following declaration:
> data Stmt link = SIf Test link link   |   ...

Clever, but I don't think I would do it this way.

> 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"!

I'd have to see your parser, but it shouldn't be too hard to work around
this depending on how you want to solve it.  By the way, for your StmtRec
you probably want a newtype instead of a type.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090802/c8ad96b5/attachment.html

More information about the Haskell-Cafe mailing list