Теория категорий, вычислительная сложность и комбинаторика связей?

17

Я пытался прочитать « Жемчужины разработки функциональных алгоритмов », а затем « Алгебру программирования », и есть очевидное соответствие между рекурсивно (и полиномиально) определенными типами данных и комбинаторными объектами, имеющими то же самое рекурсивное определение и впоследствии ведущим к тому же формальному степенному ряду (или порождающим функциям), как показано во введении к комбинаторным видам (я читаю « Виды, функторы и типы, Боже мой! »).

Итак, для первого вопроса, есть ли способ восстановить порождающее (рекурсивное) уравнение из степенного ряда? Это запоздалая мысль все же.

Меня больше интересовало понятие начальных алгебр и конечных коалгебр как своего рода «определения процедур относительно структуры данных». В функциональном программировании есть несколько практических правил, касающихся композиции, продуктов отображения между алгебрами и аналогичных, описанных, например, в этом руководстве, Мне кажется, что это мог бы быть довольно мощный способ приблизиться к сложности, и, например, выглядит довольно просто восстановить теорему Мастера в таком контексте (я имею в виду, что вы должны использовать один и тот же аргумент, так что в этом случае не так уж и много), и уникальный катаморфизм исходной алгебры и тот факт (я ошибаюсь?), что алгебры между A и FA для F-полиномиального функтора изоморфны, заставляют меня думать, что такой подход может иметь много преимуществ в анализе сложности операции над структурами данных.

С практической точки зрения, правила слияния (в основном, способы составления морфизмов алгебры друг с другом, морфизмы коалгебры и общие морфизмы) являются очень мощным методом оптимизации для преобразования и рефакторинга программы. Прав ли я, полагая, что полное использование этих правил может привести к созданию оптимальной программы (без ненужных промежуточных структур данных или других дополнительных операций).

Я на что-то (и что) здесь? Является ли выгодным (с точки зрения обучения) попытаться взглянуть на вычислительную сложность таким образом? Являются ли структуры, для которых мы можем иметь «хорошие» начальные алгебры, слишком ограниченными для некоторых задач?

В основном я пытаюсь найти способ думать о сложности с точки зрения структуры пространства поиска и того, как «пространство поиска» и «алгоритм поиска» взаимодействуют через некоторый «красивый» объект, такой как начальная алгебра функтора и чтобы понять, полезно ли пытаться смотреть на вещи таким образом, рассматривая более сложные структуры.

Стефан Петров
источник
5
Вы можете переформатировать, чтобы сделать это читабельным?
Лев Рейзин
11
Есть две потенциальные проблемы с вашими идеями. Во-первых, не все структуры данных могут быть представлены с использованием начальных алгебр. Любой общий граф или сложная структура указателей не будет исходной алгеброй любого функтора. Во-вторых, правила слияния и т. Д., Как правило, только улучшают эффективность кода, а не изменяют эффективность алгоритма (хотя я знаю об исключениях).
Дейв Кларк
Спасибо, Дэйв, я пытаюсь прочитать книгу «Алгоритмическая теория игр», и алгоритмы в традиционных методах лечения, так сказать, определены в основном оперативно, и мне было интересно, есть ли общий подход к ним, и начальные алгебры и т. Д. Выглядели хорошими для этого , но несоответствие между общей структурой данных и функторами является проблемой. @sclv: Спасибо, я посмотрю на это!
Стефан Петров
Я хочу отметить, что существуют и другие способы представления графиков, кроме сложных структур указателей. В частности, их можно представить индуктивно, путем серии изменений или дополнений @DaveClarke. Я уверен, что то же самое верно для других структур, таких как эта, хотя я не хочу говорить так категорично, поскольку я не эксперт по начальным алгебрам и их ограничениям.
Сэмюэль Шлезингер

Ответы:

7

Комментарий Дэйва Кларка довольно важен. Обычно слияние не меняет эффективность O (-). Тем не менее, особый интерес представляет работа Лю, Чэна и Гудака о Причинно-коммутативных стрелках. Программы, написанные с их помощью, обязательно оптимизируются, частично путем объединения потоков, в один цикл, свободный от динамического выделения памяти и промежуточных структур: http://haskell.cs.yale.edu/?post_type=publication&p=72

sclv
источник
6

Комбинаторные виды Джояла, «допустимые конструкции» аналитической комбинаторики Седжвика / Фалодже и виды Хаскелла Хорхе хороши.

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

Чад Brewbaker
источник