Учебник по Lisp (Материалы к экзамену и коллоквиумам 2013-го года), страница 9

список пар из имен исоответствующих им значений, по заданным спискам имен и их значений:(defun pairl (al vl); Ассоциативный список(cond; Пока AL не пуст,(al (cons (cons (car al) (car vl)); пары из “голов”.(pairl (cdr al) (cdr vl)) ; Если VL исчерпается,7; то CDR будет давать NIL))))(pair '(один два two three) '(1 2 два три)); = ((один .

1)(два . 2)(two два )(three три ))Пример 7. Определить функцию покомпонентной обработки двух списков с помощьюзаданной функции fn:(defun map-comp (fn al vl)); fn покомпонентно применить; к соотвественным элементам AL и VL(cond(xl (cons (fn (car al) (car vl)); Вызов данного FN как функции(map-comp (cdr al) (cdr vl))) ))Теперь покомпонентные действия над векторами, представленными спомощью списков, полностью в наших руках. Вот списки и сумм, ипроизведений, и пар, и результатов проверки на совпадение:(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.Пример 8. Для заданного списка вычислим ряд его атрибутов, а именно - длина, первыйэлемент, остальные элементы списка без первого.(defun mapf (fl el)(cond; Пока первый аргумент не пуст,(fl (cons ((car fl) el ); применяем очередную функцию; ко второму аргументу(mapf (cdr fl) el); и переходим к остальным функциям,)) )); собирая их результаты в общий список(mapf '(length car cdr) '(a b c d )); = (4 a (b c d ))Композициями таких функционалов можно применять серии функций к списку общихаргументов или к параллельно заданной последовательности списков их аргументов.Естественно, и серии, и последовательности представляются списками.8Безымянные функцииОпределения в примерах 4 и 5 не вполне удобны по следующим причинам:9 В определениях целевых функций duble и sqwure встречаются имена специальноопределенных вспомогательных функций.9 Формально эти функции независимы, значит программист должен отвечать за ихналичие при использовании целевых функций на протяжении всего жизненного циклапрограммы, что трудно гарантировать.9 Вероятно, имя вспомогательной функции будет использоваться ровно один раз - вопределении целевой функции.С одной стороны последнее противоречит пониманию смысла именования как техники,обеспечивающей неоднократность применения поименованного объекта.

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

Конструкторфункцийlambda обеспечивает такой стиль построения определений. Этот конструктор любоевыражение expr превращает в функцию с заданным списком аргументов (x1 ... xK) в форметак называемых lambda-выражений:( lambda (x1 ... xK) expr )Имени такая функций не имеет, поэтому может быть применена лишь непосредственно.Defun использует этот конструктор, но, кроме того, дает функциям имена.Пример 9. Определение функций duble и sqwure из примеров 4 и 5без использования имен и вспомогательных функций:(defun sqware (xl) (map-el(defun duble (xl) (map-el(lambda (x) (* x x)) xl))(lambda (x) (cons x x)) xl))Любую систему взаимосвязанных функций можно преобразовать к одной функции,используя вызовы безымянных функций.Композиции функционалов, фильтры, редукцииВызовы функционалов можно объединять в более сложные структуры таким же образом, каки вызовы обычных функций, а их композиции можно использовать в определениях новыхфункций.9Композиции функционалов позволяют порождать и более мощные построения, достаточноясные, но требующие некоторого внимания.Пример 10.

Декартово произведение хочется получить определением вида:(defun decart (x y)(map-el #'(lambda (i))(map-el #'(lambda (j) (list i j))y)x) )Но результат вызова(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 (пример 7), собирает результатыотображающей функции в общий список с помощью операции cons так, что каждыйрезультат функции образует отдельный элемент.А по смыслу задачи требуется, чтобы список был одноуровневым.Посмотрим, что получится, если вместо cons при сборе результатов воспользоватьсяфункцией append.Пример 11.

Пусть дан список списков. Нужно их все сцепить в один общий список.(defun list-ap (ll)(cond(ll (append (car ll)(list-ap (cdr ll) ))) ))(list-ap '((1 2)(3 (4)))); = (1 2 3 (4))Тогда по аналогии можно построить определение фукнционала map-ap:10(defun map-ap (fn ll)(cond(ll (append (fn (car ll) )(map-ap fn (cdr ll) ))) ))(map-ap 'cdr'((1 2 3 4) (2 4 6 8) ( 3 6 9 12))); = (2 3 44 6 86 9 12)Следовательно, интересующая нас форма результата может быть получена:(defun decart (x y)(map-ap #'(lambda (i)(map-el #'(lambda (j) (list i j))y))x))(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))Соединение результатов отображения с помощью append обладает еще одним полезнымсвойством: при таком сцеплении исчезают вхождения пустых списков в результат.

А в Лиспепустой список используется как ложное значение, следовательно такая схема отображенияпригодна для организации фильтров. Фильтр отличается от обычного отображения тем, чтоокончательно собирает не все результаты, а лишь удовлетворяющие заданному предикату.Пример 12. Построить список голов непустых списков можно следующим образом:(defun heads (xl) (map-ap#'(lambda (x)(cond (x (cons (car x) NIL)))); временно голова размещается в список,; чтобы потом списки сцепитьxl))(heads '((1 2) () (3 4) () (5 6)) ); = (1 3 5)Рассмотрим еще один типичный вариант применения функционалов.

Представим, что насинтересуют некие интегральные характеристики результатов, полученных при отображении,например, сумма полученных чисел, наименьшее или наибольшее из них и т.п. В такомслучае говорят о свертке результата или его редукции. Редукция заключается в сведениимножества элементов к одному элементу, в вычислении которого задействованы всеэлементы множества.Пример 13. Подсчитать сумму элементов заданного списка.(defun sum-el ( xl)(cond ((null xl) 0)(xl (+ (car xl)11(sum-el (cdr xl) )))))(sum-el '(1 2 3 4 ) ); = 10Перестроим определение, чтобы вместо "+" можно было использовать произвольнуюбинарную функцию:(defun red-el (fn xl)(cond ((null xl) 0)(xl (fn (car xl)(red-el fn (cdr xl) )(red-el '+ '(1 2 3 4 ) ))))); = 10В какой-то мере map-ap ведет себя как свертка - она сцепляет результаты без сохраненияграниц между ними.Такие формулы удобны при моделировании множеств, графов и металингвистическихформул, а к их обработке сводится широкий класс задач не только в информатике.Выводы:- Отображающие функционалы позволяют строить программы из крупных действий.- Функционалы обеспечивают гибкость отображений.- Определение функции может совсем не зависить от конкретных имен.- С помощью функционалов можно управлять выбором формы результатов.- Параметром функционала может быть любая функция, преобразующая элементыструктуры.- Функционалы позволяют формировать серии функций от общих данных.- Встроенные в Clisp функционалы приспособлены к покомпонентной обработкепроизвольного числа параметров.- Любую систему взаимосвязанных функций можно преобразовать к одной функции,используя вызовы безымянных функций.127.

Имена и контексты-Определения функций. Псевдо-функции.Именование значений и подвыраженийПеременные и константы.Функции и данные.Реализация языка программирования всегда сопровождается некоторым уточнением границ,в которых применяются общеизвестные понятия. Цель уточнения - удобствопрограммирования и повышение эффективности программ. Рассмотрим отдельные решения,уточненные при реализации ряда Лисп-систем, на небольшом примере моделированияработы с множествами.Задача: Пусть множества представлены с помощью списков. Для начала рассмотрим простыемножества, элементами которых могут быть только атомы. Надо реализовать объединение(UNION) и пересечение (INTERSECTION) множеств.Предварительный анализ задачи:Функции UNION и INTERSECTION применяют к множествам, каждое множествопредставлено в виде списка атомов.

Заметим, что обе функции рекурсивны и используютвспомогательную функцию, выясняющую входит ли атом в список (MEMBER).Работу этих функций можно выразить следующим образом:MEMBER – это функция двух аргументов, первый аргумент “А” - атом, а второй аргумент –список “Х”. Функция вырабатывает значение “Т”, если “А” входит в список “Х”.Алгоритм:Определение тела функции состоит из трех ветвей:- Если второй аргумент – пустой список,то значение функции Nil, т.е. атом в списке не найден.- Иначе если атом “А” совпадает с “головой” второго аргумента,то значение функции T, т.е. атом имеется в списке.- Иначе продолжаем поиск в “хвосте” списке, т.е.

рекурсивно применяем исходнуюфункцию к редуцированному второму аргументу.алг member ( атом a, список x) арг a, xначесли пусто (a)то знач := Nilинес равно (a, голова (x) )то знач := Tиначе знач := member (a, хвост (x))кон13UNION – это функция двух аргументов, оба аргумента “X” и “Y” - списки, представляющиемножества. Функция вырабатывает новый список, в который входят все атомы из списков“Х” и “Y”.Алгоритм:Определение тела функции состоит из трех ветвей:- Если первый аргумент – пустой список,то значением является второй аргумент, т.е.

можно ничего не строить.- Иначе если “голова” первого аргумента входит во второй аргумент,то достаточно объединить хвост первого аргумента со вторым аргументом, т.е.рекурсивно применяем исходную функцию, редуцируя первый аргумент.- Иначе “голову” первого аргумента присоединяем к результату объединенияредуцированного первого аргумента со вторым аргументом.алг UNION (список x,y) арг x, yначесли пусто (x)то знач := yинес member ( голова (x), y )то знач := UNION (хвост (x), y)иначе знач := cons (голова (x), UNION (хвост (x), y))конINTERSECTION – это функция двух аргументов, оба аргумента “X” и “Y” - списки,представляющие множества. Функция вырабатывает новый список, в который входят атомысписка “Х”, входящие в список “Y”.Алгоритм:Определение тела функции состоит из трех ветвей:- Если первый аргумент – пустой список,то и пересечение - пустой список.- Иначе если “голова” первого аргумента входит во второй аргумент,то “голову” первого аргумента присоединяем к результату пересечения редуцированногопервого аргумента со вторым аргументом.- Иначе применяем пересечение к редуцированному первому аргументу со вторымаргументом.алг INTERSECTION (список x,y) арг x, yначесли пусто (x)то знач := Nilинес member ( голова (x), y )то знач := cons (голова (x), INTERSECTION (хвост (x),y))иначе знач := INTERSECTION (хвост (x), y)кон14Определяя эти функции на Лиспе, мы используем специальную псевдо-функциюDEFUN.