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