Конструктор (функциональное программирование)

Поделись знанием:
Перейти к: навигация, поиск

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

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



Пример

Простейшую структуру 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 представляет собой рекурсивный тип данных[en].

Конструкторы обладают всеми правами функций (например, конструктор 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 и встроен во все Х-М-типизированные языки, но формально он определяется как рекурсивный тип данных[en] с нуль-арным конструктором 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.

Отрывок, характеризующий Конструктор (функциональное программирование)

Молодец соскочил держать под уздцы лошадей, Анатоль с Долоховым пошли по тротуару. Подходя к воротам, Долохов свистнул. Свисток отозвался ему и вслед за тем выбежала горничная.
– На двор войдите, а то видно, сейчас выйдет, – сказала она.
Долохов остался у ворот. Анатоль вошел за горничной на двор, поворотил за угол и вбежал на крыльцо.
Гаврило, огромный выездной лакей Марьи Дмитриевны, встретил Анатоля.
– К барыне пожалуйте, – басом сказал лакей, загораживая дорогу от двери.
– К какой барыне? Да ты кто? – запыхавшимся шопотом спрашивал Анатоль.
– Пожалуйте, приказано привесть.
– Курагин! назад, – кричал Долохов. – Измена! Назад!
Долохов у калитки, у которой он остановился, боролся с дворником, пытавшимся запереть за вошедшим Анатолем калитку. Долохов последним усилием оттолкнул дворника и схватив за руку выбежавшего Анатоля, выдернул его за калитку и побежал с ним назад к тройке.


Марья Дмитриевна, застав заплаканную Соню в коридоре, заставила ее во всем признаться. Перехватив записку Наташи и прочтя ее, Марья Дмитриевна с запиской в руке взошла к Наташе.
– Мерзавка, бесстыдница, – сказала она ей. – Слышать ничего не хочу! – Оттолкнув удивленными, но сухими глазами глядящую на нее Наташу, она заперла ее на ключ и приказав дворнику пропустить в ворота тех людей, которые придут нынче вечером, но не выпускать их, а лакею приказав привести этих людей к себе, села в гостиной, ожидая похитителей.
Когда Гаврило пришел доложить Марье Дмитриевне, что приходившие люди убежали, она нахмурившись встала и заложив назад руки, долго ходила по комнатам, обдумывая то, что ей делать. В 12 часу ночи она, ощупав ключ в кармане, пошла к комнате Наташи. Соня, рыдая, сидела в коридоре.
– Марья Дмитриевна, пустите меня к ней ради Бога! – сказала она. Марья Дмитриевна, не отвечая ей, отперла дверь и вошла. «Гадко, скверно… В моем доме… Мерзавка, девчонка… Только отца жалко!» думала Марья Дмитриевна, стараясь утолить свой гнев. «Как ни трудно, уж велю всем молчать и скрою от графа». Марья Дмитриевна решительными шагами вошла в комнату. Наташа лежала на диване, закрыв голову руками, и не шевелилась. Она лежала в том самом положении, в котором оставила ее Марья Дмитриевна.
– Хороша, очень хороша! – сказала Марья Дмитриевна. – В моем доме любовникам свидания назначать! Притворяться то нечего. Ты слушай, когда я с тобой говорю. – Марья Дмитриевна тронула ее за руку. – Ты слушай, когда я говорю. Ты себя осрамила, как девка самая последняя. Я бы с тобой то сделала, да мне отца твоего жалко. Я скрою. – Наташа не переменила положения, но только всё тело ее стало вскидываться от беззвучных, судорожных рыданий, которые душили ее. Марья Дмитриевна оглянулась на Соню и присела на диване подле Наташи.
– Счастье его, что он от меня ушел; да я найду его, – сказала она своим грубым голосом; – слышишь ты что ли, что я говорю? – Она поддела своей большой рукой под лицо Наташи и повернула ее к себе. И Марья Дмитриевна, и Соня удивились, увидав лицо Наташи. Глаза ее были блестящи и сухи, губы поджаты, щеки опустились.
– Оставь… те… что мне… я… умру… – проговорила она, злым усилием вырвалась от Марьи Дмитриевны и легла в свое прежнее положение.
– Наталья!… – сказала Марья Дмитриевна. – Я тебе добра желаю. Ты лежи, ну лежи так, я тебя не трону, и слушай… Я не стану говорить, как ты виновата. Ты сама знаешь. Ну да теперь отец твой завтра приедет, что я скажу ему? А?
Опять тело Наташи заколебалось от рыданий.
– Ну узнает он, ну брат твой, жених!
– У меня нет жениха, я отказала, – прокричала Наташа.
– Всё равно, – продолжала Марья Дмитриевна. – Ну они узнают, что ж они так оставят? Ведь он, отец твой, я его знаю, ведь он, если его на дуэль вызовет, хорошо это будет? А?
– Ах, оставьте меня, зачем вы всему помешали! Зачем? зачем? кто вас просил? – кричала Наташа, приподнявшись на диване и злобно глядя на Марью Дмитриевну.
– Да чего ж ты хотела? – вскрикнула опять горячась Марья Дмитриевна, – что ж тебя запирали что ль? Ну кто ж ему мешал в дом ездить? Зачем же тебя, как цыганку какую, увозить?… Ну увез бы он тебя, что ж ты думаешь, его бы не нашли? Твой отец, или брат, или жених. А он мерзавец, негодяй, вот что!
– Он лучше всех вас, – вскрикнула Наташа, приподнимаясь. – Если бы вы не мешали… Ах, Боже мой, что это, что это! Соня, за что? Уйдите!… – И она зарыдала с таким отчаянием, с каким оплакивают люди только такое горе, которого они чувствуют сами себя причиной. Марья Дмитриевна начала было опять говорить; но Наташа закричала: – Уйдите, уйдите, вы все меня ненавидите, презираете. – И опять бросилась на диван.