Главная » Haskell » Кратко об алгебраических типах данных

0

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

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

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

«единичными» элементами алгебраических типов данных.

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

такой тип определён в некотором модуле, из которого  не  экспортируются конструкторы соответствующего типа, а доступ к значениям внутри алгебраического типа данных осуществляется при помощи специальных  методов — селекторов. Абстракция данных подробно описана в главе 4..

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

Все алгебраические типы данных в языке Haskell определяются при помощи ключевого слова data, независимо от назначения типа.

2.2.1.    Перечисления

Перечисления — это специальный вид алгебраических типов данных, который характеризуется тем, что любой его конструктор не принимает на вход ни одного аргумента. Это позволяет в рамках  языка Haskell кодировать  то, чем исходно являются перечисления, а именно ограниченным набором именованных констант, которые используются для улучшения внешнего вида исходных кодов, так как использование мнемонических имён для некоторых значений всегда лучше, чем использование для тех же целей числовых или иных констант.

Соответственно, обычный способ определения  перечислений  выглядит просто — необходимо  перечислить  конструкторы типа,  разделив их вертикальной чертой (|).  Например, так определяется  булевский тип в стандартном модуле Prelude (детально рассматривается на стр. 108):

data  Bool  =  False    -Ложь

| True     -Истина

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

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

Вот несколько примеров определений перечислений в языке Haskell.

-Определение  типа для представления шахматных  фигур.

data  ChessFigure

= King      -Король

| Queen  -Ферзь

| Rook    -Ладья

| Bishop  -Слон

| Knight   -Конь

| Pawn    -Пешка

-Определение  типа для представления планет Солнечной  системы.

data  Planet

= Mercury    -Меркурий

| Venus      -Венера

| Earth        -Земля

| Mars         -Марс

| Jupiter -Юпитер

| Saturn      -Сатурн

| Uranus     -Уран

| Neptune   -Нептун

| Pluto    -Плутон

Использование таких  типов ничем не отличается от использования  любых прочих типов данных в языке Haskell. В первую очередь все конструкторы перечислений могут использоваться в сопоставлении с образцами. Без создания дополнительных  определений использование перечислений ограничено этим механизмом. Значения перечислений невозможно сравнивать друг с другом, их нельзя вывести на экран, над ними невозможно проводить какие-либо операции. Для того чтобы более полноценно использовать перечисления в программах, необходимо для  соответствующего  перечисления определить экземпляр некоторого  класса. Этот вопрос будет самым тщательным образом раскрыт в главе 3..

Уже  упомянутое перечисление  Bool  используется для  представления булевских значений в программах. Однако это  перечисление  достаточно сильно связано с трансляторами языка,  так  как оно используется в конструкции if-then-else, а эта конструкция выполнена в языке Haskell не в виде функции, а внедрена в  глубины транслятора. Поэтому перечисление Bool стоит немного отдельно от других перечислений, которые определяются программистом.

Другой особенностью перечислений в языке Haskell является отсутствие автоматического  преобразования в целые числа, как это, к примеру, сделано в языках C или C++. Для того чтобы такая возможность была, необходимо определить соответствующее перечисление экземпляром класса Enum. После  такого определения для перечисления становятся доступными некоторые интересные методы, к примеру методы для получения списков, состоящих из значений соответствующего перечисления, стоящих в определённом порядке.

Наконец, необходимо особо подчеркнуть, что алгебраический тип данных называется перечислением постольку, поскольку ни у одного из его конструкторов нет аргументов. Но это абсолютно не означает, что если программист задумал организовать перечисление, то он не может в алгебраический тип данных вставлять конструкторы с аргументами после того, как перечисление организовано. В наборе конструкторов в любом случае могут быть как конструкторы без аргументов, так и конструкторы с аргументами. Например, следующий алгебраический тип данных, который может определять наименования цветов, до создания конструктора RGB мог считаться перечислением, описывающим  цвета радуги:

data  Color  = Red                         -Красный

| Orange                    -Оранжевый

| Yellow                     -Жёлтый

| Green                      -Зелёный

| Blue                         -Голубой

| Indigo             -Синий

| Violet             -Фиолетовый

| RGB  Int Int Int  -Представление  цвета в системе RGB

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии