There are a number of ways to fix this of various complexity, depending on how many kinds of statements you have in your language and how adverse you are to code duplication.<br><br>One option is to remove the recursion from your statement type and to make a &#39;base functor&#39; like you&#39;ve proposed with your link based ADT.<br>
<br>data Stmt a = Slf Test [a] [a] | ...<br><br>and then make that recursive by using a newtype to make the folding explicit.<br><br>newtype Mu f = In { out :: f (Mu f) } <br><br>Now you can work on Mu Stmt which is a fixed point of your statement data type and get your original meaning, or work with Stmt Int and have a statement type that indexes statements by # and can look them up in a control flow graph or some such.<br>
<br>You can even attach annotations at every level by using a different ADT to wrap yourself up. (For the category-theory inclined, this gives rise to something known as the cofree comonad of your base functor)<br><br>newtype Ann f e = Ann e (f (Ann f e))<br>
<br>So now you can have something like:<br><br>Ann 2 (SIf ... (Ann 1 (Var &quot;X&quot;)) (Ann 1 (Var &quot;Y&quot;))<br><br>if you wanted to count the number of variable references in a subtree for instance.<br><br>On the other hand, rarely does a programming language consist solely of statements. You often have expressions and other types floating around and tying with an explicit Mu can sometimes get in the way of that.<br>
<br>Forgetting those definitions for a moment, we can try to fix the one statement type problem.<br><br>You can use some interesting GADT based solutions to fix that, but another approach that I&#39;ve been using recently is to use explicit recursion in a slightly different place.<br>
<br>type (v :&gt; f) = f (v f)<br>data Var (f :: * -&gt; *) = V String<br>data Exp f <br>    = App (Exp :&gt; f) (Exp :&gt; f)<br>    | Lam (Var :&gt; f) (Exp :&gt; f)<br>    | Var (Var :&gt; f)<br>data Stmt f<br>    = If (Exp :&gt; f) [Stmt :&gt; f] [Stmt :&gt; f]<br>
    | ...<br>          <br>Now we can have a lot of different kinds of expressions based on what we substitute in for f.<br><br>data Ann a e = Ann a e<br>newtype Mu e = Mu e<br>data Free a e = Return a | Free e<br>newtype Base a e = Base a<br>
<br>now:<br><br> Stmt (Base Int) -- is a statement wrapped around integers<br> Stmt (Ann Int) -- is a statement wrapped around subtrees of various types annotated with integers<br> Stmt Mu -- is your old statement type with newtype Mu wrappers on its children.<br>
 Stmt (Free Int) is your old statement data type, with occasional integer place holders for unexpanded portions of the tree, they can act as standins for Exps, Vars, etc.<br><br>You can then borrow a trick from a recent post of mine:<br>
<br><a href="http://comonad.com/reader/2009/incremental-folds/">http://comonad.com/reader/2009/incremental-folds/</a><br><br>with some minor modifications to extract data incrementally or return results as you grow the syntax tree.<br>
<br>The design space is large and there are a lot of options to explore around here, so don&#39;t take any of this as the one and only way to implement a syntax ADT. =)<br><br>-Edward Kmett<br><br><div class="gmail_quote">
On Sun, Aug 2, 2009 at 1:25 AM, Michal D. <span dir="ltr">&lt;<a href="mailto:michal.dobrogost@gmail.com">michal.dobrogost@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I&#39;m in the process of writing a toy compiler but I&#39;m having some<br>
trouble trying to make my datatypes general. For example, using parsec<br>
I parse statements as:<br>
<br>
data Stmt = SIf Test [Stmt] [Stmt]   |   ...<br>
<br>
However, when it&#39;s time to create a control flow graph it would be<br>
nice to represent statements as (the Int&#39;s signify the node id&#39;s for<br>
either case of the if statement):<br>
<br>
data Stmt = SIf Test Int Int   |   ...<br>
<br>
So, in a eureka moment I decided that this should be allowable with<br>
the following declaration:<br>
<br>
data Stmt link = SIf Test link link   |   ...<br>
<br>
Ofcourse, the problem is trying to declare the resulting type for<br>
parsing: &quot;parse -&gt; Stmt [Stmt [Stmt ....]]&quot;. Any hints on whether<br>
there is a way to accomplish what I&#39;m trying to do or do I have to<br>
bite the bullet and declare two seperate datatypes? I tried being<br>
clever and declaring a &#39;helper&#39; type as &quot;type StmtRec = Stmt [StmtRec]&quot;<br>
but to no avail... GHC won&#39;t let it slide: &quot;Cycle in type synonym declarations&quot;!<br>
<br>
Cheers,<br>
<br>
Michal<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>