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

17

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.

Stefan Petrov
la source
5
pouvez-vous reformater pour rendre cela lisible?
Lev Reyzin
11
Il y a deux problèmes potentiels avec vos idées. Premièrement, toutes les structures de données ne peuvent pas être représentées à l'aide d'algèbres initiales. Tout graphe général ou structure de pointeur compliquée ne sera l'algèbre initiale d'aucun foncteur. Deuxièmement, les règles de fusion et ainsi de suite n'amélioreront généralement que l'efficacité du code, plutôt que de modifier l'efficacité O (-) - de l'algorithme (bien que je connaisse des exceptions).
Dave Clarke
Merci, Dave, j'essaie de lire le livre de théorie des jeux algorithmiques, et les algorithmes dans les traitements traditionnels sont spécifiés principalement de manière opérationnelle, pour ainsi dire, et je me demandais s'il y avait un moyen général de les aborder, et les algèbres initiales, etc., avaient l'air bien pour cela , mais le manque de correspondance entre la structure générale des données et les foncteurs est un problème. @sclv: Merci, je vais le regarder!
Stefan Petrov le
Je tiens à souligner qu'il existe d'autres façons de représenter les graphiques que par des structures de pointeurs compliquées. En particulier, on peut les représenter de manière inductive, par une série de modifications ou d'ajouts @DaveClarke. Je suis sûr que la même chose est vraie pour d'autres structures comme celle-ci, même si je ne veux pas le dire catégoriquement car je ne suis pas un expert des algèbres initiales et de leurs limites.
Samuel Schlesinger

Réponses:

7

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

sclv
la source
6

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

Chad Brewbaker
la source