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

Как известно, аргументами функций могут быть не только переменные базовых типов, но и другие функции. В этом случае появляется понятие функций высшего порядка. Но для рассмотрения функций высшего порядка необходимо ввести понятие фун­к­ци­о­наль­но­го типа (или тип, возвращаемый функцией). Пусть некоторая функция 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). Т.е. тип таких функций получается последовательным применением символа стрелки ®. Пояснить этот процесс можно на следующем примере:

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

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

Для того чтобы не изощряться с написанием функций типа add5 (как в предыдущем при­мере), была придумана специальная аппликативная форма записи в виде "оператор – опе­ранд". Предпосылкой для этого послужило новое видение на функции в фун­к­ци­о­на­ль­ном программировании. Ведь если традиционно считалось, что выражение f (5) обозначает "при­менение функции f к значению аргумента, равному 5" (т.е. вычисляется только ар­гу­мент), то в функциональном программировании считается, что значение функции также вы­числяется. Так, возвращаясь к примеру 3.1, функцию 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²)

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