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

Примеры

Пример 5. Операция prefix.

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

1°. prefix (a₁, a₂) = a₁: a₂ (при этом результат не является элементом List_str (A)).

2°. prefix (a₁, [b₁, b₂]) = [a₁, b₁, b₂]

3°. prefix ([a₁, a₂], [b₁, b₂]) = [[a₁, a₂], b₁, b₂]

Пример 6. Функция определения длины списка Length.

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

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

Length ([]) = 0

Length (L) = 1 + Length (tail (L))

Пример 7. Функция слияния двух списков Append.

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

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

Append ([], L₂) = L₂

Append (L₁, L₂) = prefix (head (L₁), Append (tail (L₁), L₂))

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

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

#(f): A ® B

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

Например: #(sin): Real ® Real

#(Length): List (A) ® Integer

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

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

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

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

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

Таким образом, если функция f имеет тип A₁ ® (A₂ ® (... (A_n ® B)...)), то чтобы полностью вычислить значение f (a₁, a₂,..., a_n) необходимо последовательно провести вычисление (... (f (a₁) a₂)...) a_n. И результатом вычисления будет объект типа B.

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

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

f (x) = x² + 5 Û lx.(x² + 5)

f (x, y) = x + y Û ly.lx.(x + y)

f (x, y, z) = x² + y² + z² Û lz.ly.lx.(x² + y² + z²)

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

Дата добавления: 2014-01-07