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.