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