<div dir="ltr">  Hi Chris,<div><br></div><div>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 &quot;count&quot; + &quot;sum&quot; in the example, which could lead to the impression that it&#39;s list oriented.)</div>

<div><br></div><div>However, it seems to me that there is some connection between cata/anamorphisms and free (co)monads generated by a functor. I&#39;m just guessing - perhaps using such a monad in a monadic pipe would lead to a similar result?</div>

<div><br></div><div>BTW, while it seems that using existentials in by Cata data type is natural, I&#39;d like to know if I could do it without them. If you have any ideas, please let me know.</div><div><br></div><div>  Best  regards,</div>

<div>  Petr</div><div><br></div><div>PS: Is there actually anything left that ekmett hasn&#39;t implemented?</div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/1/27 Chris Wong <span dir="ltr">&lt;<a href="mailto:chrisyco+haskell-cafe@gmail.com" target="_blank">chrisyco+haskell-cafe@gmail.com</a>&gt;</span><br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi Petr,<br>
<br>
Congratulations -- you&#39;ve just implemented a Moore machine! [1]<br>
<br>
I posted something very much like this just last year [2]. It&#39;s a very<br>
common pattern in Haskell, forming the basis of coroutines and<br>
iteratees and many other things.<br>
<br>
Edward Kmett includes it in his machines package [3]. His variation,<br>
like mine, hides the state inside a closure, removing the need for<br>
existentials. pipes 2.0 contains one implemented as a free monad [4].<br>
<br>
[1] <a href="http://en.wikipedia.org/wiki/Moore_machine" target="_blank">http://en.wikipedia.org/wiki/Moore_machine</a><br>
[2] <a href="http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Machine-Moore.html" target="_blank">http://hackage.haskell.org/packages/archive/machines/0.2.3/doc/html/Data-Machine-Moore.html</a><br>


[3] <a href="http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html" target="_blank">http://www.haskell.org/pipermail/haskell-cafe/2012-May/101460.html</a><br>
[4] <a href="http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pipe-Common.html" target="_blank">http://hackage.haskell.org/packages/archive/pipes/2.0.0/doc/html/Control-Pipe-Common.html</a><br>
<br>
Chris<br>
<div><div class="h5"><br>
On Sun, Jan 27, 2013 at 11:03 AM, Petr P &lt;<a href="mailto:petr.mvd@gmail.com">petr.mvd@gmail.com</a>&gt; wrote:<br>
&gt;   Dear Haskellers,<br>
&gt;<br>
&gt; I read some stuff about attribute grammars recently [1] and how UUAGC [2]<br>
&gt; can be used for code generation. I felt like this should be possible inside<br>
&gt; Haskell too so I did some experiments and I realized that indeed<br>
&gt; catamorphisms can be represented in such a way that they can be combined<br>
&gt; together and all run in a single pass over a data structure. In fact, they<br>
&gt; form an applicative functor.<br>
&gt;<br>
&gt; [1] <a href="http://www.haskell.org/haskellwiki/Attribute_grammar" target="_blank">http://www.haskell.org/haskellwiki/Attribute_grammar</a><br>
&gt; [2] Utrecht University Attribute Grammar Compiler<br>
&gt;<br>
&gt; To give an example, let&#39;s say we want to compute the average value of a<br>
&gt; binary tree. If we compute a sum first and then count the elements, the<br>
&gt; whole tree is retained in memory (and moreover, deforestation won&#39;t happen).<br>
&gt; So it&#39;s desirable to compute both values at once during a single pass:<br>
&gt;<br>
&gt; -- Count nodes in a tree.<br>
&gt; count&#39; :: (Num i) =&gt; CataBase (BinTree a) i<br>
&gt; count&#39; = ...<br>
&gt;<br>
&gt; -- Sums all nodes in a tree.<br>
&gt; sum&#39; :: (Num n) =&gt; CataBase (BinTree n) n<br>
&gt; sum&#39; = ...<br>
&gt;<br>
&gt; -- Computes the average value of a tree.<br>
&gt; avg&#39; :: (Fractional b) =&gt; CataBase (BinTree b) b<br>
&gt; avg&#39; = (/) &lt;$&gt; sum&#39; &lt;*&gt; count&#39;<br>
&gt;<br>
&gt; Then we can compute the average in a single pass like<br>
&gt;<br>
&gt;     runHylo avg&#39; treeAnamorphism seed<br>
&gt;<br>
&gt; My experiments together with the example are available at<br>
&gt; <a href="https://github.com/ppetr/recursion-attributes" target="_blank">https://github.com/ppetr/recursion-attributes</a><br>
&gt;<br>
&gt; I wonder, is there an existing library that expresses this idea?<br>
&gt;<br>
&gt;   Best regards,<br>
&gt;   Petr Pudlak<br>
&gt;<br>
&gt;<br>
</div></div>&gt; _______________________________________________<br>
&gt; Haskell-Cafe mailing list<br>
&gt; <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
&gt; <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
&gt;<br>
</blockquote></div><br></div></div>