[Haskell-cafe] Re: Cyclic data declarations

Job Vranish jvranish at gmail.com
Mon Aug 3 17:07:20 EDT 2009

I ran into exactly the same problem while working on my own toy language :)

I used a fixed point datatype to solve it as well. This is really the best
way, as it lets your expression (or statment) type be a member of
functor/foldable/traversable, which is super handy. I made a graph module
that lets me convert any fixpointed functor into a graph, which made the
rest of that whole process much nicer. If you're interested in the graph
module, let me know :)

I think that in an ideal world haskell would have some way of allowing
infinite types if you asked for them explicitly (say in the type signature
somehow) and then just automatically wrap/unwrap everything with newtypes
behind the scenes (well maybe in an ideal world it wouldn't have to do this
either). This wouldn't change the underlying semantics, but would get rid of
alot of messyness.

Infinite types are possible, My toy language infers infinite types just fine
:) and I think Ocaml has an option for them, but niether of those have type
classes so I'm not sure how compatable the idea is with haskell in general.

- Job

On Sun, Aug 2, 2009 at 9:06 PM, Michal D. <michal.dobrogost at gmail.com>wrote:

> >
> >   newtype StmtRec = StmtRec (Stmt [StmtRec])
> >
> That's pretty much were I threw in the towel last night. Except I had
> a bunch of places where I had to add the extra constructor statements.
> I wish there was a solution that didn't require these... they really
> butcher pattern matching clarity.
> > 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))
> >
> Thanks for that! This provoked some thought on my part about what
> exactly is going on. I think I could solve this if I added some way to
> identify that a type parameter is actually referring to the whole
> type. Say we had a reserved word "fixpoint" for this. Then we'd have
> something like:
> data Stmt x = SIf x x
> then when we actually go to use it, it would be referred to as the type:
> "Stmt [fixpoint]"
> Which would get treated exactly like the data declaration:
> data Stmt = SIf [Stmt] [Stmt]
> I'll need to add the newtype declaration for the code but I'd be
> interested if anyone had further thoughts on this topic. I have an
> implementation of both approaches on a toy parser, but I doubt
> anyone's interested in seeing that.
> Michal
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090803/7e4c707c/attachment.html

More information about the Haskell-Cafe mailing list