Re: [Haskell-cafe] catamorphisms and attribute grammars

Hi Chris, 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 oriented.) 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 similar result? 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. Best regards, Petr PS: Is there actually anything left that ekmett hasn't implemented? 2013/1/27 Chris Wong

Hi Petr,

Congratulations -- you've just implemented a Moore machine! [1]

I posted something very much like this just last year [2]. 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 [3]. 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 [4].

[1] http://en.wikipedia.org/wiki/Moore_machine [2] http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Mac... [3] http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html [4] http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pip...

Chris

...

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,

On Sun, Jan 27, 2013 at 11:03 AM, Petr P wrote: 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

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe