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

Основы функционального программирования

• Вводная лекция
  
• Структуры данных и базисные операции:
  • Первая часть
    
  • Вторая часть
    

• Основы языка Haskell
  
  • Служебные слова и синтаксис
    
  • Модули и монады
    
  • Ввод-вывод
    
  • Другие статьи и учебники по Haskell →

• Конструирование функций
  
• Доказательство свойств функций
  
• Формализация функционального программирования на основе λ-исчисления
  
• Трансформация программ

• Категория «Функциональное программирование» →

Введение

Как уже́ говорилось в первой лекции, основой функциональной парадигмы программирования в большей мере являются такие направления развития математической мысли, как комбинаторная логика и λ-исчисление. В свою очередь последнее более тесно связано с функциональным программированием, и именно λ-исчисление называют теоретическими основами функционального программирования.

Для того, чтобы рассматривать теоретические основы функционального программирования, необходимо в первую очередь ввести некоторые соглашения, описать обозначения и построить некоторую формальную систему.

Пусть заданы объекты некоторого первичного типа $A$. Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от Маккарти (автора Лиспа), такие объекты называются атомами. В теории фактический способ реализации базисных операций и предикатов совершенно не важен, их существование просто постулируется. Поэтому каждый конкретный функциональный язык реализует базисный набор по-своему.

В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:

1. Операция создания пары — $\operatorname {prefix} (x,\;y)\equiv x:y\equiv [x\mid y]$. Эта операция также называется конструктором или составителем.
2. Операция отсечения головы — $\operatorname {head} (x)\equiv h(x)$. Это первая селективная операция.
3. Операция отсечения хвоста — $\operatorname {tail} (x)\equiv t(x)$. Это вторая селективная операция.

Селективные операции отсечения головы и хвоста также называют просто селекторами. Выделенные операции связаны друг с другом следующими тремя аксиомами:

1. $\operatorname {head} (x:y)=x$
2. $\operatorname {tail} (x:y)=y$
3. $\operatorname {prefix} {\Big (}\operatorname {head} (x:y),\;\operatorname {tail} (x:y){\Big )}=(x:y)$

Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество $S$-выражений (обозначение — $\operatorname {SExpr} (A)$). Например:

$a_{1}:(a_{2}:a_{3})\in \operatorname {SExpr} (A)$

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

Определение:

1. Пустой список $[\,]\in \operatorname {List} (A)$
2. $x\in A\land y\in \operatorname {List} (A)\Rightarrow x:y\in \operatorname {List} (A)$

Главное свойство списка: $x\in \operatorname {List} (A)\land x\neq [\,]\Rightarrow \operatorname {head} (x)\in A,\;\operatorname {tail} (x)\in \operatorname {List} (A)$.

Для обозначения списка из $n$ элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: $[a_{1},\;a_{2},\;\ldots ,\;a_{n}]$. Применяя к такому списку определённым образом операции $\operatorname {head}$ и $\operatorname {tail}$ можно добраться до любого элемента списка, так как:

$\operatorname {head} {\Big (}[a_{1},\;a_{2},\;\ldots ,\;a_{n}]{\Big )}=a_{1}$

$\operatorname {tail} {\Big (}[a_{1},\;a_{2},\;\ldots ,\;a_{n}]{\Big )}=[a_{2},\;\ldots ,\;a_{n}]$ (при $n>0$).

Кроме списков вводится ещё один тип данных, который носит название «списочная структура над $A$» (обозначение — $\operatorname {ListStr} (A)$), при этом можно построить следующую структуру отношений: $\operatorname {List} (A)\subset \operatorname {ListStr} (A)\subset \operatorname {SExpr} (A)$. Определение списочной структуры выглядит следующим образом:

Определение:

1. $a\in A\Rightarrow a\in \operatorname {ListStr} (A)$.
2. $\operatorname {List} {\Big (}\operatorname {ListStr} (A){\Big )}\in \operatorname {ListStr} (A)$.

Т. е. видно, что списочная структура — либо атом, либо список состоящий из списочных структур. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: ${\bigg [}a_{1},\;{\Big [}a_{2},\;a_{3},\;[a_{4}]\,{\Big ]},\;a_{5}{\bigg ]}$. Для списочных структур вводится такое понятие, как уровень вложенности.

Несколько слов о программной реализации

Пришло время уделить некоторое внимание рассмотрению программной реализации списков и списочных структур. Это необходимо для более тонкого понимания того, что происходит во время работы функциональной программы, как на каком-либо реализованном функциональном языке, так и на абстрактном языке.

Каждый объект занимает в памяти машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты. В этом случае пара $z=x:y$ графически может быть представлена так, как показано на рисунке 1.

Рисунок 1. Представление пары в памяти компьютера

Адрес ячейки, которая содержит указатели на $x$ и $y$, и есть объект $z$. Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.

Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечёркнутым квадратом (указатель ни на что не указывает).

Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее (${\bigg [}a_{1},\;{\Big [}a_{2},\;a_{3},\;[a_{4}]\,{\Big ]},\;a_{5}{\bigg ]}$) может быть представлена так, как показано на рисунке 2.

Рисунок 2. Графическое представление списочной структуры ${\bigg [}a_{1},\;{\Big [}a_{2},\;a_{3},\;[a_{4}]\,{\Big ]},\;a_{5}{\bigg ]}$

На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы $a_{1}$ и $a_{5}$ имеют уровень вложенности 1, атомы $a_{2}$ и $a_{3}$ — 2, а атом $a_{4}$ — 3 соответственно.

Остаётся отметить, что операция $\operatorname {prefix}$ требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции $\operatorname {head}$ и $\operatorname {tail}$ не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.

Примеры

Пример 5. Операция $\operatorname {prefix}$.

Для начала необходимо рассмотреть более подробно работу операции $\operatorname {prefix}$. Пояснение работы будет проведено на трёх более или менее общих примерах:

1. $\operatorname {prefix} (a_{1},a_{2})=a_{1}:a_{2}$ (при этом результат не является элементом $\operatorname {ListStr} (A)$).
2. $\operatorname {prefix} {\Big (}a_{1},\;[b_{1},\;b_{2}]{\Big )}=[a_{1},\;b_{1},\;b_{2}]$
3. $\operatorname {prefix} {\Big (}[a_{1},\;a_{2}],\;[b_{1},\;b_{2}]{\Big )}={\Big [}[a_{1},\;a_{2}],\;b_{1},\;b_{2}{\Big ]}$

Пример 6. Функция определения длины списка $\operatorname {length}$.

Перед тем, как собственно начать реализовывать функцию $\operatorname {length}$, необходимо понять, что она должна возвращать. Понятийное определение результата функции $\operatorname {length}$ может звучать как «количество элементов в списке, который передан функции в качестве параметра». Здесь возникает два случая — функции передан пустой список и функции передан непустой список. С первым случаем всё ясно — результат должен быть нулевым. Во втором случае задачу можно разбить на две подзадачи, путём разделения переданного списка на голову и хвост при помощи операций $\operatorname {head}$ и $\operatorname {tail}$.

Осмысленно, что операция $\operatorname {head}$ возвращает первый элемент списка, а операция $\operatorname {tail}$ возвращает список из оставшихся элементов. Пусть известна длина списка, полученного при помощи операции $\operatorname {tail}$, тогда длина исходного списка будет равна известной длине, увеличенной на единицу. В этом случае можно легко записать определение самой функции $\operatorname {length}$:

$\operatorname {length} ([\,])=0$

$\operatorname {length} (L)=1+\operatorname {length} {\Big (}\operatorname {tail} (L){\Big )}$

Пример 7. Функция слияния двух списков $\operatorname {append}$.

Реализовать функцию слияния (или сцепления) списков можно многими способами. Первое, что приходит в голову — деструктивное присваивание. Т. е. заменить указатель на $[\,]$ в конце первого списка на указатель на голову второго списка и тем самым получить результат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы запрещены в функциональном программировании (хотя, в очередной раз необходимо заметить, что в некоторых функциональных языках всё-таки есть такая возможность).

Второй способ состоит в копировании верхнего уровня первого списка и помещении в последний указатель копии ссылку на первый элемент второго списка. Этот способ хорош с точки зрения деструктивности (не выполняет деструктивных и побочных действий), однако требует дополнительных затрат памяти и времени.

$\operatorname {append} ([\,],\;L_{2})=L_{2}$

$\operatorname {append} (L_{1},\;L_{2})=\operatorname {prefix} {\bigg (}\operatorname {head} \left(L_{1}\right),\;\operatorname {append} {\Big (}\operatorname {tail} (L_{1}),\;L_{2}{\Big )}{\bigg )}$

Последний пример показывает, как при помощи постепенного конструирования можно построить новый список, который равен сцепке двух заданных.

Упражнения

1. Построить функции, вычисляющие $N$-ый элемент следующих рядов:
   1. $a_{n}=x^{n}$
   2. $a_{n}=\sum _{i=1}^{n}i$
   3. $a_{n}=\sum _{j=1}^{n}(\sum _{i=1}^{j}i)$
   4. $a_{n}=\sum _{i=0}^{p}n^{-i}$
   5. $a_{n}=e^{n}=\sum _{i=0}^{\infty }{\frac {n^{i}}{i!}}$
2. Объяснить результаты операции $prefix$, показанные в примере 5. Для объяснения можно воспользоваться графическим методом.
3. Объяснить результат работы функции $\operatorname {append}$ (пример 7). Пояснить, почему функция не является деструктивной.
4. Построить функции, работающие со списками:
   1. $\operatorname {getN}$ — функция вычленения $N$-ого элемента из заданного списка.
   2. $\operatorname {listSumm}$ — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
   3. $\operatorname {oddEven}$ — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
   4. $\operatorname {reverse}$ — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
   5. $\operatorname {map}$ — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.

Ответы для самопроверки

Большинство ответов для самопроверки представляют собой лишь одни из возможных вариантов (в большинстве случаев наиболее интуитивные).

1. Функции, вычисляющие $N$-ый элемент рядов:
   1. $\operatorname {power}$:
      • $\operatorname {power} (x,\;0)=1$
      • $\operatorname {power} (x,\;n)=x\cdot \operatorname {power} (x,\;n-1)$
   2. $\operatorname {summT}$:
      • $\operatorname {summT} (1)=1$
      • $\operatorname {summT} (n)=n+\operatorname {summT} (n-1)$
   3. $\operatorname {summP}$:
      • $\operatorname {summP} (1)=1$
      • $\operatorname {summP} (n)=\operatorname {summT} (n)+\operatorname {summP} (n-1)$
   4. $\operatorname {summPower}$:
      • $\operatorname {summPower} (n,\;0)=1$
      • $\operatorname {summPower} (n,\;p)={\frac {1}{\operatorname {power} (n,\;p)}}+\operatorname {summPower} (n,\;p-1)$
   5. $\operatorname {exponent}$:
      • $\operatorname {exponent} (n,\;0)=1$
      • $\operatorname {exponent} (n,\;p)={\frac {\operatorname {power} (n,\;p)}{\operatorname {factorial} (p)}}+\operatorname {exponent} (n,\;p-1)$
      • $\operatorname {factorial} (0)=1$
      • $\operatorname {factorial} (n)=n\cdot \operatorname {factorial} (n-1)$
2. Объяснение работы операции $\operatorname {prefix}$ можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции $\operatorname {prefix}$ также используется инфиксная запись посредством символа двоеточия.
   1. Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция $\operatorname {prefix}$ определяется именно таким образом.
   2. $\operatorname {prefix} {\Big (}a_{1},\;[b_{1},\;b_{2}]{\Big )}=\operatorname {prefix} {\Big (}a_{1},\;b_{1}:(b_{2}:[\,]){\Big )}=a_{1}:{\Big (}b_{1}:(b_{2}:[\,]){\Big )}=[a_{1},\;b_{1},\;b_{2}]$ (Эти преобразование проведены по определению списка).
   3. $\operatorname {prefix} {\Big (}[a_{1},\;a_{2}],\;[b_{1},\;b_{2}]{\Big )}=\operatorname {prefix} {\Big (}[a_{1},\;a_{2}],\;b_{1}:(b_{2}:[\,]){\Big )}={\Big (}[a_{1},\;a_{2}]{\Big )}:{\Big (}b_{1}:(b_{2}:[\,]){\Big )}={\Big [}[a_{1},\;a_{2}],\;b_{1},\;b_{2}{\Big ]}$.
3. В качестве примера работы функции $\operatorname {append}$ рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов: $[a,\;b]$ и $[c,\;d]$. Опять же для того, чтобы не загромождать объяснение, для записи операции $\operatorname {prefix}$ используется инфиксная форма. Для более полного понимания приведённого объяснения необходимо помнить определение списка.
   1. • $\operatorname {append} {\Big (}[a,\;b],\;[c,\;d]{\Big )}=a:\operatorname {append} {\Big (}[b],\;[c,\;d]{\Big )}=$

      $=a:{\bigg (}b:\operatorname {append} {\Big (}[\,],\;[c,\;d]{\Big )}{\bigg )}=a:{\bigg (}b:{\Big (}[c,\;d]{\Big )}{\bigg )}=a:{\bigg (}b:{\Big (}c:(d:[\,]){\Big )}{\bigg )}=[a,\;b,\;c,\;d]$.

4. Функции, работающие со списками:
   1. $\operatorname {getN}$:
      • $\operatorname {getN} (n,\;[\,])=\_$
      • $\operatorname {getN} (1,\;L)=\operatorname {head} (L)$
      • $\operatorname {getN} (n,\;L)=\operatorname {getN} {\Big (}n-1,\;\operatorname {tail} (L){\Big )}$
   2. $\operatorname {listSumm}$:
      • $\operatorname {listSumm} ([\,],\;L)=L$
      • $\operatorname {listSumm} (L,\;[\,])=L$
      • $\operatorname {listSumm} (L_{1},\;L_{2})=\operatorname {prefix} {\bigg (}{\Big (}\operatorname {head} (L_{1})+\operatorname {head} (L_{2}){\Big )},\;\operatorname {listSumm} {\Big (}\operatorname {tail} (L_{1}),\;\operatorname {tail} (L_{2}){\Big )}{\bigg )}$
   3. $\operatorname {oddEven}$:
      • $\operatorname {oddEven} ([\,])=[\,]$
      • $\operatorname {oddEven} ([x])=[x]$
      • $\operatorname {oddEven} (L)=\operatorname {append} {\bigg (}\operatorname {prefix} {\Big (}\operatorname {head} (\operatorname {tail} (L)),\;\operatorname {head} (L){\Big )},\;\operatorname {oddEven} {\Big (}\operatorname {tail} (\operatorname {tail} (L)){\Big )}{\bigg )}$
   4. $\operatorname {reverse}$:
      • $\operatorname {reverse} ([\,])=[\,]$
      • $\operatorname {reverse} (L)=\operatorname {append} {\bigg (}\operatorname {reverse} {\Big (}\operatorname {tail} (L){\Big )},\;{\Big [}\operatorname {head} (L){\Big ]}{\bigg )}$
   5. $\operatorname {map}$:
      • $\operatorname {map} (f,\;[\,])=[\,]$
      • $\operatorname {map} (f,\;L)=\operatorname {prefix} {\bigg (}f{\Big (}\operatorname {head} (L){\Big )},\;\operatorname {map} {\Big (}f,\;\operatorname {tail} (L){\Big )}{\bigg )}$