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.
