Основы функционального программирования/Структуры данных и базисные операции: различия между версиями
Содержимое удалено Содержимое добавлено
м Шаблон со списком лекций |
Первый раздел более или менее проработан... |
||
Строка 1:
{{ОФП Содержание}}
== Введение ==
Как
Для того, чтобы рассматривать теоретические основы функционального программирования, необходимо в первую очередь ввести некоторые соглашения,
Пусть заданы объекты некоторого первичного типа <math>A</math>. Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от [[w:МакКарти, Джон|МакКарти]] (автор [[w:Лисп|Lisp’а]]), такие объекты называются атомами. В теории фактический способ реализации базисных операций и [[w:Предикат|предикатов]] совершенно не важен, их существование просто постулируется. Однако каждый конкретный функциональный язык реализует базисный набор по-своему.
В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:
#Операция создания пары — <tt>prefix (x, y)</tt>
#Операция отсечения головы — <tt>head (x)</tt>
#Операция отсечения хвоста — <tt>tail (x)</tt>
Селективные операции отсечения головы и хвоста также называют просто селекторами. Выделенные операции связаны друг с другом следующими тремя аксиомами:
#<tt>head (x : y) = x</tt>
#<tt>tail (x : y) = y</tt>
#<tt>prefix (head (x : y), tail (x : y)) = (x : y)</tt>
Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество <tt>S</tt>-выражений (обозначение —
Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу <math>A</math>. Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами <tt>[]</tt> (хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество <math>List
'''Определение:'''
#Пустой список <math>[]
#<math>x
Главное свойство списка: <math>x
Для обозначения списка из <math>n</math> элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: <math>>[
head ([a1, a2, ..., an]) = a1
tail ([a1, a2, ..., an]) = [a2, ..., an] (при n > 0).
Кроме списков вводится
Определение:
#<math>a
#<math>List
Т. е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуру, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: <math>[
== Несколько слов о программной реализации ==
|