Teoria das categorias, complexidade computacional e conexões combinatórias?

17

Eu tenho tentado ler “ Projeto Pérolas do algoritmo funcional ” e, posteriormente, “ A álgebra da programação ”, e há uma correspondência óbvia entre tipos de dados definidos recursivamente (e polinomialmente) e objetos combinatórios, com a mesma definição recursiva e, posteriormente, levando para a mesma série formal de poder (ou funções geradoras), como mostrado nas introduções a espécies combinatórias (eu li “ Espécies, Functors and Types, Oh My! ”).

Portanto, para a primeira pergunta, existe uma maneira de recuperar a equação geradora (recursiva) da série de potências? Isso é uma reflexão tardia.

Eu estava mais interessado na noção de álgebras iniciais e co-álgebras finais como um tipo de "definição de procedimentos sobre a estrutura de dados". Existem algumas regras práticas na programação funcional, relativas à composição, produtos de mapeamento entre álgebras e similares, descritas por exemplo neste tutorial. Parece-me que essa poderia ser uma maneira bastante poderosa de abordar a complexidade e, por exemplo, parece bastante simples recuperar o teorema do mestre em tal contexto (quero dizer, você precisa fazer o mesmo argumento, portanto, não há muito ganho neste caso), eo catamorfismo único da álgebra inicial e o fato (estou enganado?) de que as álgebras entre A e FA para o função polinomial F são isomórficas, parece-me que essa abordagem poderia ter muitos benefícios na análise da complexidade de operações sobre estruturas de dados.

Do ponto de vista prático, as regras de fusão (basicamente formas de compor morfismos de álgebra entre si, morfismos de coalgebra e morfismos gerais) são uma técnica de otimização muito poderosa para transformação e refatoração de programas. Estou certo ao pensar que a utilização completa dessas regras pode produzir um programa ideal (sem estruturas de dados intermediárias desnecessárias ou outras operações extras).

Estou em algo (e o que) aqui? É beneficiário (do ponto de vista da aprendizagem) tentar analisar a complexidade computacional dessa maneira? As estruturas, para as quais podemos ter álgebras iniciais "legais", são de alguma forma limitadas demais para alguns problemas?

Estou principalmente tentando encontrar uma maneira de pensar sobre a complexidade em termos da estrutura do espaço de pesquisa e a maneira como o "espaço de pesquisa" e o "algoritmo de pesquisa" interagem através de algum objeto "legal", como a álgebra inicial do functor e para entender se é útil tentar visualizar as coisas dessa maneira, ao olhar para estruturas mais complicadas.

cc.complexity-theory co.combinatorics functional-programming ct.category-theory Stefan Petrov
fonte
5
você pode reformatar para tornar isso legível?
Lev Reyzin
11
Existem dois problemas em potencial com suas idéias. Em primeiro lugar, nem todas as estruturas de dados podem ser representadas usando álgebras iniciais. Qualquer gráfico geral ou estrutura complicada de ponteiro não será a álgebra inicial de nenhum functor. Em segundo lugar, as regras de fusão e assim por diante geralmente geralmente melhoram a eficiência do código, em vez de alterar a eficiência O (-) - do algoritmo (embora eu conheça exceções).
Dave Clarke
Obrigado, Dave, estou tentando ler o livro de teoria dos jogos algorítmicos, e os algoritmos nos tratamentos tradicionais são especificados principalmente operacionalmente, por assim dizer, e fiquei imaginando se existe uma maneira geral de abordá-los, e as álgebras iniciais etc. pareciam agradáveis. , mas a falta de correspondência entre a estrutura geral de dados e os functores é um problema. @sclv: Obrigado, vou dar uma olhada!
Stefan Petrov
Quero salientar que existem outras maneiras de representar gráficos que não sejam estruturas complicadas de ponteiros. Particularmente, é possível representá-los indutivamente, por uma série de alterações ou adições ao @DaveClarke. Tenho certeza de que o mesmo vale para outras estruturas como essa, embora não queira dizer isso categoricamente, pois não sou especialista em álgebras iniciais e suas limitações.
Samuel Schlesinger

Respostas:

7

O comentário de Dave Clarke é bastante importante. Geralmente, a fusão não altera a eficiência de O (-). No entanto, é de particular interesse o trabalho de Liu, Cheng e Hudak sobre Flechas Comutativas Causais. Os programas gravados com eles são necessariamente otimizáveis, em parte por meio da fusão de fluxo, para um único loop livre de alocação dinâmica de memória e estruturas intermediárias: http://haskell.cs.yale.edu/?post_type=publication&p=72

sclv
fonte
6

As espécies combinatórias de Joyal, as "construções admissíveis" de Analytic Combinatorics de Sedgwick / Falojet e as espécies de Haskell de Yorgey são boas.

Power Series O Power Serious de McIlroy, da UNIX diff fame, também é uma leitura obrigatória, assim como o capítulo sobre corecursão em The Haskell Road to Logic Maths and Programming.

As obras históricas de Buchi editadas por Saunders MacLane e Chomsky / Schützenberger fazem a conexão entre séries de potência, álgebras, árvores e autômatos de estados finitos. O Método da matriz de transferência descrito em Stanley mostra como calcular funções geradoras a partir de autômatos ponderados.

Ainda estou trabalhando na melhor maneira de traduzir entre os domínios (GF, autômatos ponderados, álgebra, árvore, recursão) de forma eficiente. No momento, estou usando o SymPy, já que ainda não há um bom pacote simbólico de Haskell.

Pessoalmente, peguei o gráfico de iteração de uma produção final e calculei um conjunto dominante mínimo para obter uma ligação exata à caixa preta, http://oeis.org/A186202 Não tenho certeza de que tipos de resultados de complexidade você estava procurando, mas essa técnica é muito poderosa para examinar qualquer ação final em um conjunto finito.

O que você precisa saber é o seguinte:

Dê uma olhada na tese de Brent Yorgey, que segue o artigo que você citou. http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf

Chad Brewbaker
fonte