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.
źródło
Odpowiedzi:
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
źródło
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
źródło