[Haskell-cafe] catamorphisms and attribute grammars
chrisyco+haskell-cafe at gmail.com
Sun Jan 27 08:20:07 CET 2013
Congratulations -- you've just implemented a Moore machine! 
I posted something very much like this just last year . It's a very
common pattern in Haskell, forming the basis of coroutines and
iteratees and many other things.
Edward Kmett includes it in his machines package . His variation,
like mine, hides the state inside a closure, removing the need for
existentials. pipes 2.0 contains one implemented as a free monad .
On Sun, Jan 27, 2013 at 11:03 AM, Petr P <petr.mvd at gmail.com> wrote:
> Dear Haskellers,
> I read some stuff about attribute grammars recently  and how UUAGC 
> 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.
>  http://www.haskell.org/haskellwiki/Attribute_grammar
>  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
> I wonder, is there an existing library that expresses this idea?
> Best regards,
> Petr Pudlak
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe