globalf5-240972240972 (850810), страница 13
Текст из файла (страница 13)
Нужно их все сцепить в один общий список.(DEFUN list-ap (ll)(COND(ll (append (CAR ll)(list-ap (CDR ll))))))(list-ap '((1 2)(3 (4)))) ; = (1 2 3 (4))Пример 4.11.78Л.В. ГородняяОсновы функционального программированияТогда по аналогии можно построить определение функционала MAPAP:(DEFUN map-ap (fn ll)(COND(ll (append (FUNCALL 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 4 4 6 8 6 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 обладает ещеодним полезным свойством: при таком сцеплении исчезают вхожденияпустых списков в результат. А в Лиспе пустой список используется какложное значение, следовательно, такая схема отображения пригодна дляорганизации фильтров.
Фильтр отличается от обычного отображениятем, что окончательно собирает не все результаты, а лишьудовлетворяющие заданному предикату.Построить список голов непустых списков можно следующим образом:(DEFUN heads (xl) (map-ap#'(LAMBDA (x) (COND (x (CONS (CAR x) NIL)))); временно голова размещается в список,; чтобы потом списки сцепитьxl))(heads '((1 2) () (3 4) () (5 6)) ); = (1 3 5)79Л.В. ГородняяОсновы функционального программированияПример 4.12.Рассмотрим еще один типичный вариант применения функционалов.Представим, что нас интересуют некие интегральные характеристикирезультатов, полученных при отображении, например, суммаполученных чисел, наименьшее или наибольшее из них и т.п.
В такомслучае говорят о свертке результата или его редукции. Редукциязаключается в сведении множества элементов к одному элементу, ввычислении которого задействованы все элементы множества.Подсчитать сумму элементов заданного списка.(DEFUN sum-el ( xl)(COND ((null xl) 0)(xl (+ (CAR xl)(sum-el (CDR xl) )))))(sum-el '(1 2 3 4) ) ; = 10Пример 4.13.Перестроим такое определение, чтобы вместо "+" можно былоиспользовать произвольную бинарную функцию:(DEFUN red-el (fn xl)(COND ((null xl) 0)(xl (FUNCALL fn (CAR xl)(red-el fn (CDR xl) )))))(red-el '+ '(1 2 3 4) ) ; = 10В какой-то мере MAP-AP ведет себя как свертка - она сцепляетрезультаты без сохранения границ между ними.Такие формулы удобны при моделировании множеств, графов иметалингвистических формул, а к их обработке сводится широкий классзадач не только в информатике.Встроенные функционалы (Clisp)80Л.В.
ГородняяОсновы функционального программированияОтображающий функционал можно написать самим, а можно ивоспользоваться одним из встроенных. Согласно стандарту, вреализацию языка Clisp обычно включены функционалы: MAP,MAPCAR, MAPLIST, MAPCAN, MAPCON, MAPC, MAPL [6, 7].Каждый из них покомпонентно обработает любой набор списков.Отличаются они схемами выбора аргументов для отображающейфункции, характером воздействия на исходные данные и оформлениемрезультатов, передаваемых объемлющим формулам.Map( map result-type function sequences ...
)Функция FUNCTION вызывается на всех первых элементахпоследовательностей, затем на всех вторых и т.д. Из полученныхрезультатовFUNCTIONформируетсярезультирующаяпоследовательность, строение которой задается параметром RESULTTYPE с допустимыми значениями CONS, LIST, ARRAY, STRING, NIL.Mapcar( mapcar funct list ... )Функция FUNCTION применяется к первым элементам списков, затемко вторым и т.д. Другими словами, FUNCTION применяется к";головам" методично сокращающихся списков, и результатыприменения собираются в результирующий список.(mapcar #'+ '(1 2 3) '(4 5 6)); = (5 7 9)(mapcar #'list '(1 2 3)'(4 5 6)); = ((1 4)(2 5)(3 6))(DEFUN evlis (args) (mapcar #'EVAL args)); вычисление аргументовПример 4.14.(Без учета ассоциативного списка)(DEFUN evlis (args AL) (mapcar #'(LAMBDA (x)(EVAL x AL)) args))81Л.В. ГородняяОсновы функционального программированияMaplist( maplist function list ...
)Функционал аналогичен MAPCAR, но FUNCTION применяется к"хвостам" списков LIST, начиная с полного списка.(maplist #'list '(1 2 3)'(4 5 6)); = (((1 2 3) (4 5 6)) ((2 3)(5 6)) ((3) (6)))Пример 4.15.Mapc и MaplОба функционала работают как MAPCAR и MAPLIST, соответственно,за исключением того, что они в качестве формального результатавыдают первый список (своеобразная аналогия с формальнымиаргументами).(mapc #'list '(1 2 3)'(4 5 6)) ; = (1 2 3)(mapl #'list '(1 2 3)'(4 5 6)) ; = (1 2 3)Пример 4.16.Mapcan и MapconИ эти два функционала аналогичны MAPCAR и MAPLIST, ноформирование результатов происходит не с помощью операции CONS,которая строит данные в новых блоках памяти, а с помощьюдеструктивной функции NCONC, которая при построении новыхданных использует память исходных данных, из-за чего исходныеданные могут быть искажены.В общем случае, отображающие функционалы представляют собойразличные виды структурной итерации или итерации по структуреданных. При решении сложных задач полезно использоватьотображения и их композиции, а также иметь в виду возможностьсоздания своих функционалов.MAP-INTO отображает результат в конкретную последовательность.82Л.В.
ГородняяОсновы функционального программированияПодведение итоговПоказанные построения достаточно разнообразны, чтобы можно былосформулировать, в чем преимущества применения техникифункционального программирования:отображающие функционалы позволяют строить программы изкрупных действий ;функционалы обеспечивают гибкость отображений ;определение функции может совсем не зависеть от конкретныхимен ;с помощью функционалов можно управлять выбором формырезультатов ;параметром функционала может быть любая функция,преобразующая элементы структуры;функционалы позволяют формировать серии функций от общихданных ;встроенныевClispфункционалыприспособленыкпокомпонентной обработке произвольного числа параметров ;любую систему взаимосвязанных функций можно преобразовать кодной функции, используя вызовы безымянных функций.Для самостоятельного решенияМожно предложить следующие задачи на применение функционалов:1) Напишите определение функционала F-ALL, выясняющего, все лиэлементы множества SET удовлетворяют заданному предикату PRED.(DEFUN f-all (Pred Set ) .
. . )2) Напишите определение функционала F-EX, выясняющего, найдетсяли в множестве SET элемент, удовлетворяющий заданному предикатуPRED.(DEFUN f-ex (Pred Set ) . . . )3) Пусть программа представляет собой набор списков, содержащих имякоманды и произвольное число операндов. Имя расположено первым в83Л.В.
ГородняяОсновы функционального программированиясписке. Напишите определение функционала, удобного для выдачисписка операндов, встречающихся в программе, а также для выдачиотдельных интегральных характеристик, таких как суммарное числовсех операндов, максимальное число операндов в команде и т.п.4) Напишите универсальный фильтр, позволяющий из произвольногосписка выделять при необходимости атомы, числа, строки или списки,начинающиеся с заданного атома, и т.д.5) Пусть клетки доски типа шахматной пронумерованы по горизонталисимволами, а по вертикали числами.
И то, и другое перечислено вотдельных списках по порядку. Напишите функцию перечислениякоординат всех клеток доски, соответствующей размерам списков.6) При анализе труднодоступных данных требуется всю потенциальнополезную информацию выяснять сразу, <в одно касание>. Напишитемодель такого стиля работы на примере покомпонентной обработкидвух списков чисел.
Роль полезной информации могут играть значениялюбых бинарных операций, таких как +, *, -, /, MAX, MIN и т.п.7) Пусть программа представляет собой набор списков, содержащих имякоманды и не более двух операндов. Имя расположено в спискепервым. Напишите определение функционала, удобного для выдачи помере необходимости перечня команд, или перечня первых операндов,или вторых операндов и т.п.Подготовьте определения вспомогательных функций на все эти случаи.8) Список содержит ежедневные сведения о количестве осадков,выпавших за весьма длительный период. Напишите функционал,позволяющий по этому списку оперативно выяснять различныесведения, наподобие:суммарный объем осадков;максимальное количество осадков в день;минимальное количество осадков в день;максимальная разница в количестве осадков в соседние дни.9) Задача повышенной сложности (с решением).84Л.В.
ГородняяОсновы функционального программированияЛексикон ***)Условие задачи: Группа специалистов договорилась подготовитьлексикон программирования для электронной публикации. Былорешено, что надо добиться <правильности> определения понятийпрограммирования, а именно не допускать цепочек понятий прямо иликосвенно определяемых через себя. Кроме того, следует обеспечитьполноту комплекта определений, т.е. всякое включенное в лексиконпонятие должно иметь определение.Напишите программу, помогающую по ходу разработки лексиконаотслеживать его <правильность> и полноту.Входные данные:(( имя_понятия объяснение ) ... ) двухуровневый список, в которомимя_понятия - атом, обозначающийопределяемое понятие,объяснение - последовательность строк и/или атомов,строки не требуют определения,а атомы должны получитьопределения в процессе разработки, но, возможно,еще не все слова удалось объяснить.Выходные данные:Словарь правиленилиЕсть неправильные цепочкиимя_понятия1 ...
имя_понятияN|___________________|______начала неправильных цепочеки/илиЕсть неопределенные понятияимя_понятия1 ... имя понятияN|___________________|_______имена неопределенных понятий(слова перечисляются в порядке включения в словарь.)85Л.В. ГородняяОсновы функционального программированияПример ввода:(( автокод язык_программирования<используется для создания>операционная_система <и> транслятор)( язык_программирования <задается множеством правилдля написания> программ)( операционная_система <комплекс> программа<управляющих решением задач наимеющемся оборудовании>)( транслятор <компилирующая> программа)( программа <описание> алгоритм<решения задачи на соответствующем языке>)( алгоритм <точно определенное правило действий>))Уточнения:Может ли объяснение быть пустым? - Да.Может ли быть много объяснений для одного имени? - Да.Могут ли быть идентичные объяснения? - Да.Может ли одно слово входить в объяснение неоднократно? - Да.Предполагается ли одновременная диагностика и циклов, инеопределенностей? - Да.При выводе результата неопределенные имена надо вывести все.Пример теста:(( а-к яп <используется для создания> ос <и> сп)( яп <задается множеством правил для написания> пр)( ос <комплекс> пр <управляющих решениемзадач на имеющемся оборудовании>)( сп <компилирующая> пр)( пр <описание> алг <решения задачи насоответствующем языке>)( алг <точно определенное правило действий>))'(( а-к яп ос сп) ( яп пр) ( ос пр) ( сп пр) ( пр алг) ( алг ))86Л.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
