[Haskell-cafe] catamorphisms and attribute grammars
petr.mvd at gmail.com
Sun Jan 27 09:40:31 CET 2013
thanks for insightful links. At the first glance, I think the main
difference is that machines and iteratees process streams of data, while
catamorphisms work on general recursive data structures. (I used "count" +
"sum" in the example, which could lead to the impression that it's list
However, it seems to me that there is some connection between
cata/anamorphisms and free (co)monads generated by a functor. I'm just
guessing - perhaps using such a monad in a monadic pipe would lead to a
BTW, while it seems that using existentials in by Cata data type is
natural, I'd like to know if I could do it without them. If you have any
ideas, please let me know.
PS: Is there actually anything left that ekmett hasn't implemented?
2013/1/27 Chris Wong <chrisyco+haskell-cafe at gmail.com>
> Hi Petr,
> 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 .
>  http://en.wikipedia.org/wiki/Moore_machine
>  http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html
> 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
> > 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,
> > 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
> > 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 at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe