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

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

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

Например: <math>\#(\sin) : \operatorname{Float} \rightarrow \operatorname{Float}</math>, <math>\#(\operatorname{length}) : \operatorname{List}(A) \rightarrow \operatorname{Integer}</math>

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

В 1924&nbsp;году [[w:Шёнфинкель, Мозес|М.&nbsp;Шёнфинкель]] предложил представлять функции многих аргументов как последовательность функций одного аргумента. В этом случае тип функции, которая складывает два действительных числа, выглядит так: <math>\operatorname{Float} \rightarrow (\operatorname{Float} \rightarrow \operatorname{Float})</math>. Т.&nbsp;е.То есть тип таких функций получается последовательным применением символа стрелки <math>\rightarrow</math>. Пояснить этот процесс можно на следующем примере:

'''Пример&nbsp;8. Тип функции <math>\operatorname{add}(x, y)</math>.'''

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

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

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

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

<center><math>f (x) = x^{2} + 5 &\Rightarrow &\lambda x.(x^{2} + 5)</math></center>\\

Необходимо отметить, что в нотации абстрактного функционального языка, который использовался до сих пор для написания примеров функций, можно было бы использовать такую конструкцию, как <math>\operatorname{if}-\operatorname{then}-\operatorname{else}</math>. Например, при описании функции <math>\operatorname{append}</math> (см. '''[[Основы функционального программирования/Структуры данных и базисные операции#Примеры|пример&nbsp;7]]'''), её тело можно было бы записать следующим образом:

<math>\operatorname{append}(L_{1}L_1, L_{2}L_2) = \operatorname{if} (L_{1}L_1 = [\,])\ \operatorname{then}\ L_L_2\ \operatorname{2else}\ else head(L_\operatorname{1head}(L_1) : \operatorname{append}(tail(L_\operatorname{1tail}(L_1), L_{2}L_2)</math>

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

<math>\mathbf{def} f p_{1}p_1, \ldots, p_{n} = \operatorname{expr}</math>

*<math>p_{i}p_i</math> — последовательность образцов (при этом <math>n \geq 0</math>);

*<math>\operatorname{expr}</math> — выражение.

'''Пример&nbsp;9. Образцы и клозы в функции <math>\operatorname{length}</math>.'''

<math>\operatorname{length}([\,]) = 0</math>

<math>\operatorname{length}(L) = 1 + \operatorname{length}(\operatorname{tail}(L))</math>

Пусть вызов функции <math>\operatorname{length}</math> произведён с параметром <math>[a, b, c]</math>. В этом случае начнёт свою работу механизм сопоставления с образцом. Последовательно перебираются все клозы и делаются попытки сопоставления. В данном случае удачное сопоставление будет только во втором клозе (т.&nbsp;к.так как список <math>[a, b, c]</math> не пуст).

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

При написании функций в абстрактной нотации допустимо использовать так называемую охрану, т.&nbsp;е.то есть ограничения на значения переменных образца. Например, при использовании охраны функция <math>\operatorname{length}</math> будет выглядеть примерно следующим образом:

<math>\operatorname{length}(L) = 0\ \mathbf{when}\ L = [\,]</math>

<math>\operatorname{length}(L) = 1 + \operatorname{length}(\operatorname{tail}(L))\ \mathbf{otherwise}</math>

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

<math>\operatorname{append} = \lambda [\,].(\lambda L.L)</math>

<math>\operatorname{append} = \lambda (h:t).(\lambda L.h:\operatorname{append}(t, L))</math>

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

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

<math>\mathbf{let}\ v = f(X)\ \mathbf{in}\ h(v, v)</math>

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

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

<math>\operatorname{Factorial}(0) = 1</math>

<math>\operatorname{Factorial}(N) = N *\cdot \operatorname{Factorial}(N - 1)</math>

<math>\operatorname{Factorial}(3)</math>

<tt>==></tt> <math>3 *\cdot \operatorname{Factorial}(2)</math>

<tt>==></tt> <math>3 *\cdot 2 *\cdot \operatorname{Factorial}(1)</math>

<tt>==></tt> <math>3 *\cdot 2 *\cdot 1 *\cdot \operatorname{Factorial}(0)</math>

<tt>==></tt> <math>3 *\cdot 2 *\cdot 1 *\cdot 1</math>

<tt>==></tt> <math>3 *\cdot 2 *\cdot 1</math>

<tt>==></tt> <math>3 *\cdot 2</math>

<math>Factorial_A\operatorname{Factorial\_A}(N) = F(N, 1)</math>

<math>F(N, A) = F((N - 1), (N *\cdot A))</math>

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

<center><math>f_{i}f_i (p_{ij}) = e_{ij}</math></center>

#<math>e_{ij}</math> — «простое» выражение, т.&nbsp;е.то есть оно не содержит рекурсивных вызовов, а только операции над данными.

#<math>e_{ij}</math> имеет вид <math>f_{k}f_k(v_{k}v_k)</math>, при этом <math>v_{k}v_k</math> — последовательность простых выражений. Это и есть хвостовая рекурсия.

#*<math>\operatorname{ReverseAll}</math> — функция, получающая на вход списочную структуру и обращающая все её элементы, а также её саму.

#*<math>\operatorname{Position}</math> — функция, возвращающая номер первого вхождения заданного атома в список.

#*<math>\operatorname{Set}</math> — функция, возвращающая список из всех атомов, содержащихся в заданном списке. Каждый атом должен присутствовать в результирующем списке в единственном числе.

#*<math>\operatorname{Frequency}</math> — функция, возвращающая список пар (символ, частота). Каждая пара определяет атом из заданного списка и частоту его вхождения в этот список.

##<math>\operatorname{ReverseAll}</math>:

##*<math>\operatorname{ReverseAll}(L) = L\ \mathbf{when}\ \operatorname{atom}(L)</math>

##*<math>\operatorname{ReverseAll} ([\,]) = [\,]</math>

##*<math>\operatorname{ReverseAll}(H:T) = Append\operatorname{append}(\operatorname{ReverseAll}(T), \operatorname{ReverseAll}(H))\ \mathbf{otherwise}</math>

##<math>\operatorname{Position}</math>:

##*<math>\operatorname{Position}(A, L) = Position_N\operatorname{Position\_N}(A, L, 0)</math>

##*<math>Position_N\operatorname{Position\_N}(A, (A:L), N) = N + 1</math>

##*<math>Position_N \operatorname{Position\_N}(A, (B:L), N) = Position_N \operatorname{Position\_N}(A, L, N + 1)</math>

##*<math>Position_N \operatorname{Position\_N}(A, [\,], N) = 0</math>

##<math>\operatorname{Set}</math>:

##*<math>\operatorname{Set}([\,]) = [\,]</math>

##*<math>\operatorname{Set}(H:T) = \operatorname{Include}(H, \operatorname{Set}(T))</math>

##*<math>\operatorname{Include}(A, [\,]) = [A]</math>

##*<math>\operatorname{Include}(A, A:L) = A:L</math>

##*<math>\operatorname{Include}(A, B:L) = \operatorname{prefix}(B, \operatorname{Include}(A, L))</math>

##<math>\operatorname{Frequency}</math>:

##*<math>\operatorname{Frequency}(L) = F([\,], L)</math>

##*<math>F(L, [\,]) = L</math>

##*<math>F(L, H:T) = F(\operatorname{Corrector}(H, L), T)</math>

##*<math>\operatorname{Corrector}(A, [\,]) = [A:1]</math>

##*<math>\operatorname{Corrector}\Big(A, (A:N):T\Big) = \operatorname{prefix}\Big((A:N + 1), T\Big)</math>

##*<math>\operatorname{Corrector}(A, H:T) = \operatorname{prefix}(H, \operatorname{Corrector}(A, T))</math>

##<math>\operatorname{Power\_A}</math>:

##*<math>\operatorname{Power\_A}(X, N) = P(X, N, 1)</math>

##*<math>P(X, N, A) = P(X, N - 1, X *\cdot A)</math>

##<math>\operatorname{Summ\_T\_A}</math>:

##*<math>\operatorname{Summ\_T\_A}(N) = \operatorname{ST}(N, 0)</math>

##*<math>\operatorname{ST}(0, A) = A</math>

##*<math>\operatorname{ST}(N, A) = \operatorname{ST}(N - 1, N + A)</math>

##<math>\operatorname{Summ\_P\_A}</math>:

##*<math>\operatorname{Summ\_P\_A}(N) = \operatorname{SP}(N, 0)</math>

##*<math>\operatorname{SP}(0, A) = A</math>

##*<math>\operatorname{SP}(N, A) = \operatorname{SP}(N - 1, \operatorname{Summ\_T\_A}(N) + A)</math>

##<math>\operatorname{Summ\_Power\_A}</math>:

##*<math>\operatorname{Summ\_Power\_A}(N, P) = \operatorname{SPA}(N, P, 0)</math>

##*<math>\operatorname{SPA}(N, 0, A) = A</math>

##*<math>\operatorname{SPA}(N, P, A) = \operatorname{SPA}\left(N, P - 1, (1 / \frac1{\operatorname{Power\_A}(N, P))} + A\right)</math>

##<math>\operatorname{Exponent\_A}</math>:

##*<math>\operatorname{Exponent\_A}(N, P) = \operatorname{E}(N, P, 0)</math>

##*<math>\operatorname{E}(N, 0, A) = A</math>

##*<math>\operatorname{E}\left(N, P - 1, (\frac{\operatorname{Power\_A}(N, P) / }{\operatorname{Factorial\_A}(P))} + A\right)</math>