Существуют ли алгебраические типы данных помимо суммы и произведения?

По большинству определений общие или базовые типы алгебраических данных в Haskell или Scala - это сумма и произведение. Примеры: 1, 2.

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

Однако определения оставляют впечатление, что возможны и другие типы алгебраических данных, а сумма и произведение являются наиболее полезными для описания выбора или комбинации элементов.

Учитывая, что в базовой алгебре есть операции вычитания, деления и возведения в степень целого числа - правильно ли, что в программировании возможна реализация других альтернативных алгебраических типов, но они бесполезны?

Реализованы ли в каких-либо языках программирования алгебраические типы данных, не являющиеся типами сумм и продуктов?


types scala haskell algebraic-data-types
person Evgeny    schedule 28.12.2019    source источник
comment
Возведение в степень также представлено в ADT через типы функций A -> B. (PS Я подхожу к этому вопросу, имея опыт работы с Haskell. Я вообще не знаю Scala.)   -  person Robin Zigmond    schedule 28.12.2019
comment
Отвечает ли это на ваш вопрос? Что такое алгебраический тип данных (ADT)?   -  person Suma    schedule 29.12.2019
comment
@Suma - спасибо за ссылку, там есть похожий, но более широкий вопрос. Приведенные здесь ответы относятся к алгебраическим типам, отличным от суммы / произведения, и их реализации. Также для сокращения, ADT обычно зарезервирован для абстрактных типов данных wiki.haskell.org/Abstract_data_type, а не алгебраических. типы данных.   -  person Evgeny    schedule 29.12.2019

Ответы (2)


arrow_upward
14
arrow_downward

«Алгебраика» пришла из теории категорий. Каждый алгебраический тип данных представляет собой исходную алгебру функтора. Таким образом, вы могли бы в принципе назвать все, что происходит от функтора таким образом, алгебраическим, и я думаю, что это довольно большой класс.

Интерпретация «алгебраический» как «школьная алгебра» (я не хочу быть снисходительным, это просто как мы его называем), как и у вас, есть несколько хороших аналогий.

  • Произвольные степени, а не только целые степени, очень похожи на типы функций, то есть A -> B аналогична BA. В теории категорий, когда вы рассматриваете функцию («морфизм») как объект категории, она называется экспоненциальным объектом, и используется последняя запись. Ради интереса посмотрим, сможете ли вы доказать закон CA+B = CA × CB, написав взаимно однозначное соответствие между соответствующими типами.
  • Деление аналогично факторным типам - увлекательной области исследований, которая затрагивает такие горячие и модные вещи, как теория гомотопических типов. Аналогия частных с делением не так сильна, как типы продуктов с умножением, поскольку деление приходится на отношение эквивалентности.
  • С такой скоростью можно было бы ожидать, что с вычитанием будет какая-то красивая аналогия, но, увы, я ничего не знаю. Дэн Пипони немного исследовал это через антидиагональ, но это далеко не общая аналогия.
person luqui    schedule 28.12.2019
comment
Я полагаю, что (A + B)^C = A^C × B^C неверно. Вы имеете в виду (A × B)^C = A^C × B^C? - person Dmytro Mitin; 28.12.2019
comment
@DmytroMitin, ой, перепуталась. Починил это. - person luqui; 28.12.2019

arrow_upward
3
arrow_downward

Обычный ответ - это @luqui, и мне нечего добавить к этому. Обратной стороной является то, что, хотя вы различаете альтернативы суммы по тегу («конструктор» в Haskell), вы должны обращаться к компонентам продукта по позиции. Для однородных компонентов, как в векторе / массиве, это нормально; но для типичных структур данных (типов записей) вы хотите получить доступ по «метке поля» и абстрагироваться от позиции. Система звукозаписи / лейбла Haskell: а) с этим справляется очень плохо; и б) настолько глубоко укоренился в языке, что его практически невозможно улучшить - смотрите бесконечные предложения и бесконечные обсуждения, которые пока не привели к никаким изменениям.

Тогда нетрадиционный ответ - индексированные семейства, также известные как «индексированные наборы». Идея была разработана в основном вокруг «теоретико-множественных структур данных» DLChild, например, этой < / а>. Подход Чайлдса был упомянут в основополагающей статье о реляционной модели (базы данных) Кодд 1970 < / а>.

Важнейшей особенностью является то, что вы можете использовать любой тип для индексации коллекции компонентов; компоненты неоднородны; а компилятор поддерживает типобезопасный доступ (чтение и обновление) как по компонентам, так и по всей структуре. Компоненты вполне могут быть организованы позиционно внутри структуры, но эта деталь реализации скрыта от программиста. (Система записи Haskell здесь не работает.)

Реализованы ли в каких-либо языках программирования алгебраические типы данных, не являющиеся типами сумм и продуктов?

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

Было предложено / разработано несколько расширяемых / анонимных систем записи на Haskell (особенно HList) или языках, подобных Haskell (например, Ur / web), или даже TRex. (См. person AntC    schedule 28.12.2019