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

Как уже́ говорилось в '''[[Основы функционального программирования/Вводная лекция|первой лекции]]''', основой [[w:Функциональное программирование|функциональной парадигмы программирования]] в большей мере являются такие направления развития математической мысли, как [[w:Комбинаторная логика|комбинаторная логика]] и [[w:Лямбда-исчисление|λ-исчисление]]. В свою очередь последнее более тесно связано с функциональным программированием, и именно λ-исчисление называют теоретическими основами функционального программирования.

#Операция создания пары — <ttmath>prefix (x, y)</tt> <math>\equiv</math> <tt>x : y</tt> <math>\equiv</math> <tt>[x |\mid y]</ttmath>. Эта операция также называется конструктором или составителем.

#Операция отсечения головы — <ttmath>head (x)</tt> <math>\equiv</math> <tt>h (x)</ttmath>. Это первая селективная операция.

#Операция отсечения хвоста — <ttmath>tail (x)</tt> <math>\equiv</math> <tt>t (x)</ttmath>. Это вторая селективная операция.

#<ttmath>head (x : y) = x</ttmath>

#<ttmath>tail (x : y) = y</ttmath>

#<ttmath>prefix (head (x : y), tail (x : y)) = (x : y)</ttmath>

Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество <ttmath>S</ttmath>-выражений (обозначение — <math>SExpr(A)</math>). Например:

<center><ttmath>a1 a_{1}: (a2 a_{2}: a3a_{3})</tt> <math>\in SExpr(A)</math></center>

Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу <math>A</math>. Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами <ttmath>[]</ttmath> (хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество <math>List(A) \subset SExpr(A)</math>, которое называется «список над <math>A</math>».

Для обозначения списка из <math>n</math> элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: <math>>[a_1a_{1}, a_2a_{2}, \ldots, a_na_{n}]</math>. Применяя к такому списку определённым образом операции <ttmath>head</ttmath> и <ttmath>tail</ttmath> можно добраться до любого элемента списка, т.&nbsp;к.:

<math>head ([a1a_{1}, a2a_{2}, ...\ldots, ana_{n}]) = a1a_{1}</math>

Т.&nbsp;е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуру, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: <math>[a_1a_{1}, [a_2a_{2}, a_3a_{3}, [a_4a_{4}]], a_5a_{5}]</math>. Для списочных структур вводится такое понятие, как уровень вложенности.