# Category theory, computational complexity, and combinatorics connections?

I have been trying to read “Pearls of Functional Algorithm design”, and subsequently “The Algebra of Programming”, 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!”).

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. 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.

• can you reformat to make this readable? Commented Jan 25, 2011 at 5:45
• 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). Commented Jan 25, 2011 at 9:24
• 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! Commented Jan 26, 2011 at 8:46
• 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. Commented Mar 16, 2017 at 0:33

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

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

Power Series Power Serious 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 edited by Saunders MacLane and Chomsky/Schützenberger 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