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

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

Пример

Простейшую структуру XML -документа в Standard ML можно определить следующим образом:

datatype simple_xml = Empty
                    | Word of string
                    | Tagged of string * simple_xml list

Это определение алгебраического типа данных . Оно вводит в программу четыре идентификатора: нуль-арный конструктор типов simple_xml и три конструктора объектов этого алгебраического типа: нуль-арный Empty , унарный Word и бинарный Tagged . Последний принимает два параметра (в данном случае в виде кортежа ), второй из которых имеет тип simple_xml list (то есть список объектов определяемого здесь типа). Таким образом, simple_xml представляет собой .

Конструкторы обладают всеми правами функций (например, конструктор Word имеет функциональный тип « string -> simple_xml »), и в частности, могут использоваться в абстракции функций .

fun listOfWords s =
   map Word (String.tokens Char.isSpace s)

fun toString e =
   let val scat = String.concat in
      case e of
         Empty => ""
       | Word s => s ^ " "
       | Tagged (tag, contents) => scat [ "<",tag,">", scat (map toString contents), "</",tag,">" ]
   end

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

Каждое применение конструктора Word к объекту типа «строка» порождает объект типа simple_xml . Эти порождённые объекты затем используются для построения списка (это происходит внутри функции map ) — таким образом, результатом функции listOfWords будет список объектов типа simple_xml . Это подтверждается её функциональным типом , который выводит компилятор: « string -> simple_xml list ». Соответственно, результат функции может непосредственно использоваться в качестве параметра для другого конструктора данного типа — Tagged — что породит новый объект типа simple_xml :

fun mkXmlFile s = Tagged ( "main", listOfWords s )

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

<main>Here is some text</main>

будет представлен в программе такой структурой данных :

Tagged ( "main", [Word "Here", Word "is", Word "some", Word "text"] )

В этой записи перемешивается использование конструкторов двух типов — simple_xml и list . Синтаксис « [ , , ] », конструирующий список, является на самом деле синтаксическим сахаром над цепочкой конструкторов типа list :

Tagged ( "main", Word "Here" :: Word "is" :: Word "some" :: Word "text" :: nil )

Хотя тип list и встроен во все Х-М-типизированные языки, но формально он определяется как с нуль-арным конструктором nil и бинарным конструктором cons , который обычно имеет инфиксное символьное имя (два двоеточия в классических диалектах ML или одно в Хаскеле ):

datatype 'a list = nil | :: of 'a * 'a list
infixr 5 ::

См. также

• Алгебраический тип данных
• Конструктор типов
• Род (теория типов)

Литература

• Riccardo Pucella. Notes on Programming Standard ML of New Jersey ( (англ.) ) // Last revised January 10, 2001. — Cornell University, 2001.