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

Patarakin в 09:17, 19 октября 2022

2022-10-19T09:17:53Z

← Предыдущая версия		Версия от 12:17, 19 октября 2022
Строка 1:		Строка 1:
	В [[теория типов\|теории типов]] и [[функциональное программирование\|функциональных языках программирования]] '''конструктор алгебраического типа данных''' или просто '''конструктор''' представляет собой функцию с пустым телом, конструирующую объект '''[[Алгебраический тип данных\|алгебраического типа данных]]'''.		В [[теория типов\|теории типов]] и [[функциональное программирование\|функциональных языках программирования]] '''конструктор алгебраического типа данных''' или просто '''конструктор''' представляет собой функцию с пустым телом, конструирующую объект '''[[Алгебраический тип данных\|алгебраического типа данных]]'''.

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

	== Пример ==		== Пример ==

Patarakin в 09:17, 19 октября 2022

2022-10-19T09:17:26Z

← Предыдущая версия		Версия от 12:17, 19 октября 2022
Строка 5:		Строка 5:
	== Пример ==		== Пример ==
	Простейшую структуру [[XML]]-документа в [[Standard ML]] можно определить следующим образом<		Простейшую структуру [[XML]]-документа в [[Standard ML]] можно определить следующим образом<
			<syntaxhighlight lang="ocaml" line>
	<~~source~~ lang=ocaml>
	datatype simple_xml = Empty		datatype simple_xml = Empty
	\| Word of string		\| Word of string
	\| Tagged of string * simple_xml list		\| Tagged of string * simple_xml list
	</~~source~~>		</syntaxhighlight>
	Это определение [[алгебраический тип данных\|алгебраического типа данных]]. Оно вводит в программу четыре идентификатора: нуль-арный [[конструктор типов]] <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> имеет [[функциональный тип]] «<code>string -> simple_xml</code>»), и в частности, могут использоваться в [[абстракция функций\|абстракции функций]].		Конструкторы обладают всеми правами функций.
	<~~source~~ lang=ocaml>		<syntaxhighlight lang="ocaml" line>
	fun listOfWords s =		fun listOfWords s =
	map Word (String.tokens Char.isSpace s)		map Word (String.tokens Char.isSpace s)
Строка 25:		Строка 25:
	\| Tagged (tag, contents) => scat [ "<",tag,">", scat (map toString contents), "</",tag,">" ]		\| Tagged (tag, contents) => scat [ "<",tag,">", scat (map toString contents), "</",tag,">" ]
	end		end
	</~~source~~>		</syntaxhighlight>

	[[Категория:Структуры данных]]		[[Категория:Структуры данных]]

Patarakin в 09:10, 19 октября 2022

2022-10-19T09:10:28Z

@@ Строка 1: / Строка 1: @@
-{{не путать|Конструктор типов}}
+В [[теория типов|теории типов]] и [[функциональное программирование|функциональных языках программирования]] '''конструктор алгебраического типа данных''' или просто '''конструктор''' представляет собой функцию с пустым телом, конструирующую объект '''[[Алгебраический тип данных|алгебраического типа данных]]'''.
 Алгебраические типы данных являются важным элементом языков, [[Система типов Хиндли — Милнера|типизированных по Хиндли — Милнеру]].
 == Пример ==
-Простейшую структуру [[XML]]-документа в [[Standard ML]] можно определить следующим образом<!-- Пример взят из {{sfn|Pucella, Notes on Programming SML/NJ|2001|loc=5.3 Prettyprinting|с=136}}, с двумя изменениями: дополнен нуль-арным конструктором для более полного изложения; тип запись заменен на кортеж для упрощения кодов -->:
+Простейшую структуру [[XML]]-документа в [[Standard ML]] можно определить следующим образом<
 <source lang=ocaml>
 datatype simple_xml = Empty
@@ Строка 26: / Строка 26: @@
     end
 </source>
 [[Категория:Структуры данных]]

Patarakin: 1 версия импортирована

2022-10-19T07:30:52Z

1 версия импортирована

← Предыдущая версия		Версия от 10:30, 19 октября 2022
(нет различий)

188.232.183.106: Просто опечатка, видимо.

2020-12-24T10:18:27Z

Просто опечатка, видимо.

Новая страница

{{не путать|Конструктор типов}}
В [[теория типов|теории типов]] и [[функциональное программирование|функциональных языках программирования]] '''конструктор алгебраического типа данных''' или просто '''конструктор''' представляет собой функцию с пустым телом, конструирующую объект '''[[Алгебраический тип данных|алгебраического типа данных]]'''. Оптимизирующие компиляторы исполняют эти функции статически, то есть {{iw|Стадия компиляции (программирование)|на этапе компиляции|en|compile time}}.

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

== Пример ==
Простейшую структуру [[XML]]-документа в [[Standard ML]] можно определить следующим образом:
<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> имеет [[функциональный тип]] «<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>. Эти порождённые объекты затем используются для построения [[Список (информатика)|списка]] (это происходит внутри функции <code>map</code>) — таким образом, результатом функции <code>listOfWords</code> будет список объектов типа <code>simple_xml</code>. Это подтверждается её [[Функциональный тип|функциональным типом]], который [[вывод типов|выводит]] компилятор: «<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
infixr 5 ::
</source>

== См. также ==
* [[Алгебраический тип данных]]
* [[Конструктор типов]]
* [[Род (теория типов)]]

== Литература ==
* {{статья
|автор = Riccardo Pucella
|заглавие = Notes on Programming Standard ML of New Jersey
|ссылка =
|язык ={{ref-en}}
|издание = Last revised January 10, 2001
|издательство = Cornell University
|год = 2001
|isbn =
|ref = Pucella, Notes on Programming SML/NJ
}}

{{типы данных}}

[[Категория:Теория типов]]
[[Категория:Инкапсуляция (программирование)]]
[[Категория:Типы данных]]
[[Категория:Структуры данных]]
[[Категория:Языки программирования семейства ML]]