<p>Joyal's Combinatorial Species, Sedgwick/Falojet's "admissible constructions" of Analytic Combinatorics, and Yorgey's Haskell Species are all good.</p>

<p><a href="http://www.cs.dartmouth.edu/~doug/music.ps.gz" rel="nofollow">Power Series Power Serious</a> by McIlroy of UNIX diff fame is also a must read, as is the chapter on corecursion in The Haskell Road to Logic Maths and Programming.</p>

<p>The historical works by <a href="http://rads.stackoverflow.com/amzn/click/0387970649" rel="nofollow">Buchi</a> edited by Saunders MacLane and <a href="http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1963-7ChomskyAlgebraic.pdf" rel="nofollow">Chomsky/Schützenberger</a> make the connection between power series, algebras, trees, and finite state automata. The Transfer Matrix Method described in Stanley shows you how to compute generating functions from weighted automata.</p>

<p>I'm still working out the best way to translate between the domains (GF, weighted automata, algebra, tree, recursion) efficiently. Right now I'm shelling out to SymPy since there isn't a good Haskell symbolics package yet.</p>

<p>Personally, I've taken the iteration graph of an endofuction then calculated a min dominating set on it to get an exact black box search bound,  <a href="http://oeis.org/A186202" rel="nofollow">http://oeis.org/A186202</a> Not sure what types of complexity results you were searching for, but that technique is very powerful in examining any endofuction over a finite set.</p>

<p>--Original Oct 2 '14 at 15:37 answer--</p>

<p>Take a look at Brent Yorgey's thesis which follows the paper of his you cited. <a href="http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf" rel="nofollow">http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf</a></p>

CC BY-SA 3.0
2014-10-02T15:37:07.590Z
2015-07-13T13:51:09.070Z
2015-07-13T13:51:09.070Z
Chad Brewbaker
<p>Dave Clarke's comment is quite important. Generally fusion doesn't change the O(-) efficiency.  However, of particular interest is Liu, Cheng, and Hudak's work on Causal Commutative Arrows. Programs written with them are necessarily optimizable, in part through stream fusion, to a single loop free of dynamic memory allocation and intermediate structures: <a href="http://haskell.cs.yale.edu/?post_type=publication&amp;p=72" rel="nofollow">http://haskell.cs.yale.edu/?post_type=publication&amp;p=72</a></p>

CC BY-SA 3.0
2011-01-25T16:13:54.420Z
2014-10-03T03:36:54.187Z
2014-10-03T03:36:54.187Z
sclv
<p>I have been trying to read “<a href="http://rads.stackoverflow.com/amzn/click/0521513383" rel="nofollow noreferrer">Pearls of Functional Algorithm design</a>”, and subsequently “<a href="http://rads.stackoverflow.com/amzn/click/013507245X" rel="nofollow noreferrer">The Algebra of Programming</a>”, and there is an obvious correspondence between recursively (and polynomially) defined data types and combinatorial objects, having the same recursive definition and subsequently leading to the same formal power series (or generating functions), as shown in the introductions to combinatorial species (I read “<a href="http://ozark.hendrix.edu/~yorgey/pub/species-pearl.pdf" rel="nofollow noreferrer">Species and Functors and Types, Oh My!</a>”).</p>

<blockquote>
  <p>So, for the first question, is there a way to recover the generating (recursive) equation from the power series? That’s an afterthought though.</p>
</blockquote>

<p>I was more interested in the notion of initial algebras and final co-algebras as kind of “defining procedures about the data structure”. There are some practical rules in functional programming, concerning composition, products of mapping between algebras and similar, described for example <a href="http://www.comlab.ox.ac.uk/ralf.hinze/publications/IFL10.pdf" rel="nofollow noreferrer">in this tutorial</a>. It seems to me that this could be quite powerful way to approach complexity and for example, it looks fairly straightforward to recover Master’s theorem in such context (I mean, you have to do the same argument, so not much gain in this instance), and the unique catamorphism from the initial algebra and the fact (am I mistaken?) that the algebras between A and FA for F-polynomial functor are isomorphic, makes it look to me that such approach could have a lot of benefits in analysing complexity of operations over data structures.</p>

<p>From practical standpoint, looks like fusion rules (basically, ways to compose algebra morphisms with one another, coalgebra morphisms, and general morphisms) are very powerful optimization technique for program transformation and refactoring. Am I right in thinking that full utilization of these rules can produce optimal program (no unnecessary intermediate data structures or other extra operations). </p>

<blockquote>
  <p>Am I onto something (and what) here? Is it beneficiary (from learning standpoint) to try to look about computational complexity in this way? Are the structures, for which we can have "nice" initial algebras somehow too limited for some problems? </p>
</blockquote>

<p>I’m mostly trying to find a way to think about complexity in terms of the structure of the search space and the way the "search space" and "search algorithm" interact through some "nice" object like the initial algebra of the functor and to understand if it's useful to try to view things this way, when looking at more complicated structures. </p>

CC BY-SA 3.0
2017-03-16T00:33:07.010Z
I want to point out that there are other ways to represent graphs than by complicated pointer structures. Particularly, one can represent them inductively, by a series of changes or additions @DaveClarke. I'm sure the same is true for other structures such as this, though I don't want to say so categorically as I'm not an expert on initial algebras and their limitations.
Samuel Schlesinger
CC BY-SA 2.5
2011-01-25T05:45:00.257Z
can you reformat to make this readable?
Lev Reyzin
CC BY-SA 2.5
2011-01-25T09:24:48.773Z
There are two potential problems with your ideas. Firstly, not all data structures can be represented using initial algebras. Any general graph or complicated pointer structure will not be the initial algebra of any functor. Secondly, fusion rules and so forth will generally only improve the efficiency of the code, rather than change the O(-)-efficiency of the algorithm (though I do know of exceptions).
Dave Clarke
CC BY-SA 2.5
2011-01-26T08:46:51.870Z
Thanks, Dave, I am trying to read the Algorithmic Game theory book, and the algorithms in traditional treatments are specified mostly operationally,so to speak,and was wondering if there is general way to approach them, and initial algebras etc looked nice for that,but lack of correspondence between general data structure and functors is a problem. @sclv: Thanks, I will look at it!
Stefan Petrov
<cc.complexity-theory><co.combinatorics><functional-programming><ct.category-theory>
Category theory, computational complexity, and combinatorics connections?
Stefan Petrov
# Category theory, computational complexity, and combinatorics connections?

(Asked by: username_0 on 2011-01-25)

I have been trying to read “[Pearls of Functional Algorithm design](http://rads.stackoverflow.com/amzn/click/0521513383)”, and subsequently “[The Algebra of Programming](http://rads.stackoverflow.com/amzn/click/013507245X)”, and there is an obvious correspondence between recursively (and polynomially) defined data types and combinatorial objects, having the same recursive definition and subsequently leading to the same formal power series (or generating functions), as shown in the introductions to combinatorial species (I read “[Species and Functors and Types, Oh My!](http://ozark.hendrix.edu/~yorgey/pub/species-pearl.pdf)”).

> So, for the first question, is there a way to recover the generating (recursive) equation from the power series? That’s an afterthought though.

I was more interested in the notion of initial algebras and final co-algebras as kind of “defining procedures about the data structure”. There are some practical rules in functional programming, concerning composition, products of mapping between algebras and similar, described for example [in this tutorial](http://www.comlab.ox.ac.uk/ralf.hinze/publications/IFL10.pdf). It seems to me that this could be quite powerful way to approach complexity and for example, it looks fairly straightforward to recover Master’s theorem in such context (I mean, you have to do the same argument, so not much gain in this instance), and the unique catamorphism from the initial algebra and the fact (am I mistaken?) that the algebras between A and FA for F-polynomial functor are isomorphic, makes it look to me that such approach could have a lot of benefits in analysing complexity of operations over data structures.

From practical standpoint, looks like fusion rules (basically, ways to compose algebra morphisms with one another, coalgebra morphisms, and general morphisms) are very powerful optimization technique for program transformation and refactoring. Am I right in thinking that full utilization of these rules can produce optimal program (no unnecessary intermediate data structures or other extra operations).

> Am I onto something (and what) here? Is it beneficiary (from learning standpoint) to try to look about computational complexity in this way? Are the structures, for which we can have "nice" initial algebras somehow too limited for some problems?

I’m mostly trying to find a way to think about complexity in terms of the structure of the search space and the way the "search space" and "search algorithm" interact through some "nice" object like the initial algebra of the functor and to understand if it's useful to try to view things this way, when looking at more complicated structures.

**Tags:** cc.complexity-theory, co.combinatorics, functional-programming, ct.category-theory
> **Comments:**
> **username_2**: can you reformat to make this readable?  
> **username_3**: There are two potential problems with your ideas. Firstly, not all data structures can be represented using initial algebras. Any general graph or complicated pointer structure will not be the initial algebra of any functor. Secondly, fusion rules and so forth will generally only improve the efficiency of the code, rather than change the O(-)-efficiency of the algorithm (though I do know of exceptions).  
> **username_0**: Thanks, Dave, I am trying to read the Algorithmic Game theory book, and the algorithms in traditional treatments are specified mostly operationally,so to speak,and was wondering if there is general way to approach them, and initial algebras etc looked nice for that,but lack of correspondence between general data structure and functors is a problem. @sclv: Thanks, I will look at it!  
> **username_1**: I want to point out that there are other ways to represent graphs than by complicated pointer structures. Particularly, one can represent them inductively, by a series of changes or additions @DaveClarke. I'm sure the same is true for other structures such as this, though I don't want to say so categorically as I'm not an expert on initial algebras and their limitations.  

---

## 2 answers

### Answer by username_5 on 2011-01-25. Score: 7 | Accepted answer

Dave Clarke's comment is quite important. Generally fusion doesn't change the O(-) efficiency. However, of particular interest is Liu, Cheng, and Hudak's work on Causal Commutative Arrows. Programs written with them are necessarily optimizable, in part through stream fusion, to a single loop free of dynamic memory allocation and intermediate structures: <http://haskell.cs.yale.edu/?post_type=publication&p=72>


---

### Answer by username_4 on 2014-10-02. Score: 6

Joyal's Combinatorial Species, Sedgwick/Falojet's "admissible constructions" of Analytic Combinatorics, and Yorgey's Haskell Species are all good.

[Power Series Power Serious](http://www.cs.dartmouth.edu/~doug/music.ps.gz) by McIlroy of UNIX diff fame is also a must read, as is the chapter on corecursion in The Haskell Road to Logic Maths and Programming.

The historical works by [Buchi](http://rads.stackoverflow.com/amzn/click/0387970649) edited by Saunders MacLane and [Chomsky/Schützenberger](http://www-igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1963-7ChomskyAlgebraic.pdf) make the connection between power series, algebras, trees, and finite state automata. The Transfer Matrix Method described in Stanley shows you how to compute generating functions from weighted automata.

I'm still working out the best way to translate between the domains (GF, weighted automata, algebra, tree, recursion) efficiently. Right now I'm shelling out to SymPy since there isn't a good Haskell symbolics package yet.

Personally, I've taken the iteration graph of an endofuction then calculated a min dominating set on it to get an exact black box search bound, <http://oeis.org/A186202> Not sure what types of complexity results you were searching for, but that technique is very powerful in examining any endofuction over a finite set.

--Original Oct 2 '14 at 15:37 answer--

Take a look at Brent Yorgey's thesis which follows the paper of his you cited. <http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf>


---

