Teoria kategorii, złożoność obliczeniowa i połączenia kombinatoryczne?

17

Próbowałem przeczytać „ Perły projektowania algorytmu funkcjonalnego ”, a następnie „ Algebra programowania ”, i istnieje oczywista zgodność między rekurencyjnie (i wielomianowo) zdefiniowanymi typami danych i obiektami kombinatorycznymi, mającymi tę samą definicję rekurencyjną, a następnie prowadzącą do tych samych formalnych szeregów mocy (lub funkcji generujących), jak pokazano we wstępach do gatunków kombinatorycznych (czytam „ Gatunki i funktory i typy, o mój! ”).

Czy w przypadku pierwszego pytania istnieje sposób na odzyskanie równania generującego (rekurencyjnego) z szeregu mocy? To jednak przemyślenie.

Bardziej interesowało mnie pojęcie początkowych algeb i końcowych koalgeb jako rodzaju „definiowania procedur dotyczących struktury danych”. Istnieje kilka praktycznych zasad programowania funkcjonalnego, dotyczących składu, produktów mapowania między algebrami i podobnych, opisanych na przykład w tym samouczku. Wydaje mi się, że może to być dość potężny sposób podejścia do złożoności i na przykład odzyskanie twierdzenia Mistrza w takim kontekście wydaje się dość proste (mam na myśli, że musisz zrobić ten sam argument, więc w tym przypadku nie ma większego zysku), a wyjątkowy katamorfizm z początkowej algebry oraz fakt (czy się mylę?), że algebry między A i FA dla F-wielomianowego funktora są izomorficzne, sprawiają, że wydaje mi się, że takie podejście może mieć wiele korzyści w analizowaniu złożoności operacje na strukturach danych.

Z praktycznego punktu widzenia, wygląda na to, że reguły syntezy (w zasadzie sposoby łączenia morfizmów algebry ze sobą, morfizmy węgielgebry i morfizmy ogólne) są bardzo potężną techniką optymalizacji transformacji programu i refaktoryzacji. Mam rację, myśląc, że pełne wykorzystanie tych reguł może zapewnić optymalny program (bez zbędnych pośrednich struktur danych lub innych dodatkowych operacji).

Czy mam coś (i co) tutaj? Czy z punktu widzenia uczenia się beneficjentem jest próba spojrzenia na złożoność obliczeniową w ten sposób? Czy struktury, dla których możemy mieć „ładne” algebry początkowe, są w jakiś sposób zbyt ograniczone, aby powodować pewne problemy?

Staram się głównie znaleźć sposób myślenia o złożoności pod względem struktury przestrzeni wyszukiwania oraz sposobu, w jaki „przestrzeń wyszukiwania” i „algorytm wyszukiwania” oddziałują przez jakiś „ładny” obiekt, taki jak początkowa algebra funktora i aby zrozumieć, czy warto patrzeć na to w ten sposób, patrząc na bardziej skomplikowane struktury.

Stefan Pietrow
źródło
5
czy możesz sformatować, aby było to czytelne?
Lev Reyzin
11
Istnieją dwa potencjalne problemy z Twoimi pomysłami. Po pierwsze, nie wszystkie struktury danych mogą być reprezentowane za pomocą początkowych algeb. Jakikolwiek ogólny wykres lub skomplikowana struktura wskaźnika nie będzie początkową algebrą żadnego funktora. Po drugie, reguły syntezy i tak dalej ogólnie poprawią jedynie wydajność kodu, zamiast zmieniać wydajność algorytmu O (-) (choć znam wyjątki).
Dave Clarke,
Dzięki, Dave, próbuję przeczytać książkę teorii gier algorytmicznych, a algorytmy w tradycyjnych metodach leczenia są określane głównie operacyjnie, że tak powiem, i zastanawiałem się, czy istnieje ogólny sposób na ich podejście, a początkowe algebry itp. Wyglądały ładnie , ale problemem jest brak zgodności między ogólną strukturą danych a funktorami. @sclv: Dzięki, popatrzę na to!
Stefan Pietrow
Chcę podkreślić, że istnieją inne sposoby reprezentowania wykresów niż skomplikowane struktury wskaźników. W szczególności można je przedstawić indukcyjnie, poprzez szereg zmian lub uzupełnień @DaveClarke. Jestem pewien, że to samo dotyczy innych struktur takich jak ta, choć nie chcę mówić tak kategorycznie, że nie jestem ekspertem od początkowych algeb i ich ograniczeń.
Samuel Schlesinger

Odpowiedzi:

7

Komentarz Dave'a Clarke'a jest dość ważny. Ogólnie fuzja nie zmienia wydajności O (-). Jednak szczególnie interesujące są prace Liu, Chenga i Hudaka nad przyczynowymi strzałkami przemiennymi. Programy napisane z nimi można koniecznie zoptymalizować, częściowo poprzez syntezę strumieniową, do pojedynczej pętli wolnej od dynamicznej alokacji pamięci i struktur pośrednich: http://haskell.cs.yale.edu/?post_type=publication&p=72

sclv
źródło
6

Kombinatoryjne gatunki Joyal, „dopuszczalne konstrukcje” analitycznej kombinatoryki Sedgwicka / Falojeta i gatunki Haskell Yorgeya są dobre.

Power Series Power Serious autorstwa McIlroya z UNIX-owej sławy jest również obowiązkową lekturą, podobnie jak rozdział o corecursion w The Haskell Road to Logic Maths and Programming.

Historyczne dzieła Buchi pod redakcją Saundersa MacLane'a i Chomsky'ego / Schützenbergera łączą serie mocy, algebry, drzewa i automaty stanów skończonych. Metoda Transfer Matrix opisana w Stanley pokazuje, jak obliczyć funkcje generujące z ważonych automatów.

Nadal pracuję nad skutecznym tłumaczeniem między domenami (GF, ważone automaty, algebra, drzewo, rekurencja). W tej chwili jestem zwolniony z SymPy, ponieważ nie ma jeszcze dobrego pakietu symboli Haskell.

Osobiście wziąłem wykres iteracji endofukcji, a następnie obliczyłem minimalny zestaw dominujący, aby uzyskać dokładne ograniczenie wyszukiwania w czarnej skrzynce, http://oeis.org/A186202 Nie jestem pewien, jakiego rodzaju wyników złożoności szukałeś , ale ta technika jest bardzo skuteczna w badaniu każdej endofukcji na skończonym zestawie.

- Oryginalna 2 października 14 o 15:37 odpowiedź--

Spójrz na tezę Brenta Yorgeya, która podąża za cytowaną przez niego pracą. http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf

Chad Brewbaker
źródło