You have applied the so-called banana-split theorem, as described e.g. in 
http://www.cs.ox.ac.uk/jeremy.gibbons/publications/acmmpc-calcfp.pdf

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.

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:


@inproceedings{1596586,
        Address = {New York, NY, USA},
        Author = {Viera, Marcos and Swierstra, S. Doaitse and Swierstra, 
Wouter},
        Booktitle = {ICFP '09: Proceedings of the 14th ACM SIGPLAN 
international conference on Functional programming},
        Date-Added = {2009-10-05 22:06:26 +0200},
        Date-Modified = {2009-10-05 22:06:26 +0200},
        Doi = {http://doi.acm.org/10.1145/1596550.1596586},
        Isbn = {978-1-60558-332-7},
        Location = {Edinburgh, Scotland},
        Pages = {245--256},
        Publisher = {ACM},
        Title = {Attribute grammars fly first-class: how to do aspect oriented 
programming in Haskell},
        Year = {2009}}

where you will find the problem you are solving done using the library.

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.

http://www.cs.uu.nl/wiki/bin/view/Center/PhDs

 Doaitse Swierstra





On Jan 26, 2013, at 23:03 , Petr P <petr....@gmail.com> wrote:

>   Dear Haskellers,
> 
> I read some stuff about attribute grammars recently [1] and how UUAGC [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 
> catamorphisms 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 functor.
> 
> [1] http://www.haskell.org/haskellwiki/Attribute_grammar
> [2] Utrecht University Attribute Grammar Compiler
> 
> 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:
> 
> -- Count nodes in a tree.
> count' :: (Num i) => CataBase (BinTree a) i
> count' = ...
> 
> -- Sums all nodes in a tree.
> sum' :: (Num n) => CataBase (BinTree n) n
> sum' = ...
> 
> -- Computes the average value of a tree.
> avg' :: (Fractional b) => CataBase (BinTree b) b
> avg' = (/) <$> sum' <*> count'
> 
> Then we can compute the average in a single pass like
> 
>     runHylo avg' treeAnamorphism seed
> 
> My experiments together with the example are available at 
> https://github.com/ppetr/recursion-attributes
> 
> I wonder, is there an existing library that expresses this idea?
> 
>   Best regards,
>   Petr Pudlak
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to