[Haskell-cafe] catamorphisms and attribute grammars
Petr P
petr.mvd at gmail.com
Sat Jan 26 23:03:51 CET 2013
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130126/809005f3/attachment.htm>
More information about the Haskell-Cafe
mailing list