Основы функционального программирования/Структуры данных и базисные операции: различия между версиями

Содержимое удалено Содержимое добавлено
м Шаблон со списком лекций
Первый раздел более или менее проработан...
Строка 1:
{{ОФП Содержание}}
 
== Введение ==
= Лекция 2. «Структуры данных и базисные операции» =
 
Как ужеуже́ говорилось в [[Основы функционального программирования/Вводная лекция|первой лекции]], основой [[w:Функциональное программирование|функциональной парадигмы программирования]] в большей мере являются такие направления развития математической мысли, как [[w:Комбинаторная логика|комбинаторная логика]] и [[w:Лямбда-исчисление|λ-исчисление]]. В свою очередь последнее более тесно связано с функциональным программированием, и именно λ-исчисление называют теоретическими основами функционального программирования.
 
Для того, чтобы рассматривать теоретические основы функционального программирования, необходимо в первую очередь ввести некоторые соглашения, описатьописа́ть обозначения и построить некоторую формальную систему.
 
Пусть заданы объекты некоторого первичного типа <math>A</math>. Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от [[w:МакКарти, Джон|МакКарти]] (автор [[w:Лисп|Lisp’а]]), такие объекты называются атомами. В теории фактический способ реализации базисных операций и [[w:Предикат|предикатов]] совершенно не важен, их существование просто постулируется. Однако каждый конкретный функциональный язык реализует базисный набор по-своему.
 
В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:
 
#Операция создания пары — <tt>prefix (x, y)</tt> <math>\equiv</math> <tt>x : y</tt> <math>\equiv</math> <tt>[x | y]</tt>. Эта операция также называется конструктором или составителем.
#Операция отсечения головы — <tt>head (x)</tt> <math>\equiv</math> <tt>h (x)</tt>. Это первая селективная операция.
#Операция отсечения хвоста — <tt>tail (x)</tt> <math>\equiv</math> <tt>t (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>-выражений (обозначение — Sexpr <math>SExpr(A)</math>). Например:
 
<center><tt>a1 : (a2 : a3)</tt> <math>\in SexprSExpr(A)</math></center>
 
Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу <math>A</math>. Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами <tt>[]</tt> (хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество <math>List (A)  Sexpr\subset SExpr(A)</math>, которое называется «список над <math>A</math>».
 
'''Определение:'''
 
#Пустой список <math>[] \in List (A)</math>
#<math>x \in A &\and y \in List (A) \Rightarrow x : y \in List (A)</math>
 
Главное свойство списка: <math>x \in List (A) &\and x \neq [] \Rightarrow head (x) \in A;, tail (x) \in List (A)</math>.
 
Для обозначения списка из <math>n</math> элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: <math>>[a1a_1, a2a_2, ...\ldots, ana_n]</math>. Применяя к такому списку определеннымопределённым образом операции <tt>head</tt> и <tt>tail</tt> можно добраться до любого элемента списка, т.&nbsp;к.:
 
head ([a1, a2, ..., an]) = a1
tail ([a1, a2, ..., an]) = [a2, ..., an] (при n > 0).
 
Кроме списков вводится ещеещё один тип данных, который носит название «списочная структура над <math>A</math>» (обозначение — List_str <math>ListStr(A)</math>), при этом можно построить следющую структуру отношений: <math>List (A)  List_str\subset ListStr(A)  Sexpr\subset SExpr(A)</math>. Определение списочной структуры выглядит следующим образом:
 
Определение:
 
#<math>a \in A \Rightarrow a  List_str\in ListStr(A)</math>.
#<math>List (List_str ListStr(A))  List_str\in ListStr(A)</math>.
 
Т.&nbsp;е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуру, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: <math>[a1a_1, [a2a_2, a3a_3, [a4a_4]], a5a_5]</math>. Для списочных структур вводится такое понятие, как уровень вложенности.
 
== Несколько слов о программной реализации ==