Изоморфизмы структуры данных

20

Отказ от ответственности: я не теоретик CS.

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

Есть ли более ограничительное (но более полезное) определение? (Или, если нет, почему?) Существует ли каноническое определение категории «построенных структур данных»?

скоро
источник

Ответы:

16

Канонической такой категории не существует, по той же причине нет канонической категории вычислений. Тем не менее, существуют большие и полезные алгебраические структуры на структурах данных.

Одной из наиболее общих таких структур, которая все же полезна, является теория комбинаторных видов. Вид - это функтор , где B - категория конечных множеств и биекций между ними. Вы можете думать о видах как о семействах структур, проиндексированных абстрактными наборами местоположений. Это объясняет функториальность над B - такие семейства должны быть инвариантны относительно переименования абстрактных меток. Затем исчисление видов в основном воспроизводит генерирующие функциональные методы на уровне функций, чтобы генерировать наборы структур данных вместо счетчиков.F:ВВВВ

Чтобы увидеть, как эта теория реализована на языке программирования, вы можете прочитать статью Симпозиума Брента Йорджи на Хаскелле, Виды, функторы и типы, о боже! , Я думаю, у Sage также есть пакет видов, хотя, конечно, он ориентирован на компьютерную алгебру, а не на программирование.

Нил Кришнасвами
источник
14

На самом деле, существует другое понятие, чем изоморфизм, который более полезен в программировании. Это называется «поведенческой эквивалентностью» (иногда называемой «наблюдательной эквивалентностью») и устанавливается путем предоставления «имитационного отношения» между структурами данных, а не биекциями. Вошли алгебраисты и основали область, называемую «алгебраические типы данных» в области компьютерных наук, где они на некоторое время выдвинули изоморфизмы и начальные алгебры. В конце концов, ученые-компьютерщики поняли, что их вводят в заблуждение. Хорошая статья, в которой говорится об этих вопросах, - «Об эквивалентности наблюдений и алгебраической спецификации» Саннеллы и Тарлецки.

Я написал ответ на другой вопрос в теории логических отношений и симуляций, который говорит о более общей истории отношений симуляции в информатике. Вы можете прочитать это и следить за ссылками, приведенными там. Глава 5 «Ремесла программирования» Рейнольдса особенно поучительна.

В учебнике Холкомба по теории алгебраических автоматов есть интересная цитата (стр. 42):

Есть много других результатов, связанных с гомоморфизмами и частными ... Хотя они представляют самостоятельный алгебраический интерес, они еще не оказались особенно полезными при изучении автоматов и смежных областей. Фактически, алгебраическая теория машин расходится с направлением, взятым в других алгебраических теориях, в одном важном аспекте ... Однако акцент в теории автоматов сделан не на том, «как» машины выглядят, а на том, «что они могут делать». , Мы будем рассматривать две машины как очень близкие, если они могут «делать одно и то же», однако они могут быть алгебраически не изоморфными!

Удай Редди
источник
Размышляя над цитатой Холкомба, я заметил, что он в основном говорит, что традиционная алгебра имеет дело с тем, как «выглядят» вещи, то есть с их структурой, но они не имеют никакого отношения к тому, что «они могут сделать», то есть к их поведению. Это, кажется, указывает на фундаментальное ограничение традиционной алгебры в отношении информатики. К сожалению, я думаю, что теория категорий также принадлежит к тому же лагерю. Но теория категорий имеет статус «святой коровы», и говорить о ее ограничениях считается некруто. Надеемся, что ученые-компьютерщики наберутся смелости, чтобы сказать это громче.
Uday Reddy
Uday, не могли бы вы рассказать подробнее о том, как (асимметрия?) Теории категорий кажется не очень подходящей?
Лукаш Лью
@ ŁukaszLew, Если бы теория категорий подходила, вы могли бы сказать, что все типизированные выражения типа лямбда-исчисления с переменной типа X являются функторами. Но они не являются, например, F (X) = (X -> X) не является функтором.
Удай Редди
7

Вместо того, чтобы спрашивать, как мы можем усилить / ослабить понятие изоморфизма, можно задать другой вопрос: каково правильное понятие эквивалентности между вычислительными структурами и какова математическая структура, лежащая в основе этого понятия.

Одно большое семейство структур - коалгебры. Структуры, такие как списки, деревья, автоматы, как конечного, так и бесконечного многообразия, могут быть описаны как коалгебры. Затем мы можем изучить гомоморфизм или изоморфизм между коалгебрами.

Однако даже гомоморфизмы между коалгебрами не рассказывают всей истории. Возможно, вам будет полезно посмотреть симуляции, бисимуляции и другие логические отношения. Если вы строго предпочитаете алгебраический подход (в отличие от реляционного), то галуа-связями являются одним из вариантов. Вот некоторые отправные точки.

Виджай Д
источник
2

Отказ от ответственности: я не уверен, что понял ваш вопрос. Вы хотите поговорить об изоморфизме между двумя структурами данных или между двумя «спецификациями структуры данных»? (Их иногда называют абстрактными типами данных.)

Если вы рассматриваете модель клеточного зонда, то я думаю, что концепция изоморфизма легко возникает. Это связано с тем, что модель клеточного зонда моделирует вычисления с помощью дерева решений, поэтому изоморфизм легко определить. Я думаю, что модель клеточного зонда может помочь, если вы учитываете изоморфизм между реализациями структуры данных, и если вы рассматриваете спецификации структуры данных.

Для получения информации о модели клеточного зонда, см., Например, опрос Милтерсена. ( Сложность сотового зонда: обзор )

Если вы скажете больше о том, почему вам нужно определить изоморфизм между структурами данных, возможно, будет возможно предоставить больше помощи. Не стесняйтесь сообщать мне.

Elad
источник