Функциональное программирование

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

Пусть `Z` – множество целых чисел, тогда функция `f(x)=x+1` имеет тип `Z\ ->\ Z`. Функция двух аргументов `g(x,y)=x+y` имеет тип `Z\ times\ Z\ ->\ Z`. Вообще функция `f(x_1,x_2,…,x_n)` имеет тип `X_1\ times\ X_2\ times\ …\ times\ X_n\ ->\ Y`, если ее аргумент `x_1` имеет тип `X_1`, аргумент `x_2` – тип `X_2` и т.д., а ее результат имеет тип Y.

Рассмотрим функцию `h(x,f)\ =\ x+f(x)`, которая имеет в качестве аргументов число и функцию, а возвращает число. Тип аргумента `x` есть `Z`, тип аргумента `f` – `Z\ ->\ Z`, а тип результата – `Z`. Тогда функция `h` имеет тип `Z\ times\ (Z->Z)\ ->\ Z`.

Функция `"дважды"(f)\ =\ lambda(x)f(f(x))` имеет тип `(Z->Z)->(Z->Z)`, так как, если `x` имеет тип `Z`, и f имеет тип `Z->Z`, то `f(f(x))` имеет тип `Z`, а `lambda(x)f(f(x))` имеет тип `Z->Z`. В принципе функция `"дважды"` не зависит от типа аргумента `x`, и можно сказать, что дважды имеет тип `(X->X)->(X->X)` при любом `X`. Так как `X` можно положить равным `Y->Y`, функцию дважды можно использовать в качестве аргумента: `"четырежды"="дважды"("дважды")`. Более простое определение функции `"дважды"(f,x)=f(f(x))` не позволило бы определить функцию четырежды через композицию функций дважды.

Обозначим через `"список"(X)` тип, значение которого есть либо пустой список, либо список значений типа `X`. Тогда основные функции для работы со списком имеют следующий тип:

Функции `"car"` и `"cdr"` являются частичными, так как не определены для пустого списка.

Рассмотрим определение функции `"отобр"`.

Если `x` имеет тип `"список"(X)`, а `f` – `X->Y`, то `"car"(x)` имеет тип `X`, `f("car"(x))` имеет тип `Y`, a `"cons"(f("car"(x)),"отобр"("cdr"(x),f))` – `"список"(Y)`. Таким образом, функция `"отобр"` имеет тип `"список"(X)\ times\ (X->Y)\ ->\ "список"(Y)`. Формальный алгоритм вывода типа можно найти в главе 7 книги Филд А., Харрисон П. "Функциональное программирование".

Определим функцию `"отобр"` другим способом.

В этом случае функция `"отобр"` имеет тип `(X->Y)\ ->\ ("список"(X)->"список"(Y))`. Выражение `"отобр"(f)` имеет тип `"список"(X)->"список"(Y)`. Полагая `X'="список"(X)` и `Y'="список"(Y)`, получаем, что вызов `"отобр"("отобр"(f))` возвращает значение типа `"список"("список"(X))\ ->\ "список"("список"(Y))`, то есть функцию, применяющую функцию `f` ко всем элементам списка из списков значений типа `X`.

Если положить `X'=\ X->Y` и `Y'="список"(X)->"список"(Y)`, то выражение `"отобр"("отобр")` имеет тип `"список"(X->Y)\ ->\ "список"("список"(X)->"список"(Y))`, что означает функцию, которая требует в качестве аргумента список функций типа `X->Y` и возвращает в качестве результата список функций типа `"список"(X)->"список"(Y)`. Для примера использования потребуются следующие определения:

Значение `"добавки"` – это список функций, увеличивающих значение своего аргумента на 1, 2 или 3. Функция каждая имеет тип `"список"(X->Y)\ ->\ (X->"список"(Y))` и возвращает функцию, которая применяет каждую функцию из списка к своему аргументу, получая список результатов. Например, выражение `("каждая"("добавки"))(1)` возвращает список `(2\ 3\ 4)`. Функция каждая позволяет применить список функций, полученный вызовом `"отобр"("отобр")`. Выражение `("каждая"(("отобр"("отобр"))("добавки")))('(0\ 5\ 10))` вернет список `((1\ 6\ 11)\ (2\ 8\ 12)\ (3\ 9\ 13))`.

Функции высших порядков упрощают написание сложных программ. Рассмотрим следующее описание грамматики:

Пусть для распознавания терминальных символов грамматики имеются функции `"согл"` и `"глас"` типа `"список"(A)->\ B`, где `A` – множество букв, а `B` – множество булевых значений. Функции `"согл"` и `"глас"` проверяют первый элемент списка на принадлежность к классу гласных или согласных. Для определения грамматики на функциональном языке будем использовать следующие функции высшего порядка:

Функция `"части"` делит список на две части таким образом, чтобы одна из них удовлетворяла предикату `p`, а другая – предикату `q`. При использовании этих функций определение на функциональном языке почти один к одному повторяет грамматические правила:

Бэкус показал, что, задав несколько элементарных функционалов (функций высшего порядка, например, `"комп"(f,g)=lambda(x)\ f(g(x))`), можно построить все другие функции без использования переменных.

1. По аналогии с функцией `"отобр"`, дайте альтернативное определение для функции `"редукция"(f,a)`. Определите ее тип.

2. Определите тип выражений `"отобр"("редукция"(f,a))` и `"редукция"("редукция",’())`