Théorie des catégories, complexité informatique et connexions combinatoires?

J'ai essayé de lire « Perles de conception d'algorithmes fonctionnels », puis « L'algèbre de programmation », et il existe une correspondance évidente entre les types de données définis de manière récursive (et polynomiale) et les objets combinatoires, ayant la même définition récursive et menant par la suite à la même série de puissance formelle (ou fonctions génératrices), comme indiqué dans les introductions aux espèces combinatoires (j'ai lu " Espèces et foncteurs et types, Oh My! ").

Donc, pour la première question, existe-t-il un moyen de récupérer l'équation génératrice (récursive) de la série de puissances? C'est une réflexion après coup.

J'étais plus intéressé par la notion d'algèbres initiales et de co-algèbres finales comme une sorte de «procédures de définition de la structure des données». Il existe quelques règles pratiques en programmation fonctionnelle, concernant la composition, les produits de mappage entre algèbres et similaires, décrites par exemple dans ce tutoriel. Il me semble que cela pourrait être un moyen assez puissant d'approcher la complexité et par exemple, il semble assez simple de récupérer le théorème du Maître dans un tel contexte (je veux dire, vous devez faire le même argument, donc pas beaucoup de gain dans ce cas), et le catamorphisme unique de l'algèbre initiale et le fait (je me trompe?) que les algèbres entre A et FA pour le foncteur polynomial F sont isomorphes, me fait penser qu'une telle approche pourrait avoir beaucoup d'avantages dans l'analyse de la complexité de opérations sur les structures de données.

D'un point de vue pratique, les règles de fusion (essentiellement, les moyens de composer les morphismes d'algèbre les uns avec les autres, les morphismes de houille et les morphismes généraux) sont des techniques d'optimisation très puissantes pour la transformation de programme et la refactorisation. Ai-je raison de penser que la pleine utilisation de ces règles peut produire un programme optimal (pas de structures de données intermédiaires inutiles ou d'autres opérations supplémentaires).

Suis-je sur quelque chose (et quoi) ici? Est-il avantageux (du point de vue de l'apprentissage) d'essayer de voir la complexité informatique de cette manière? Les structures, pour lesquelles nous pouvons avoir de "belles" algèbres initiales sont en quelque sorte trop limitées pour certains problèmes?

J'essaie principalement de trouver un moyen de penser la complexité en termes de structure de l'espace de recherche et de la façon dont "l'espace de recherche" et "l'algorithme de recherche" interagissent à travers un objet "agréable" comme l'algèbre initiale du foncteur et pour comprendre s'il est utile d'essayer de voir les choses de cette façon, quand on regarde des structures plus compliquées.

Le commentaire de Dave Clarke est assez important. En général, la fusion ne modifie pas l'efficacité O (-). Cependant, les travaux de Liu, Cheng et Hudak sur les flèches commutatives causales sont particulièrement intéressants. Les programmes écrits avec eux sont nécessairement optimisables, en partie grâce à la fusion de flux, en une seule boucle sans allocation dynamique de mémoire et structures intermédiaires: http://haskell.cs.yale.edu/?post_type=publication&p=72

Les espèces combinatoires de Joyal, les "constructions admissibles" de combinatoire analytique de Sedgwick / Falojet et les espèces Haskell de Yorgey sont toutes bonnes.

Power Series Power Serious de McIlroy de UNIX diff fame est également une lecture incontournable, tout comme le chapitre sur la corecursion dans The Haskell Road to Logic Maths and Programming.

Les travaux historiques de Buchi édités par Saunders MacLane et Chomsky / Schützenberger font le lien entre les séries de puissance, les algèbres, les arbres et les automates à états finis. La méthode de matrice de transfert décrite dans Stanley vous montre comment calculer les fonctions de génération à partir d'automates pondérés.

Je travaille toujours sur la meilleure façon de traduire efficacement entre les domaines (GF, automates pondérés, algèbre, arbre, récursivité). En ce moment, je lance à SymPy car il n'y a pas encore de bon package symbolique Haskell.

Personnellement, j'ai pris le graphique d'itération d'une endofuction puis calculé un ensemble dominant minimum pour obtenir une limite de recherche exacte dans la boîte noire, http://oeis.org/A186202 Je ne sais pas quels types de résultats de complexité vous cherchiez, mais cette technique est très puissante pour examiner toute endofuction sur un ensemble fini.

--Original 2 octobre 14 à 15:37 réponse--

Jetez un oeil à la thèse de Brent Yorgey qui suit le document que vous avez cité. http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf