Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1156449), страница 11
Текст из файла (страница 11)
Если же Y – неатомарное выражение(точечная пара), его можно рассматривать как бинарное дерево, и сначаларекурсивно выравнивается правое поддерево (полученное операцией cdr),при этом используется параметр Res:(Flat (cdr Y) Res).57Полученный результат (выровненное правое поддерево) используется какнакапливающий параметр для выравнивания левого поддерева(полученного операцией car): (Flat (car Y)(Flat(cdr Y) Res)).Именно такой порядок рекурсивных вызовов функции Flat обеспечиваетсохранение исходного порядка атомов в выровненном списке.В данном случае один рекурсивный вызов стоит внутри другогорекурсивного вызова, демонстрируя ещё один, более сложный видрекурсии – рекурсию более высокого порядка.
Точнее, Flat – это рекурсияпервого порядка, поскольку порядок отсчитывается по числу вложенныхрекурсивных вызовов.Покажем на примере вычисление функции FlattenA :0)1)2)3)(FlattenA: X=((A(B))C))(Flat: Y=((A(B))C), Res=())(Flat: Y=(A(B)), Res=(Flat: Y=(C), Res=()) )(Flat: Y=(A(B)), Res=(Flat: y=C,Res=(Flat: Y=(), Res=())))4) (Flat: Y=(A(B)), Res=(Flat: Y=C, Res=()) )5) (Flat: Y=(A(B)), Res=(C) )6) (Flat: Y=A, Res=(Flat: Y=((B)), Res=(C)) )7) (Flat: Y=A, Res=(Flat: Y=(B),Res=(Flat: Y=(), Res=(C)) ))8) (Flat: Y=A, Res=(Flat: Y=(B), Res=(C)) )9) (Flat: Y=A, Res=(Flat: Y=B,Res=(Flat: y=(), Res=(C))))10) (Flat: Y=A, Res=(Flat: Y=B, Res=(C)) ))11) (Flat: Y=A, Res=(B C))=> (A B C)Заметим, что по окончании обработки очередного подсписка и возврате напредыдущий уровень вложенности списка туда передаётся списокпараметр Res, в котором уже накоплены атомы обработанных подсписков.В отличие от функции Flatten, общее количество обращений коперации cons при работе функции FlattenA минимально, т.е.
равночислу атомов обработанного списочного выражения. При этом дляобработки одного и того же выражения потребовалось меньшее числошагов вычисления (11 против 16) и меньшее количество вложенныхфункциональных вызовов (3 против 5).В качестве ещё одного примера рекурсии более высокого порядкаприведём определение функции Collect, собирающей все различныеатомы в заданном списочном выражении:(collect '(A(S A D)((Z(S))X C))) => (A D Z S X C)58Результирующий список – список атомов без повторений, т.е. множество.Как и в задаче выравнивания списка, Collect используетвспомогательную функцию с накапливающим параметром Res, нодобавление атома в Res происходит только в том случае, когда этогоатома там нет:(defun Collect (X) (Col X nil))(defun Col (Y Res) ;вспомогательная функция(cond ((null Y) Res)((atom Y) (cond ((member Y Res)Res)(T(cons Y Res))))(T (Col (car Y) (Col (cdr Y) Res)) ) ))2.6.
Задачи на программирование рекурсииПростая рекурсия1. Составить функцию (RemoveLast L), удаляющую из спискапоследний элемент. Например:(RemoveLast '(A (S D) E (Q))) => (A (S D) E)2. Определить функцию-предикат (OneLevel L), которая проверяет,является ли список-аргумент одноуровневым списком:(OneLevel '(A B C)) => T,(OneLevel '((A) B C)) => NIL3. Запрограммировать функцию (Bubl N A) с двумя вычисляемымиаргументами – числом N и атомом A.
Функция строит список глубиныN; на самом глубоком уровне элементом списка является A, а налюбом другом уровне список состоит из одного элемента. Например:(Bubl 3 5)=>(((5))).4. Определить функцию (LastAtom L), выбирающую последний отначала списка (невзирая на скобки) атом списка:(LastAtom '(((5)A))) => A5. Составить функцию (Delete L X), удаляющую из списка L на еговерхнем уровнеа) первое вхождение значения Х;б) все вхождения значения Х.6. Написать функцию (Remove2 L), удаляющую из списка каждыйвторой элемент верхнего уровня:(Remove2 '(A B C D E)) => (A C E).7.
Составить функцию(Pair L), которая разбивает элементы списка Lна точечные пары, например:(Pair '(A B C D E)) => ((A . B)(C . D)(E))59Определить функцию(Mix1 L1 L2), которая образует новыйсписок, чередуя элементы заданных:(Mix1 '(A B C) '(Z X)) => (A Z B X C)9. Определить функцию(Mix2 L1 L2), которая образует списокточечных пар элементов, взятых последовательно из заданныхсписков L1 и L2, например:(Mix2 '(A B C) '(Z X))=> ((A . Z)(B . X)(C))10.
Написать функцию (Elem N L), которая выдаёт N-тый элементверхнего уровня списка L. Если длина списка меньше N, то функциявозвращает NIL.11. Составить функцию (Position X L), возвращающую порядковыйномер значения Х в списке L, либо 0, если выражение Х невстречается в списке на верхнем уровне.8.12. Запрограммировать функцию (RevBr L), которая переворачиваетсвой аргумент-список атомов и разбивает его на уровни; количествоуровней равно количеству элементов исходного списка:(RevBr '(A B C)) => (((C) B) A)13.
Определить функцию (RightBr L), которая преобразует свойаргумент – список атомов, разбивая его на уровни. Количествоуровней равно количеству атомов, на самом глубоком уровненаходится последний атом исходного списка:(RightBr '(A B C)) => (A (B (C)))14. Определить функцию (LeftBr L), которая делает преобразованиеисходного списка атомов, подобное RightBr, но на самом глубокомуровне находится первый атом исходного списка:(LeftBr '(A B C)) => (((A) B) C)15. Составить функцию (RightBrOut L), являющуюся обратной кфункции RigthBr: (RightOut '(A(B(C)))) => (A B C)16.
Составить функцию (LeftBrOut L), обратную к функции LeftBr:(LeftOut '(((A)B)C)) => (A B C)17. Написать функцию (Fact N) с одним аргументом – натуральнымчислом N. Функция строит списочное выражение, являющеесязаписью произведения натуральных чисел от 1 до N:(Fact 4)=>(1 * 2 * 3 * 4) или (4 * 3 * 2 * 1).18. Определить функцию (MakeSet L), которая преобразует свойаргумент L – одноуровневый список атомов во множество, исключаяв нём повторяющиеся элементы.6019. Запрограммировать основные операции с множествами: пересечение,объединение, разность множеств.
Множества представляются каксписки атомов без повторений. Составить также функции-предикатыдля проверки равенства множеств и вхождения одного множества вдругое.Параллельная рекурсия и рекурсия высшего порядка1. Определить функцию (Depth L), вычисляющую глубину списка L,т.е. максимальное количество уровней в нём. Например:(Depth '(((A (5) 8) B (K))(G (C)))) => 42. Составить функцию (Subst A L E), заменяющую в произвольномсписочном выражении L на всех его уровнях все вхождения атома Ана выражение Е. Например:(Subst 'Q '(Q (B (Q)) C ((Q) 8))) '(A Z)) =>((A Z) (B ((A Z))) C (((A Z)) 8)))3.
Определить функцию-предикат (OnlyZ L), которая вырабатывает Тв том случае, если в списке L на всех его уровнях встречается толькоатом Z, иначе вырабатывает NIL. Например:(OnlyZ '((Z (Z())Z)()Z) )=> T,(OnlyZ '((Z (Z())8)()Z) )=> NIL.4. Написать функцию (Trans N S), которая упрощает структурусписочного выражения S, заменяя в нём все списочные элементы,находящиеся на уровне N (N>=1), на атом “#”. Например:(Trans 2 '(((A(5)8)B(K))(G(C)))) => ((# B #)(G #))5. Определить функцию(Level N S), которая строит список изэлементов списочного выражения S, находящихся на уровне N(N>=1), например:(Level 2 '(((A (5) 8) B) 7 (G (()))))=> ((A (5) 8) B G (NIL))6.
Составить функцию (Deep S), вырабатывающую атом списочноговыражения S, который находится на наиболее глубоком уровне (еслитаких атомов несколько, выбирается любой). Например:(Deep '(A (B (A)) C ((D) 8))) => A7. Определить функцию (Freq S), которая для каждого атома,входящего в списочное выражение S, вычисляет частоту еговхождения в S и выдает список пар вида: атом – его частота,например:(Freq '(A (B (A)) C ((A) 8)))=> ((A 3)(B 1)(C 1)(8 1))613. ФункционалыФункционалы не усиливают вычислительную мощность языка Лисп,они усиливают его выразительные возможности, позволяя в сжатой формеописать повторяющиеся вычисления [15]. Некоторые задачи оченьестественно решаются с помощью функционалов, приводя к компактным,и в то же время мощным программам.3.1.
Понятие функционалаДо сих пор мы рассматривали лисповские функции, в качествеаргументов которых выступали обрабатываемые данные – атомы исписочные выражения. В языке Лисп данные и функции имеют одинаковоесинтаксическое представление, поэтому в нём достаточно естественнофункция может быть аргументом или результатом вычисления другойфункции.
Последняя при этом называется функционалом, или функциейвысших порядков, а функции, используемые как ее аргументы –функциональными аргументами.Функции высших порядков возникают довольно часто при решенииразных классов задач, к примеру, при вычислении определённогоинтеграла, когда параметрами решаемой задачи являются пределыинтегрирования и подынтегральная функция.Рассмотрим пример определения функционала.
Сначала составимфункцию Аdd1List, работающую с одноуровневым списком чисел иувеличивающую каждое из чисел списка на единицу:(defun Add1List(X)(cond ((null X) NIL)(T (cons (add1 (car X))(Add1List (cdr X))))))Пример работы этой функции:(Add1List '(5 17 0 23)) => (6 18 1 24)Функция Add1List последовательно просматривает исходныйсписок-аргумент и, увеличивая (с помощью функции add1) на 1 каждыйэлемент-число, строит результирующий список. По такой схемерекурсивной обработки элементов верхнего уровня списка можносоставить и другие лисповские функции.
Например, для полученияфункции, уменьшающей на 1 каждое из чисел-элементов исходногосписка, в записи функции Add1List потребуется лишь заменитьфункцию add1 на sub1, уменьшающую свой аргумент на единицу, атакже изменить имя функции, взяв, например, Sub1List вместоAdd1List:62(defun Sub1List (X)(cond ((null X)NIL)(T (cons(sub1 (car X))(Sub1List (cdr X))))))Попробуем определить вместо двух одну, более общую функциюFList, которая применяла бы нужную операцию ко всем элементамисходного списка чисел и составляла бы из полученных значений списокрезультат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
