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

Лекции по функциональному программированию

1. Вводная лекция 2. Структуры данных и базисные операции 3. Структуры данных и базисные операции — 2 4. Основы языка Haskell 5. Служебные слова и синтаксис Haskell'а 6. Модули и монады в Haskell'е 7. Операции ввода/вывода в Haskell'е 8. Конструирование функций 9. Доказательство свойств функций 10. Формализация ФП на основе λ-исчисления 11. Трансформация программ

В этой лекции продолжается описание структур данных и базовых операций, начатое в лекции 2. Более или менее подробно рассматриваются другие аспекты функциональной парадигмы программирования.

Типы в функциональных языках

В первой лекции говорилось, что аргументами функций могут быть не только переменные базовых типов, но и другие функции. В этом случае появляется понятие функций высшего порядка. Но для рассмотрения функций высшего порядка необходимо ввести понятие функционального типа (или тип функции). Пусть некоторая функция $f$ — это функция одной переменной из множества $A$, принимающая значение из множества $B$. Тогда по определению:

$\#(f) : A \rightarrow B$

Знак $\#(f)$ обозначает «тип функции $f$». Таким образом, типы, в которых есть символ стрелки $\rightarrow$, носят название функциональных типов. Иногда для их обозначения используется более изощренная запись: $B^{A}$ (далее будет использоваться только стрелочная запись, т. к. для некоторых функций их типы чрезвычайно сложно представить при помощи степеней).

Например: $\#(sin) : Float \rightarrow Float$, $\#(length) : List(A) \rightarrow Integer$

Для функций многих аргументов определение типа можно выводить при помощи операции декартового произведения (например, $\#(add(x, y)) : Float \times Float \rightarrow Float$). Однако в функциональном программировании такой способ определения типов функций многих переменных не прижился.

В 1924 году М. Шёнфинкель предложил представлять функции многих аргументов как последовательность функций одного аргумента. В этом случае тип функции, которая складывает два действительных числа, выглядит так: $Float \rightarrow (Float \rightarrow Float)$. Т. е. тип таких функций получается последовательным применением символа стрелки $\rightarrow$. Пояснить этот процесс можно на следующем примере:

Пример 8. Тип функции $add(x, y)$.

Предположительно, каждый из аргументов функции $add$ уже́ означен, пусть $x = 5$, $y = 7$. В этом случае из функции $add$ путём удаления первого аргумента получается новая функция — $add5$, которая прибавляет к своему единственному аргументу число $5$. Её тип получается легко, он по определению таков: $Float \rightarrow Float$. Теперь, возвращаясь назад, можно понять, почему тип функции $add$ равен $Float \rightarrow (Float \rightarrow Float)$.

Для того чтобы не изощряться с написанием функций типа $add5$ (как в предыдущем примере), была придумана специальная аппликативная форма записи в виде «оператор-операнд». Предпосылкой для этого послужило новое видение на функции в функциональном программировании. Ведь если традиционно считалось, что выражение $f(5)$ обозначает «применение функции $f$ к значению аргумента, равному $5$» (т. е. вычисляется только аргумент), то в функциональном программировании считается, что значение функции также вычисляется. Так, возвращаясь к примеру 8, функцию $add$ можно записать как $(add(x))y$, а когда аргументы получают конкретные значения (например, $(add(5))7)$, сначала вычисляются все функции, пока не появится функция одного аргумента, которая применяется к последнему.

Таким образом, если функция $f$ имеет тип $A_{1} \rightarrow (A_{2} \rightarrow (\ldots(A_{n} \rightarrow B)\ldots))$, то чтобы полностью вычислить значение $f(a_{1}, a_{2}, \ldots, a_{n})$ необходимо последовательно провести вычисление $(\ldots(f(a_{1})a_{2})\ldots)a_{n}$. И результатом вычисления будет объект типа $B$.

Соответственно выражение, в котором все функции рассматриваются как функции одного аргумента, а единственной операцией является аппликация (применение), называются выражениями в форме «оператор-операнд». Такие функции получили название «каррированные», а сам процесс сведения типа функции к виду, приведённому в предыдущем абзаце — каррированием (по имени Карри Хаскелла).

В λ-исчислении также присутствует математическая абстракция для аппликативных форм записей. Например:

$f (x) = x^{2} + 5 \Rightarrow \lambda x.(x^{2} + 5)$ $f (x, y) = x + y \Rightarrow \lambda y.\lambda x.(x + y)$ $f (x, y, z) = x^{2} + y^{2} + z^{2} \Rightarrow \lambda z.\lambda y.\lambda x.(x^{2} + y^{2} + z^{2})$

И так далее...

Несколько слов о нотации абстрактного языка

Образцы и клозы

Необходимо отметить, что в нотации абстрактного функционального языка, который использовался до сих пор для написания примеров функций, можно было бы использовать такую конструкцию, как $if-then-else$. Например, при описании функции $append$ (см. пример 7), её тело можно было бы записать следующим образом:

$append(L_{1}, L_{2}) = if (L_{1} = []) then L_{2} else head(L_{1}) : append(tail(L_{1}), L_{2})$

Однако данная запись чревата непониманием и трудным разбором. Поэтому даже в примере 7 была использована нотация, которая поддерживает так называемые «образцы».

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

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

Примеры образцов:

• $5$ — просто числовая константа;
• $X$ — просто переменная;
• $X:(Y:Z)$ — пара;
• $[X, Y]$ — список.

К образцам предъявляется единственое требование, без которого сопоставление с образцами может быть выполнено неверно. Требование это звучит следующим образом: при сопоставлении образца с данными означивание переменных должно происходить единственным образом. Т. е., например, выражение $(1 + X \Rightarrow 5)$ можно использовать как образец, т. к. означивание переменной $X$ происходит единственным образом ($X = 4$), а выражение $(X + Y \Rightarrow 5)$ использовать в качестве образца нельзя, ибо означить переменные $X$ и $Y$ можно различным образом.

Кроме образцов в функциональном программировании вводится такое понятие, как «клоз» (от англ. «clause»). По определению клозы выглядят так:

$\mathbf{def} f p_{1}, \ldots, p_{n} = expr$

где:

• $\mathbf{def}$ и $=$ — константы абстрактного языка;
• $f$ — имя определяемой функции;
• $p_{i}$ — последовательность образцов (при этом $n \geq 0$);
• $expr$ — выражение.

Таким образом, определение функции в функциональном программировании есть просто последовательность клозов (возможно состоящая из одного элемента). Для того, чтобы упростить запись определений функций, далее слово $\mathbf{def}$ будет опускаться.

Пример 9. Образцы и клозы в функции $length$.

$length([]) = 0$

$length(L) = 1 + length(tail(L))$

Пусть вызов функции $length$ произведён с параметром $[a, b, c]$. В этом случае начнёт свою работу механизм сопоставления с образцом. Последовательно перебираются все клозы и делаются попытки сопоставления. В данном случае удачное сопоставление будет только во втором клозе (т. к. список $[a, b, c]$ не пуст).

Интерпретация вызова функции заключается в нахождении первого по порядку сверху вниз образца, успешно сопоставимого с фактическим параметром. Значение переменных образца, означиваемые в результате сопоставления, подставляются в правую часть клоза (выражение $expr$), вычисленное значение которой в данном контексте объявляется значением вызова функции.

Охрана

При написании функций в абстрактной нотации допустимо использовать так называемую охрану, т. е. ограничения на значения переменных образца. Например, при использовании охраны функция $length$ будет выглядеть примерно следующим образом:

$length(L) = 0 \mathbf{when} L = []$

$length(L) = 1 + length(tail(L)) \mathbf{otherwise}$

В рассмотренном коде слова́ $\mathbf{when}$ (когда) и $\mathbf{otherwise}$ (в противном случае) являются зарезервированными словами языка. Однако использование этих слов не является необходимым условием для организации охраны. Охрану можно организовывать различными способами, в том числе и с помощью λ-исчисления:

$append = \lambda [].(\lambda L.L)$

$append = \lambda (h:t).(\lambda L.h:append(t, L))$

Представленная запись не очень читабельна, поэтому использоваться она будет только в крайних случаях по необходимости.

Локальные переменные

Как уже́ говорилось, использование локальных переменных представляет собой побочный эффект, поэтому оно недопустимо в функциональных языках. Однако в некоторых случаях использование локальных переменных носит оптимизирующий характер, что позволяет сэкономить время и ресурсы во время вычислений.

Пусть $f$ и $h$ — функции, и необходимо вычислить выражение $h(f(X),f(X))$. Если в языке нет оптимизирующих методов, то в этом случае произойдёт двойное вычисление выражения $f(X)$. Чтобы этого не произошло, можно прибегнуть к такому изощренному способу: $(\lambda v.h(v, v))(f(X))$. Естественно, что в этом случае выражение $f(X)$ вычислится первым и один раз. Для того, чтобы минимизировать использование λ-исчисления, далее будет применяться следующая форма записи:

$\mathbf{let} v = f(X) \mathbf{in} h(v, v)$

(слова́ $\mathbf{let}$, $=$ и $\mathbf{in}$ — зарезервированы в языке). В этом случае переменная $v$ будет называться локальной.

Элементы программирования

Накапливающий параметр — аккумулятор

Бывает так, что при выполнении функции исключительно серьезно встаёт проблема расхода памяти. Эту проблему можно пояснить на примере функции, вычисляющей факториал числа:

$Factorial(0) = 1$

$Factorial(N) = N * Factorial(N - 1)$

Если провести пример вычисления этой функции с аргументом $3$, то можно будет увидеть следующую последовательность:

$Factorial(3)$

==> $3 * Factorial(2)$

==> $3 * 2 * Factorial(1)$

==> $3 * 2 * 1 * Factorial(0)$

==> $3 * 2 * 1 * 1$

==> $3 * 2 * 1$

==> $3 * 2$

==> $6$

На примере этого вычисления наглядно видно, что при рекурсивных вызовах функций очень сильно используется память. В данном случае количество памяти пропорционально значению аргумента, но аргументов может быть большее число. Возникает резонный вопрос: можно ли так написать функцию вычисления факториала (и ей подобные), чтобы память использовалась минимально?

Чтобы ответить на данный вопрос положительно, необходимо рассмотреть понятие аккумулятора (накопителя). Для этого можно рассмотреть следующий пример:

Пример 10. Функция вычисления факториала с аккумулятором.

$Factorial_A(N) = F(N, 1)$

$F(0, A) = A$

$F(N, A) = F((N - 1), (N * A))$

В этом примере второй параметр функции $F$ выполняет роль аккумулирующей переменной, именно в ней содержится результат, который возвращается по окончании рекурсии. Сама же рекурсия в этом случае принимает вид «хвостовой», память при этом расходуется только на хранение адресов возврата значения функции.

Хвостовая рекурсия представляет собой специальный вид рекурсии, в которой имеется единственный вызов рекурсивной функции и при этом этот вызов выполняется после всех вычислений.

При реализации вычисления хвостовой рекурсии могут выполняться при помощи итераций в постоянном объёме памяти. На практике это обозначает, что «хороший» транслятор функционального языка должен «уметь» распознавать хвостовую рекурсию и реализовывать её в виде цикла. В свою очередь, метод накапливающего параметра не всегда приводит к хвостовой рекурсии, однако он однозначно помогает уменьшить общий объём памяти.

Принципы построения определений с накапливающим параметром

1. Вводится новая функция с дополнительным аргументом (аккумулятором), в котором накапливаются результаты вычислений.
2. Начальное значение аккумулирующего аргумента задается в равенстве, связывающем старую и новую функции.
3. Те равенства исходной функции, которые соответствуют выходу из рекурсии, заменяются возвращением аккумулятора.
4. Равенства, соответствующие рекурсивному определению, выглядят как обращения к новой функции, в котором аккумулятор получает то значение, которое возвращается исходной функцией.

Возникает вопрос: любую ли функцию можно преобразовать для вычисления с аккумулятором? Очевидно, что ответ на этот вопрос отрицателен. Построение функций с накапливающим параметром — приём не универсальный, и он не гарантирует получения хвостовой рекурсии. С другой стороны, построение определений с накапливающим параметром является делом творческим. В этом процессе необходимы некоторые эвристики.

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

Общий вид рекурсивных определений, позволяющих при трансляции обеспечить вычисления в постоянном объёме памяти через итерацию, называется равенствами в итеративной форме.

Общий вид равенств в итеративной форме может быть описан следующим образом:

$f_{i} (p_{ij}) = e_{ij}$

При этом на выражения $e_{ij}$ накладываются следующие ограничения:

1. $e_{ij}$ — «простое» выражение, т. е. оно не содержит рекурсивных вызовов, а только операции над данными.
2. $e_{ij}$ имеет вид $f_{k}(v_{k})$, при этом $v_{k}$ — последовательность простых выражений. Это и есть хвостовая рекурсия.
3. $e_{ij}$ — условное выражение с простым выражением в условии, ветви которого определяются этими же тремя пунктами.

Упражнения

1. Построить функции, работающие со списками. При необходимости воспользоваться дополнительными функциями и теми, что определены в лекции 2.
   • $ReverseAll$ — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.
   • $Position$ — функция, возвращающая номер первого вхождения заданного атома в список.
   • $Set$ — функция, возвращающая список из всех атомов, содержащихся в заданном списке. Каждый атом должен присутствовать в результирующем списке в единственном числе.
   • $Frequency$ — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.
2. Написа́ть (если это возможно) функции с накапливающим параметром для заданий из упражнения 1 лекции 2.

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

1. Следующие описания реализуют заявленные функции. В некоторых пунктах реализованы дополнительные функции, обойтись без которых представляется сложным.
   1. $ReverseAll$:
      • $ReverseAll(L) = L when atom(L)$
      • $ReverseAll ([]) = []$
      • $ReverseAll(H:T) = Append(ReverseAll(T), ReverseAll(H)) otherwise$
   2. $Position$:
      • $Position(A, L) = Position_N(A, L, 0)$
      • $Position_N(A, (A:L), N) = N + 1$
      • $Position_N (A, (B:L), N) = Position_N (A, L, N + 1)$
      • $Position_N (A, [], N) = 0$
   3. $Set$:
      • $Set([]) = []$
      • $Set(H:T) = Include(H, Set(T))$
      • $Include(A, []) = [A]$
      • $Include(A, A:L) = A:L$
      • $Include(A, B:L) = prefix(B, Include(A, L))$
   4. $Frequency$:
      • $Frequency(L) = F([], L)$
      • $F(L, []) = L$
      • $F(L, H:T) = F(Corrector(H, L), T)$
      • $Corrector(A, []) = [A:1]$
      • $Corrector(A, (A:N):T) = prefix((A:N + 1), T)$
      • $Corrector(A, H:T) = prefix(H, Corrector(A, T))$
2. Для всех функций из упражнения 1 лекции 2 можно построить определения с накапливающим параметром. С другой стороны, возможно некоторые из вновь построенных функций не будут оптимизированы.
   1. $Power\_A$:
      • $Power\_A(X, N) = P(X, N, 1)$
      • $P(X, 0, A) = A$
      • $P(X, N, A) = P(X, N - 1, X * A)$
   2. $Summ\_T\_A$:
      • $Summ\_T\_A(N) = ST(N, 0)$
      • $ST(0, A) = A$
      • $ST(N, A) = ST(N - 1, N + A)$
   3. $Summ\_P\_A$:
      • $Summ\_P\_A(N) = SP(N, 0)$
      • $SP(0, A) = A$
      • $SP(N, A) = SP(N - 1, Summ\_T\_A(N) + A)$
   4. $Summ\_Power\_A$:
      • $Summ\_Power\_A(N, P) = SPA(N, P, 0)$
      • $SPA(N, 0, A) = A$
      • $SPA(N, P, A) = SPA(N, P - 1, (1 / Power\_A(N, P)) + A)$
   5. $Exponent\_A$:
      • $Exponent\_A(N, P) = E(N, P, 0)$
      • $E(N, 0, A) = A$
      • $E(N, P - 1, (Power\_A(N, P) / Factorial\_A(P)) + A)$