<html><head><meta http-equiv="Content-Type" content="text/html charset=iso-8859-1"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">You have applied the so-called banana-split theorem, as described e.g. in <a href="http://www.cs.ox.ac.uk/jeremy.gibbons/publications/acmmpc-calcfp.pdf">http://www.cs.ox.ac.uk/jeremy.gibbons/publications/acmmpc-calcfp.pdf</a><div><br></div><div>Indeed you are right in noticing the correspondence between AG's and catamorphims; actually I see AG's as a domain specific language for constructing algebras.</div><div><br></div><div>Since we believe in embedded domain specific languages we have developed a library for constructing attribute grammars in Haskell, which is described in our ICFP paper:</div><div><br></div><div><div><br></div><div>@inproceedings{1596586,</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Address = {New York, NY, USA},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Author = {Viera, Marcos and Swierstra, S. Doaitse and Swierstra, Wouter},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Booktitle = {ICFP '09: Proceedings of the 14th ACM SIGPLAN international conference on Functional programming},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Date-Added = {2009-10-05 22:06:26 +0200},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Date-Modified = {2009-10-05 22:06:26 +0200},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Doi = {<a href="http://doi.acm.org/10.1145/1596550.1596586">http://doi.acm.org/10.1145/1596550.1596586</a>},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Isbn = {978-1-60558-332-7},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Location = {Edinburgh, Scotland},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Pages = {245--256},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Publisher = {ACM},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Title = {Attribute grammars fly first-class: how to do aspect oriented programming in Haskell},</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>Year = {2009}}</div></div><div><br></div><div>where you will find the problem you are solving done using the library.</div><div><br></div><div>On March 8 2013 Marcos Viera hopes to defend his Ph.D. thesis at Utrecht University. His thesis contains the progress we have made in this area in recent years. You can find it at the bottom op the page; amongst others you can use the UUAGC nowadays to generate this code form uuagc input.</div><div><br></div><div><a href="http://www.cs.uu.nl/wiki/bin/view/Center/PhDs">http://www.cs.uu.nl/wiki/bin/view/Center/PhDs</a></div><div><br></div><div> Doaitse Swierstra</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br><div><div>On Jan 26, 2013, at 23:03 , Petr P <<a href="mailto:petr.mvd@gmail.com">petr.mvd@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"><div dir="ltr"> Dear <span class="" style="">Haskellers</span>,<div><br></div><div>I read some stuff about attribute grammars recently [1] and how <span class="" style="">UUAGC</span> [2] can be used for code generation. I felt like this should be possible inside Haskell too so I did some experiments and I realized that indeed <span class="" style="">catamorphisms</span> can be represented in such a way that they can be combined together and all run in a single pass over a data structure. In fact, they form an applicative <span class="" style="">functor</span>.</div>
<div><div><br></div><div>[1] <a href="http://www/">http://www</a>.<span class="" style="">haskell</span>.org/<span class="" style="">haskellwiki</span>/Attribute_grammar</div><div>[2] Utrecht University Attribute Grammar Compiler</div>
</div><div><br></div><div style="">To give an example, let's say we want to compute the average value of a binary tree. If we compute a sum first and then count the elements, the whole tree is retained in memory (and moreover, deforestation won't happen). So it's desirable to compute both values at once during a single pass:</div>
<div style=""><br></div><div style="">-- Count nodes in a tree.</div><div style=""><div>count' :: (<span class="" style="">Num</span> i) => <span class="" style="">CataBase</span> (<span class="" style="">BinTree</span> a) i</div><div>
count' = ...</div><div><br></div><div>-- Sums all nodes in a tree.</div><div>sum' :: (<span class="" style="">Num</span> n) => <span class="" style="">CataBase</span> (<span class="" style="">BinTree</span> n) n</div><div>
sum' = ...</div><div><br></div><div>-- Computes the average value of a tree.</div><div>avg' :: (Fractional b) => <span class="" style="">CataBase</span> (<span class="" style="">BinTree</span> b) b</div><div>avg' = (/) <$> sum' <*> count'<br>
</div><div><br></div><div style="">Then we can compute the average in a single pass like</div><div style=""><br></div><div style=""> <span class="" style="">runHylo</span> avg' <span class="" style="">treeAnamorphism</span> seed</div>
<div style=""><br></div><div style="">My experiments together with the example are available at https://<span class="" style="">github</span>.com/<span class="" style="">ppetr</span>/recursion-attributes</div><div style=""><br></div><div style="">
I wonder, is there an existing library that expresses this idea?</div><div style=""><br></div><div style=""> Best regards,</div><div style=""> Petr <span class="" style="">Pudlak</span></div><div style=""><br></div></div></div>
_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>http://www.haskell.org/mailman/listinfo/haskell-cafe<br></blockquote></div><br></div></body></html>