Hi Chris, While the two things solve similar problems and have other similarities, they are still quite different.
It's hard to call Petr's type a machine — there's no dynamics in it. It's just a pair of an f-algebra and finalizer. Values of your type return themselves — it is exactly this recursion that makes them "machines". And the problem solved are different. Catamorphisms are not the same as folds in the sense of Data.Foldable. Folds get elements one at a time, while a catamorphism sees the structure of the tree. For instance, it is possible to write an evaluator for an expression AST using catamorphisms, but not using Moore machines[*], because you won't know what the operations are. [*] without linearizing the tree beforehand Roman * Chris Wong <[email protected]> [2013-01-27 20:20:07+1300] > 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-Machine-Moore.html > [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-Pipe-Common.html > > Chris > > On Sun, Jan 27, 2013 at 11:03 AM, Petr P <[email protected]> wrote: > > 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 > > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > [email protected] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
