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

printФункции высших порядков и /\-выражения

Рассмотрим функцию `"увел"1`, увеличивающую значения всех элементов числового списка на 1, и функцию `"ост"2`, вычисляющую остаток от деления на 2 для всех элементов списка.
`"увел"1(x)=bb"если"\ "null"(x)\ bb"то"\ '()\ bb"иначе"\ "cons"("car"(x)+1,"увел"1("cdr"(x)));`
`"ост"2(x)=bb"если"\ "null"(x)\ bb"то"\ '()\ bb"иначе"\ "cons"("car"(x)\ mod\ 2,"ост"2("cdr"(x)));`
Эти определения очень схожи. Можно определить функцию высшего порядка, которая применяет некоторую функцию ко всем элементам списка.
`"отобр"(x,f)=bb"если"\ "null"(x)\ bb"то"\ '()\ bb"иначе"\ "cons"(f("car"(x)),"отобр"("cdr"(x),f));`
Функции `"увел"1` и `"ост"2` можно определить, используя функцию `"отобр"`:
`"ув"1(z)=z+1;`
`"увел"1(x)="отобр"(x,"ув"1);`
`"ос"2(z)=z\ mod\ 2;`
`"ост"2(x)="отобр"(x,"ос"2)`
Также полезна для обработки списков следующая функция высшего порядка:
`"редукция"(x,f,a)=bb"если"\ "null"(x)\ bb"то"\ a\ bb"иначе"\ f("car"(x),"редукция"("cdr"(x),f,a))`
С помощью функции редукция можно легко определить функцию для вычисления суммы элементов списка.
`"плюс"(a,b)=a+b;`
`"сумма"(x)="редукция"(x,"плюс",0)`
Определение функции суммпроиз также упрощается:
`"накопить"(h,z)="список"2(h+"car"(z),h*"cadr"(z));`
`"суммпроиз"(x)="редукция"(x,"накопить","список"2(0,1))`
Можно избавиться от вспомогательных функций, если воспользоваться другим способом определения функции. До сих пор мы вводили функцию с помощью определений вида `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` и сумма следующим образом:
`"увел"1(x)="отобр"(x,\ λ(z)\ z+1);`
`"сумма"(x)="редукция"(x,\ λ(y,z)\ y+z,0)`
`λ`-выражение обозначает одно и тоже функциональное значение, независимо от имен, выбранных для его параметров. Выражения `λ(z)\ z+1` и `λ(x)\ x+1` обозначают одно и то же и являются взаимозаменяемыми, например, можно определить функцию `"увел"1(x)="отобр"(x,\ λ(x)\ x+1)`.
`λ`-выражения можно использовать и в блоках локальных определений "пусть" и "где", определяя локальные функции:
`"расст"(x,y)={"квадрат"(x)+"квадрат"(y)\ bb"где"\ "квадрат"=λ(x)\ x*x}`
Когда локальное определение вводит рекурсивную функцию, будем использовать модифицированные формы для блоков локальных определений `{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. Можно использовать формы "пустьрек" и "гдерек" для определения функций, чтобы вспомогательные функции были скрыты внутри выражения, а не определялись глобально.
`"суммпроиз"(x)={"сп"(x,0,1)`
              `bb"гдерек"\ "сп"=λ(x,s,p)`
                           `bb"если"\ "null"(x)\ bb"то"\ "список"2(s,p)`
                           `bb"иначе"\ "сп"("cdr"(x),s+"car"(x),p*"car"(x))}`
Наконец, рассмотрим функцию высшего порядка другого типа `"ув"(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.
loading