Я пытался прочитать « Жемчужины разработки функциональных алгоритмов », а затем « Алгебру программирования », и есть очевидное соответствие между рекурсивно (и полиномиально) определенными типами данных и комбинаторными объектами, имеющими то же самое рекурсивное определение и впоследствии ведущим к тому же формальному степенному ряду (или порождающим функциям), как показано во введении к комбинаторным видам (я читаю « Виды, функторы и типы, Боже мой! »).
Итак, для первого вопроса, есть ли способ восстановить порождающее (рекурсивное) уравнение из степенного ряда? Это запоздалая мысль все же.
Меня больше интересовало понятие начальных алгебр и конечных коалгебр как своего рода «определения процедур относительно структуры данных». В функциональном программировании есть несколько практических правил, касающихся композиции, продуктов отображения между алгебрами и аналогичных, описанных, например, в этом руководстве, Мне кажется, что это мог бы быть довольно мощный способ приблизиться к сложности, и, например, выглядит довольно просто восстановить теорему Мастера в таком контексте (я имею в виду, что вы должны использовать один и тот же аргумент, так что в этом случае не так уж и много), и уникальный катаморфизм исходной алгебры и тот факт (я ошибаюсь?), что алгебры между A и FA для F-полиномиального функтора изоморфны, заставляют меня думать, что такой подход может иметь много преимуществ в анализе сложности операции над структурами данных.
С практической точки зрения, правила слияния (в основном, способы составления морфизмов алгебры друг с другом, морфизмы коалгебры и общие морфизмы) являются очень мощным методом оптимизации для преобразования и рефакторинга программы. Прав ли я, полагая, что полное использование этих правил может привести к созданию оптимальной программы (без ненужных промежуточных структур данных или других дополнительных операций).
Я на что-то (и что) здесь? Является ли выгодным (с точки зрения обучения) попытаться взглянуть на вычислительную сложность таким образом? Являются ли структуры, для которых мы можем иметь «хорошие» начальные алгебры, слишком ограниченными для некоторых задач?
В основном я пытаюсь найти способ думать о сложности с точки зрения структуры пространства поиска и того, как «пространство поиска» и «алгоритм поиска» взаимодействуют через некоторый «красивый» объект, такой как начальная алгебра функтора и чтобы понять, полезно ли пытаться смотреть на вещи таким образом, рассматривая более сложные структуры.
Ответы:
Комментарий Дэйва Кларка довольно важен. Обычно слияние не меняет эффективность O (-). Тем не менее, особый интерес представляет работа Лю, Чэна и Гудака о Причинно-коммутативных стрелках. Программы, написанные с их помощью, обязательно оптимизируются, частично путем объединения потоков, в один цикл, свободный от динамического выделения памяти и промежуточных структур: http://haskell.cs.yale.edu/?post_type=publication&p=72
источник
Комбинаторные виды Джояла, «допустимые конструкции» аналитической комбинаторики Седжвика / Фалодже и виды Хаскелла Хорхе хороши.
Power Series Power Serious от Макилроя о разнице в славе UNIX также необходимо прочитать, как и главу о corecursion в Haskell Road to Logic Maths и Programming.
Исторические работы Бучи, отредактированные Сондерсом МакЛейном и Хомским / Шютценбергером, связывают степенные ряды, алгебры, деревья и конечные автоматы. Метод Матрицы Передачи, описанный в Stanley, показывает, как вычислить генерирующие функции из взвешенных автоматов.
Я все еще разрабатываю лучший способ эффективного перевода между доменами (GF, весовые автоматы, алгебра, дерево, рекурсия). Прямо сейчас я рассылаю SymPy, так как пока нет хорошего пакета символов Haskell.
Лично я взял итерационный график эндофункции, а затем рассчитал минимальное доминирующее множество на нем, чтобы получить точную границу поиска черного ящика, http://oeis.org/A186202 Не уверен, какие типы результатов поиска вы искали, но этот метод очень силен при исследовании любой эндофункции на конечном множестве.
- Первоначально 2 октября '14 в 15:37 ответ--
Взгляните на тезис Брента Йорги, который следует за статьей, которую вы цитировали. http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf
источник