|
В [[язык программирования|языках программирования]] и [[теория типов|теории типов]], '''конструктор типа''' представляет собой конструкцию [[система типов|типизированного]] [[формальный язык|формального языка]], которая строит новые типы из старых. Примерами типичных конструкторов типов служат [[тип-произведение|типы-произведения]], {{iw|Функциональный тип|функциональные типы|en|Function type}} и [[Список (информатика)|списки]]. [[Примитивный тип|Примитивные типы]] представляются конструкторами типов нулевой [[арность|арности]]. Конструкторы типов интенсивно используются в [[полнотиповое программирование|полнотиповом программировании]].
== Пример ==
Конструкторы типов являются важным элементов языков, [[Система типов Хиндли — Милнера|типизированных по Хиндли — Милнеру]].
Например, простейшую структуру [[XML]]-документа можно определить следующим образом:
<source lang=ocaml>
datatype simple_xml = Empty
| Word of string
| Tagged of string * simple_xml list
</source>
Это определение вводит в программу четыре идентификатора: [[алгебраический тип данных]] <code>simple_xml</code> и три его конструктора: [[арность|нуль-арный]] <code>Empty</code>, унарный <code>Word</code> и бинарный <code>Tagged</code>. Последний принимает два параметра (в данном случае в виде [[кортеж (информатика)|кортежа]]), второй из которых имеет тип <code>simple_xml list</code> (т.е. [[Список (информатика)|список]] объектов определяемого здесь типа). Таким образом, <code>simple_xml</code> представляет собой {{iw|рекурсивный тип данных||en|Recursive data type}}.
Конструкторы типов обладают всеми правами функций (например, конструктор <code>Word</code> имеет {{iw|функциональный тип||en|Function type}} «<code>string -> simple_xml</code>»), и в частности, могут использоваться в [[абстракция функций|абстракции функций]].
<source lang=ocaml>
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
</source>
В теле функции <code>listOfWords</code> можно видеть как конструктор <code>Word</code> передаётся в качестве параметра функции [[map|<code>map</code>]], и та применяет его к каждому элементу списка строк, который она получает вторым параметром. Список строк, в свою очередь, получен токенизацией (в данном случае просто разбиением на слова) строки, которую получила функция <code>listOfWords</code> входным параметром.
Каждое применение конструктора <code>Word</code> к объекту типа «строка» порождает объект типа <code>simple_xml</code>. Эти порождённые объекты затем используются для построения [[Список (информатика)|списка]] (это происходит внутри функции [[map|<code>map</code>]]) — таким образом, результатом функции <code>listOfWords</code> будет список объектов типа <code>simple_xml</code>. Это подтверждается её {{iw|Функциональный тип|функциональным типом|en|Function type}}, который [[вывод типов|выводит]] компилятор: «<code>string -> simple_xml list</code>». Соответственно, результат функции может непосредственно использоваться в качестве параметра для другого конструктора типа — <code>Tagged</code> — что породит новый объект типа <code>simple_xml</code>:
<source lang=ocaml>
fun mkXmlFile s = Tagged ( "main", listOfWords s )
</source>
Таким образом, [[XML]]-документ строится посредством рекурсивной композиции конструкторов типа (отсюда и название «''рекурсивный тип данных''»). Например, такой документ
<source lang=xml>
<main>Here is some text</main>
</source>
будет представлен в программе такой [[Структура данных|структурой данных]]:
<source lang=ocaml>
Tagged ( "main", [Word "Here", Word "is", Word "some", Word "text"] )
</source>
В этой записи перемешивается использование конструкторов двух типов — <code>simple_xml</code> и <code>list</code>. Синтаксис «<code>[ , , ]</code>», конструирующий список, является на самом деле [[синтаксический сахар|синтаксическим сахаром]] над цепочкой конструкторов типа <code>list</code>:
<source lang=ocaml>
Tagged ( "main", Word "Here" :: Word "is" :: Word "some" :: Word "text" :: nil )
</source>
Хотя тип <code>list</code> и встроен во все [[Система типов Хиндли — Милнера|Х-М-типизированные]] языки, но формально он определяется как {{iw|рекурсивный тип данных||en|Recursive data type}} с нуль-арным конструктором <code>nil</code> и инфиксным бинарным конструктором <code>cons</code>, который обычно имеет символьное имя (два двоеточия в классических диалектах [[ML]] или одно в [[Haskell|Хаскеле]]):
<source lang=ocaml>
datatype 'a list = nil | :: of 'a * 'a list
infix ::
</source>
== Теория ==
[[Просто типизированное лямбда-исчисление]] можно рассматривать как язык с единственным конструктором типа — конструктором функционального типа. [[Каррирование]] позволяет рассматривать типы-произведения в [[типизированное лямбда-исчисление|типизированном лямбда-исчислении]] как встроенные.
| 