Алгебраический тип данных

Алгебраический тип данных

Алгебраи́ческий тип да́нных — в теории программирования любой тип, значения которого являются значениями некоторых иных типов, «обёрнутыми» конструкторами алгебраического типа. Другими словами, алгебраический тип данных имеет набор конструкторов типа, каждый из которых принимает на вход значения определённых типов и возвращает значение конструируемого типа. Важное отличие конструктора типа от функции заключается в том, что конструктор не исполняется, но единственная его задача — создание значения своего типа на основе входных значений. Для работы с такими значениями используется механизм сопоставления с образцами, как наиболее эффективный способ разбора значений (но это не означает, что иные механизмы работы с значениями не применимы к алгебраическим типам данных).

Самым простым алгебраическим типом данных является список. Действительно, список имеет два конструктора — конструктор пустого списка и конструктор пары, первым элементом которой является значение определённого типа, а вторым — список. Пример определения списка на языке Haskell:

 data List a = Nil 
             | Cons a (List a)

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

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

 data Bool = False | True

Также алгебраический тип данных может быть абстрактным, если такой тип определён в некотором модуле, из которого не экспортируются конструкторы соответствующего типа, а доступ к значениям внутри алгебраического типа данных осуществляется при помощи специальных методов — селекторов. Особо стоит отметить так называемые «обобщённые алгебраические типы данных», которые реализованы в языках Haskell и ML.

Остаётся отметить, что с точки зрения синтаксически-ориентированного конструирования данных алгебраическим типом данных является размеченное объединение декартовых произведений типов. Каждое слагаемое в размеченном объединении соответствует одному конструктору, а каждый конструктор в свою очередь определяет декартово произведение типов, соответствующих параметрам конструктора. Конструкторы без параметров являются пустыми произведениями. Если алгебраический тип данных является рекурсивным, всё размеченное объединение обёртывается рекурсивным типом, и каждый конструктор типа возвращает рекурсивный тип.

Содержание

Реализация

Язык Haskell

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

Язык Nemerle

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

См. также


Wikimedia Foundation. 2010.

Смотреть что такое "Алгебраический тип данных" в других словарях:

  • Обобщённый алгебраический тип данных — один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности в языках ML и Haskell, причём в… …   Википедия

  • Обобщенный алгебраический тип данных — Обобщённый алгебраический тип данных один из видов алгебраических типов данных, который характеризуется тем, что его конструкторы могут возвращать значения не своего типа. Это понятие реализовано в нескольких языках программирования, в частности… …   Википедия

  • Тип данных — (встречается также термин вид данных)  фундаментальное понятие теории программирования. Тип данных определяет множество значений, набор операций, которые можно применять к таким значениям и, возможно, способ реализации хранения значений и… …   Википедия

  • Абстрактный тип данных — Для улучшения этой статьи по информационным технологиям желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставив сноски, внести более точные у …   Википедия

  • Целое (тип данных) — Целое, целочисленный тип данных (англ. Integer), в информатике  один из простейших и самых распространённых типов данных в языках программирования. Служит для представления целых чисел. Множество чисел этого типа представляет собой… …   Википедия

  • Множество (тип данных) — У этого термина существуют и другие значения, см. Множество (значения). Множество тип и структура данных в информатике, является реализацией математического объекта множество. Данные типа множество позволяют хранить ограниченное число значений… …   Википедия

  • Комплексный тип данных — Некоторые языки программирования предоставляют специальный тип данных для комплексных чисел. Наличие встроенного типа упрощает хранение комплексных величин и вычисления над ними. Содержание 1 Арифметика над комплексными 2 Поддержка в языках …   Википедия

  • Указатель (тип данных) — У этого термина существуют и другие значения, см. Указатель. Диаграмма указателей Указатель (пойнтер, англ. pointer)  переменная, диапазон значений которой состоит из адресов ячеек памяти и специального значения  нулевого адреса.… …   Википедия

  • Типизация данных — Тип данных  фундаментальное понятие теории программирования. Тип данных определяет множество значений, набор операций, которые можно применять к таким значениям, и, возможно, способ реализации хранения значений и выполнения операций. Любые… …   Википедия

  • Типы данных — В этой статье перечисляются типы данных, о самом понятии см тип данных В различных операционных системах, языках программирования, спецификациях форматов данных фигурируют различные символические обозначения для типов данных. Часть из них… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.