¿Teoría de categorías, complejidad computacional y conexiones combinatorias?

17

He estado tratando de leer " Diseño de Algoritmo Funcional de Perlas " y, posteriormente, " El Álgebra de la Programación ", y existe una correspondencia obvia entre los tipos de datos definidos recursivamente (y polinomialmente) y los objetos combinatorios, que tienen la misma definición recursiva y posteriormente conducen a la misma serie de poder formal (o funciones generadoras), como se muestra en las introducciones a las especies combinatorias (leí " Especies y Functores y Tipos, ¡Dios mío! ").

Entonces, para la primera pregunta, ¿hay alguna manera de recuperar la ecuación generadora (recursiva) de la serie de potencia? Sin embargo, es una idea de último momento.

Estaba más interesado en la noción de álgebras iniciales y co-álgebras finales como una especie de "procedimientos definitorios sobre la estructura de datos". Existen algunas reglas prácticas en la programación funcional, relativas a la composición, productos de mapeo entre álgebras y similares, descritas por ejemplo en este tutorial.. Me parece que esta podría ser una forma bastante poderosa de abordar la complejidad y, por ejemplo, parece bastante sencillo recuperar el teorema de la Maestra en ese contexto (quiero decir, tienes que hacer el mismo argumento, por lo que no hay mucha ganancia en este caso), y el catamorfismo único del álgebra inicial y el hecho (¿me equivoco?) de que las álgebras entre A y FA para el functor polinomial F son isomórficas, me parece que tal enfoque podría tener muchos beneficios en el análisis de la complejidad de operaciones sobre estructuras de datos.

Desde el punto de vista práctico, parece que las reglas de fusión (básicamente, formas de componer morfismos de álgebra entre sí, morfismos de coalgebra y morfismos generales) son una técnica de optimización muy poderosa para la transformación y refactorización de programas. Estoy en lo cierto al pensar que la plena utilización de estas reglas puede producir un programa óptimo (sin estructuras de datos intermedias innecesarias u otras operaciones adicionales).

¿Estoy en algo (y qué) aquí? ¿Es beneficiario (desde el punto de vista del aprendizaje) tratar de ver la complejidad computacional de esta manera? ¿Son las estructuras, para las cuales podemos tener álgebras iniciales "agradables", de alguna manera demasiado limitadas para algunos problemas?

Principalmente estoy tratando de encontrar una manera de pensar sobre la complejidad en términos de la estructura del espacio de búsqueda y la forma en que el "espacio de búsqueda" y el "algoritmo de búsqueda" interactúan a través de algún objeto "agradable" como el álgebra inicial del functor y para entender si es útil tratar de ver las cosas de esta manera, al mirar estructuras más complicadas.

cc.complexity-theory co.combinatorics functional-programming ct.category-theory Stefan Petrov
fuente
55
¿Puedes reformatear para que esto sea legible?
Lev Reyzin
11
Hay dos problemas potenciales con tus ideas. En primer lugar, no todas las estructuras de datos se pueden representar utilizando álgebras iniciales. Cualquier gráfico general o estructura de puntero complicada no será el álgebra inicial de ningún functor. En segundo lugar, las reglas de fusión, etc., generalmente solo mejorarán la eficiencia del código, en lugar de cambiar la eficiencia O (-) del algoritmo (aunque sí sé de excepciones).
Dave Clarke el
Gracias, Dave, estoy tratando de leer el libro de teoría del juego algorítmico, y los algoritmos en los tratamientos tradicionales se especifican principalmente de manera operativa, por así decirlo, y me preguntaba si hay una forma general de abordarlos, y las álgebras iniciales, etc., se veían bien para eso. , pero la falta de correspondencia entre la estructura general de datos y los functores es un problema. @sclv: ¡Gracias, lo miraré!
Stefan Petrov
Quiero señalar que hay otras formas de representar gráficos que mediante estructuras de puntero complicadas. Particularmente, uno puede representarlos inductivamente, mediante una serie de cambios o adiciones @DaveClarke. Estoy seguro de que lo mismo es cierto para otras estructuras como esta, aunque no quiero decirlo categóricamente, ya que no soy un experto en álgebras iniciales y sus limitaciones.
Samuel Schlesinger

Respuestas:

7

El comentario de Dave Clarke es bastante importante. En general, la fusión no cambia la eficiencia O (-). Sin embargo, de particular interés es el trabajo de Liu, Cheng y Hudak sobre flechas causales conmutativas. Los programas escritos con ellos son necesariamente optimizables, en parte a través de la fusión de flujo, a un solo bucle libre de asignación dinámica de memoria y estructuras intermedias: http://haskell.cs.yale.edu/?post_type=publication&p=72

sclv
fuente
6

Las especies combinatorias de Joyal, las "construcciones admisibles" de Sedgwick / Falojet de Combinatoria analítica y las especies Haskell de Yorgey son todas buenas.

Power Series Power Serious de McIlroy de UNIX diff fame también es una lectura obligada, como lo es el capítulo sobre corecursion en The Haskell Road to Logic Maths and Programming.

Las obras históricas de Buchi editadas por Saunders MacLane y Chomsky / Schützenberger hacen la conexión entre series de energía, álgebras, árboles y autómatas de estados finitos. El Método de matriz de transferencia descrito en Stanley le muestra cómo calcular funciones generadoras a partir de autómatas ponderados.

Todavía estoy trabajando en la mejor manera de traducir entre los dominios (GF, autómatas ponderados, álgebra, árbol, recursión) de manera eficiente. En este momento estoy enviando a SymPy ya que todavía no hay un buen paquete de símbolos de Haskell.

Personalmente, tomé el gráfico de iteración de una endofucción y luego calculé un conjunto dominante mínimo para obtener un límite de búsqueda de recuadro negro exacto, http://oeis.org/A186202 No estoy seguro de qué tipo de resultados de complejidad estaba buscando, pero esa técnica es muy poderosa para examinar cualquier endofucción en un conjunto finito.

- Respuesta original del 2 de octubre de 2014 a las 15:37

Eche un vistazo a la tesis de Brent Yorgey que sigue el artículo de su cita. http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf

Chad Brewbaker
fuente