globalf5-240972240972 (850810), страница 12
Текст из файла (страница 12)
ГородняяОсновы функционального программированиядлины из произвольных символов, включая все что угодно".Список - составное данное, первый элемент которого можетрассматриваться как функция, применяемая к остальным элементам,также представленным как символьные выражения. Это относится и коперациям над числами и строками:(+ 1 2 3 4 5 6) ;= 21(- 12 6 3) ;= 3(/ 3 5) ;= 3/5(1+ 3) ;= 4Большинство операций над числами при префиксной записиестественно рассматривать как мультиоперации от произвольного числааргументов.(string-equal "строка 1" "строка1") ;= Nil(ATOM "a+b-c") ;= T(char "стр1" 4 ) ;= "1"Со строками при необходимости можно работать посимвольно, хотяони рассматриваются как атомы.Любой список можно превратить в константу, поставив перед ним <'>апостроф. Это эквивалентно записи со специальной функцией QUOTE.Для чисел и строк в этом нет необходимости, но это не запрещено.'1 ;= 1'"abc" ;= "abc"Можно строить композиции функций.
Ветвления представлены какрезультат специальной функции COND, использующей отличие от NILв качестве значения "истина". Числа и строки таким образомоказываются допустимыми представлениями значения "истина". Отказот барьера между представлениями функций и значений даетвозможность использовать символьные выражения как дляизображения заданных значений, включая любые структуры надчислами и строками, так и для определения функций, обрабатывающихлюбые данные.
(Напоминаем, что определение функции - данное.)Функционалы - это функции, которые используют в качестве70Л.В. ГородняяОсновы функционального программированияаргументов или результатов другие функции. При построениифункционалов переменные могут играть роль имен функций,определения которых находятся во внешних формулах, использующихфункционалы .Функционалы - общее понятиеРассмотрим технику использования функционалов на упражнениях счислами и покажем, как от простых задач перейти к более сложным.Для каждого числа из заданного списка получить следующее за нимчисло и все результаты собрать в список1)(DEFUN next (xl);; Следующие числа*)(COND; пока список не пуст(x (CONS (1+ (CAR xl)) ; прибавляем 1 к его "голове"(next (CDR xl)) ; и переходим к остальным,) ) ) ); собирая результаты в список(next '(1 2 5)); = (2 3 6)Пример 4.1.Построить список из <голов> элементов списка(DEFUN 1st (xl); "головы" элементов = CAR(COND; пока список не пуст(xl (CONS (caar xl); выбираем CAR от его головы(1st (CDR xl)) ; и переходим к остальным,)))); собирая результаты в список(1st '((один два)(one two)(1 2)) ) ; = (один one 1)Пример 4.2.Выяснить длины элементов списка(DEFUN lens (xl) ; Длины элементов(COND; Пока список не пуст71Л.В.
ГородняяОсновы функционального программирования(xl (CONS (length (CAR xl)); вычисляем длину его головы(lens (CDR xl)); и переходим к остальным,)))); собирая результаты в список(lens '((1 2) () (a b c d) (1(a b c d)3)) ); = (2 0 4 3)Пример 4.3.Внешние отличия в записи этих трех функций малосущественны, чтопозволяет ввести более общую функцию MAP-EL, в определениикоторой имена "CAR", "1+" и "LENGTH" могут быть заданы как значенияпараметра fn:(DEFUN map-el(fn xl); Поэлементное преобразование XL с помощью функции FN(COND; Пока XL не пуст(xl (CONS (FUNCALL fn (car xl)); применяем FN как функцию к голове XL**)(map-el fn (CDR xl)); и переходим к остальным,)))); собирая результаты в списокЭффект функций NEXT, 1ST и LENS можно получить выражениями:(map-el #'1+ xl); Следующие числа:(map-el #'CAR xl); "головы" элементов = CAR(map-el #'length xl) ; Длины элементов(map-el #'1+'(1 2 5)) ; = (2 3 6)(map-el #'CAR'((один два)(one two)(1 2)) ); = (один one 1)(map-el #'length'((1 2)()(a b c d)(1(a b c d)3)) ); = (2 0 4 3) соответственно.Примечание.
#’x – эквивалент ( FUNCTIONпредставлением функции в качестве аргумента.x ), что являетсяВсе три примера можно решить с помощью таких определяющих72Л.В. ГородняяОсновы функционального программированиявыражений:(DEFUN next(xl)(map-el #'1+ xl)) ; Очередные числа:(DEFUN 1st(xl)(map-el #'CAR xl)) ; "головы" элементов = CAR(DEFUN lens(xl)(map-el #'length xl)) ; Длины элементовЭти определения функций формально эквивалентны ранееприведенным - они сохраняют отношение между аргументами ирезультатами.
Параметром функционала может быть любаявспомогательная функция.Пусть дана вспомогательная функция sqw, возводящая числа в квадрат(DEFUN sqw (x)(* x x)) ; Возведение числа в квадрат(sqw 3);=9Пример 4.4.Построить список квадратов чисел, используя функцию sqw:(DEFUN sqware (xl); Возведение списка чисел в квадрат(COND ; Пока аргумент не пуст,(xl (CONS (sqw (CAR xl)); применяем sqw к его голове(sqware(CDR xl)); и переходим к остальным,)))); собирая результаты в список(sqware'(1 2 5 7)); = (1 4 25 49 )Можно использовать map-el:(DEFUN sqware (xl) (map-el #'sqw xl))Ниже приведено определение функции SQWARE- без вспомогательнойфункции, выполняющее умножение непосредственно. Оно влечет засобой двойное вычисление (CAR xl), т.е.
такая техника не вполне73Л.В. ГородняяОсновы функционального программированияэффективна:(DEFUN sqware- (xl)(COND(xl (cons (* (CAR xl) (car xl) ); квадрат "головы" списка; "голову" вычислять приходится дважды(sqware- (CDR xl))))))Пусть дана вспомогательная функция TUPLE, превращающая любоеданное в пару:(DEFUN tuple (x) (CONS x x))(tuple 3) ; = (3 . 3)(tuple 'a) ; = (a . a)(tuple '(Ха)); = ((Ха) .
(Ха)) = ((Ха) Ха); - это одно и то же!Пример 4.5.Чтобы преобразовать элементы списка с помощью такой функции,пишем сразу:(DEFUN duble (xl) (map-el #'tuple xl)); дублирование элементов(duble '(1(a)())) ; = ((1 . 1)((a)a)(()))Немногим сложнее организовать покомпонентную обработку двухсписков.Построить ассоциативный список, т.е. список пар из имен исоответствующих им значений, по заданным спискам имен и ихзначений:(DEFUN pairl (al vl) ; Ассоциативный список(COND; Пока al не пуст,(al (CONS (CONS (CAR al) (CAR vl)); пары из <голов>.74Л.В. ГородняяОсновы функционального программирования(pairl (CDR al) (CDR vl)); Если vl исчерпается,; то CDR будет давать NIL))))(pair '(один два two three) '(1 2 два три)); = ((один . 1)(два . 2)(two . два)(three .
три))Пример 4.6.Определить функцию покомпонентной обработки двух списков спомощью заданной функции FN:(DEFUN map-comp (fn al vl); fn покомпонентно применить; к соотвественным элементам al и vl(COND(al (CONS (FUNCALL fn (CAR al) (CAR vl)); Вызов данного fn как функции(map-comp (CDR al) (CDR vl))))))Пример 4.7.Теперь покомпонентные действия над векторами, представленными спомощью списков, полностью в наших руках. Вот списки и сумм, ипроизведений, и пар, и результатов проверки на совпадение:(map-comp #'+'(1 2 3) '(4 6 9)); = (5 8 12) Суммы(map-comp #'*'(1 2 3) '(4 6 9)); = (4 12 27) Произведения(map-comp #'CONS'(1 2 3) '(4 6 9)); = ((1 . 4) (2 .
6) (3 . 9)) Пары(map-comp #'EQ'(4 2 3) '(4 6 9)); = (T NIL NIL) СравненияДостаточно уяснить, что надо делать с элементами списка, остальноедовершит функционал MAP-COMP, отображающий этот список всписок результатов заданной функции.75Л.В.
ГородняяОсновы функционального программированияДля заданного списка вычислим ряд его атрибутов, а именно - длина,первый элемент, остальные элементы списка без первого.(DEFUN mapf (fl el)(COND ; Пока первый аргумент не пуст,(fl (CONS (FUNCALL (CAR fl) el); применяем очередную функцию; ко второму аргументу(mapf (CDR fl) el); и переходим к остальным функциям,) ) ) ) ; собирая их результаты в общий; список(mapf '(length CAR CDR) '(a b c d)); = (4 a (b c d))Пример 4.8.Композициями таких функционалов можно применять серии функций ксписку общих аргументовилик параллельнозаданнойпоследовательности списков их аргументов. Естественно, и серии, ипоследовательности представляются списками.Безымянные функцииОпределения в примерах 4.4 и 4.5 не вполне удобны по следующимпричинам:в определениях целевых функций DUBLE и SQWARE встречаютсяимена специально определенных вспомогательных функций;формально эти функции независимы, значит, программист долженотвечать за их наличие при использовании целевых функций напротяжении всего жизненного цикла программы, что трудногарантировать;вероятно, имя вспомогательной функции будет использоватьсятолько один раз - в определении целевой функции.С одной стороны, последнее утверждение противоречит пониманиюсмысла именования как техники, обеспечивающей неоднократность76Л.В.
ГородняяОсновы функционального программированияприменения поименованного объекта. С другой стороны, придумыватьподходящие, долго сохраняющие понятность и соответствие цели,имена - задача нетривиальная.Учитывая это, было бы удобнее вспомогательные определениявкладывать непосредственно в определения целевых функций иобходиться при этом вообще без имен. Конструктор функций LAMBDAобеспечивает такой стиль построения определений. Этот конструкторлюбое выражение EXPR превращает в функцию с заданным спискомаргументов (X1. ..
XK) в форме так называемых LAMBDA-выражений:(LAMBDA (x1 ... xK) expr)Имени такая функций не имеет, поэтому может быть применена лишьнепосредственно. DEFUN использует данный конструктор, но требуетдать функциям имена.Определение функций DUBLE и SQWARE из примеров 4.4 и 4.5 безиспользования имен и вспомогательных функций:(DEFUN sqware (xl)(map-el #' (LAMBDA (x) (* x x)) xl))(DEFUN duble (xl)(map-el #' (LAMBDA (x) (CONS x x)) xl))Пример 4.9.Любую систему взаимосвязанных функций можно преобразовать кодной функции, используя вызовы безымянных функций.Композиции функционалов, фильтры, редукцииВызовы функционалов можно объединять в более сложные структурытаким же образом, как и вызовы обычных функций, а их композицииможно использовать в определениях новых функций.
Композициифункционалов позволяют создавать и более мощные построения,достаточно ясные, но требующие некоторого внимания.Декартово произведение хочется получить определением вида:77Л.В. ГородняяОсновы функционального программирования(DEFUN decart (x y)(map-el #' (lambda (i)(map-el #' (lambda (j) (list i j)) y)) x) )Пример 4.10.Но результат вызова(decart '(a s d) '( e r t))дает(((A E) (A R) (A T)) ((S E) (S R) (S T)) ((D E) (D R) (D T)))вместо ожидаемого((A E) (A R) (A T) (S E) (S R) (S T) (D E) (D R) (D T))Дело в том, что функционал MAP-EL, как и MAP-COMP (пример 4.7),собирает результаты отображающей функции в общий список спомощью операции CONS так, что каждый результат функции образуетотдельный элемент.А по смыслу задачи требуется, чтобы список был одноуровневым.Посмотрим, что получится, если вместо CONS при сборе результатоввоспользоваться функцией APPEND.Пусть дан список списков.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
