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

Рассмотрим функцию `"увел"1`, увеличивающую значения всех элементов числового списка на 1, и функцию `"ост"2`, вычисляющую остаток от деления на 2 для всех элементов списка.

Эти определения очень схожи. Можно определить функцию высшего порядка, которая применяет некоторую функцию ко всем элементам списка.

Функции `"увел"1` и `"ост"2` можно определить, используя функцию `"отобр"`:

Также полезна для обработки списков следующая функция высшего порядка:

С помощью функции редукция можно легко определить функцию для вычисления суммы элементов списка.

Определение функции суммпроиз также упрощается:

Можно избавиться от вспомогательных функций, если воспользоваться другим способом определения функции. До сих пор мы вводили функцию с помощью определений вида `f(x_1,\ x_2,\ …,\ x_n)=e`, где `f` – имя определяемой функции, `x_1,\ x_2,\ …,\ x_n` - ее параметры, `e` – определяющее функцию выражение. Имя `f` является глобальным, то есть может использоваться для определения других функций, а имена параметров `x_1,\ x_2,\ …,\ x_n` являются локальными, то есть могут использоваться только в выражении `e`. Функция является правилом для вычисления значения по некоторым аргументам. Определение, приведенное выше, связывает с именем `f` некоторое значение, заключающее в себе это правило. Это значение является `lambda`-выражением `lambda(x_1,\ x_2,\ …,\ x_n)\ e`. `lambda`-выражение выделяет имена параметров `x_1,\ x_2,\ …,\ x_n` и выражение для вычисления значения, использующее эти параметры. Например, `lambda(z)\ z+1` определяет функцию увеличения значения на 1. Используя `λ`-выражение, можно определить функции `"увел"1` и сумма следующим образом:

`λ`-выражение обозначает одно и тоже функциональное значение, независимо от имен, выбранных для его параметров. Выражения `λ(z)\ z+1` и `λ(x)\ x+1` обозначают одно и то же и являются взаимозаменяемыми, например, можно определить функцию `"увел"1(x)="отобр"(x,\ λ(x)\ x+1)`.

`λ`-выражения можно использовать и в блоках локальных определений "пусть" и "где", определяя локальные функции:

Когда локальное определение вводит рекурсивную функцию, будем использовать модифицированные формы для блоков локальных определений `{bb"пустьрек"\ x_1=e_1;\ x_2=e_2;\ …;\ x_k=e_k\ в\ e}` и `{e\ bb"гдерек"\ x_1=e_1;\ x_2=e_2;\ …;\ x_k=e_k}`. Разница заключается в области действия имен. В формах "пусть" и "где" имена `x_1,\ x_2,\ …,\ x_k` со значениями `e_1,\ e_2,\ …,\ e_k` доступны только в определяемом выражении `e`. В случае форм "пустьрек" и "гдерек" имена `x_1,\ x_2,\ …,\ x_k` можно использовать не только в выражении `e`, но и в выражениях `e_1,\ e_2,\ …,\ e_k`. Обычно каждое из выражений `e_1,\ e_2,\ …,\ "ek"` является `λ`-выражением, что позволяет вызывать в любом из выражений любую из функций `x_1,\ x_2,\ …,\ x_k`.

Хотя формы "пустьрек" и "гдерек" обобщают формы "пусть" и "где", их область применения ограничена. Например, выражение `{{x\ bb"гдерек"\ x=x+1}\ bb"где"\ x=0}` бессмысленно, тогда как значение выражения `{{x\ bb"где"\ x=x+1}\ bb"где"\ x=0}` равно 1. Можно использовать формы "пустьрек" и "гдерек" для определения функций, чтобы вспомогательные функции были скрыты внутри выражения, а не определялись глобально.

Наконец, рассмотрим функцию высшего порядка другого типа `"ув"(n)=λ(z)\ z+n`, которая возвращает функцию в качестве результата. Ее можно использовать при определении функции `"увел"1(x)="отобр"(x,"ув"(1))`.

В функции ув используется `λ`-выражение с переменной n, которая не является параметром `λ`-выражения. Эта переменная является свободной переменной данной функции. В функциональном программировании значение свободной переменной определяется во время определения функции, а не во время ее вызова. Такой способ вычисления `λ`-выражения называется простым или статическим связыванием. Например, вычисление выражения `{bb"пусть"\ n=1\ в\ {bb"пусть"\ f=λ(z)\ z+n\ в\ {bb"пусть"\ n=2\ в\ f(3)}}}` дает 4.

Функция высшего порядка `"комп"(f,g)=λ(x)\ f(g(x))` имеет функции и в качестве аргументов, и в качестве результата. Эта функция позволяет определить функцию через композицию других функций. Например, функция `"увобр"="комп"("увел"1,"обратить")` сначала обращает список, а затем увеличивает его элементы на 1.

1. Пусть функция `f` является функцией принадлежности к множеству `X`, то есть `f(x)=bb"если"\ x\ ∈\ X\ bb"то"\ #T\ bb"иначе"\ #F`. Определите функцию `"добавить"(z,f)`, которая возвращает функцию принадлежности для множества `X'=\ X\ ∪\ {z}`.

2. Используя функцию `"отобр"`, определите функцию, вычисляющую декартово произведение двух множеств. Например, вызов `"декарт"`('(1 2 3),'(4 5)) возвращает список ((1 4) (1 5) (2 4) (2 5) (3 4) (3 5)).

3. Определите функцию `"обход"(f,x)`, которая аналогична функции `"отобр"`, но применяет функцию `f` не к голове, а к хвосту списка, начиная с исходного списка `x`.

4. Определите функцию `"каждый"(f,s)`, проверяющую, что каждый элемент списка `s` удовлетворяет функции-предикату `f`. Например, вызов `"каждый"`(`"atom"`,'(A B C)) возвращает #T, а `"каждый"`(`"atom"`,'(A (B C))) возвращает #F.

5. Определите функцию `"удалитьеслине"(f,s)`, возвращающую новый список из элементов списка `s`, удовлетворяющих функции-предикату `f`. Например, вызов `"удалитьеслине"`(`"atom"`, '(A (B C) D)) возвращает (A D).

6. Определите функцию `"проверить"(f,x,y)`, которая определяет степень соответствия аппроксимирующей функции `f` данным, заданным в списках `x` и `y`, вычисляя `sqrt(sum((f(x_i)-y_i)^2))`

7. Определите функцию `"применить"(f,x)`, которая возвращает список из результатов применения функции `f_i` из списка функций `f` к соответствующему элементу `x_i` из списка `x`: `(f_1(x_1)\ …\ f_k(x_k))`.

8. Определите функцию `"существует"(f,s)`, проверяющую, что существует элемент списка `s`, удовлетворяющий функции-предикату `f`. Например, вызов `"существует"`(`"atom"`, '((A B) C)) дает #T.