Emil Axelsson emax at chalmers.se
Mon Jan 28 12:05:42 CET 2013

```Patrick Bahr does something very similar in Modular Tree Automata [1],
also noting the relation to attribute grammars. It's implemented in the
compdata package [2].

[1] Patrick Bahr, Modular Tree Automata (MPC 2012),
http://dx.doi.org/10.1007/978-3-642-31113-0_14

/ Emil

2013-01-26 23:03, Petr P skrev:
>
> 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.
>
> [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
>
>
>
> _______________________________________________