Е.И. Большакова, Н.В. Груздева - Основы программирования на языке Лисп (1110798), страница 12
Текст из файла (страница 12)
Определить функцию (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, которая применяла бы нужную операцию ко всем элементамисходного списка чисел и составляла бы из полученных значений списокрезультат. Эта функция будет иметь два аргумента – применяемуюоперацию F и исходный список X, т.е.
будет функционалом. ОпределимFList как обычную функцию с вычисляемыми аргументами, поэтому приее вызове с нужными нам операциями последние должны квотироваться:(FList 'add1 X) и (FList 'sub1 X). Эти два функциональныхвызова должны быть эквивалентны соответственно вызовам функций(Аdd1List X) и (Sub1List X), в частности:(FList 'add1 '(5 17 0 3)) => (6 18 1 4)(FList 'sub1 '(5 17 0 3)) => (4 16 -1 2)Кажущееся очевидным определение FList, получающееся из Add1Listзаменой конкретной операции на формальный параметр F:(defun FList (F X)(cond ((null X) NIL)(T (cons (F (car X)) (FList F (cdr X))))))всё же неверно, и в этом легко убедиться, попробовав вычислить(FList 'add1 X) или (FList 'sub1 X).Причинаошибкисвязанасособенностьювычисленийфункциональных вызовов в языке Лисп. Любой вычислимый в Лиспесписок должен иметь в качестве своего первого элемента либо символьныйатом – имя функции (встроенной или уже определённой), либо лямбдавыражение, определяющее некоторую безымянную функцию.
Инымисловами, первый элемент вычисляемого списка (функционального вызова)никогда не вычисляется, он должен быть задан явно. В случае, когдапервый элемент – это атом (имя функции), лисп-интерпретатор используетсвязанное с этим символьным атомом определяющее выражение функции.Поэтому при вычислении тела функции FList, точнее, привычислении выражения (F (car X)) символ F будет трактоваться какимя функции, а такая функция не была определена. Чтобы исправитьошибку, необходимо при вычислении этого выражения использоватьвместо символа F его значение как фактического параметра.
Применяявстроенную функцию eval, это можно сделать, например, так:(defun FList (F X)(cond ((null X) NIL)63(T (cons (eval (list F (list 'quote (car X))))(FList F (cdr X))))))При вычислении первого аргумента функции cons сначала формируетсясписок-обращение к нужной функции F (за счёт первого вычисленияфункцией eval своего аргумента), а затем сформированное обращениевычисляется (за счёт второго вычисления функцией eval своегоаргумента).
Чтобы при этом аргумент функции F не вычислялся дважды, входе первого этапа вычислений строится форма для его последующегоквотирования:(list 'quote(car X)) => (quote первый_элемент_X)).Функции add1 и sub1 являются встроенными в диалекте MuLisp,но их нет в Common Lisp. Однако и в этом диалекте легко применитьсозданный функционал, используя вместо имени функции еёопределяющее выражение:(FList '(lambda(x)(+ x 1)) '(5 17 0 3)) => (6 18 1 4)(FList '(lambda(x)(- x 1)) '(5 17 0 3)) =>(4 16 -1 2)При вычислении первого аргумента этих вызовов будет получено лямбдавыражение, которое будет использовано в теле функционала FListвместо формального параметра F.Таким образом, функциональный аргумент функционала FListвычисляется, и его значением должно быть либо имя функции от одногоаргумента (вычисляемого), либо её определяющее выражение:(FList 'list '(5 17 0 3)) => ((5)(17)(0)(3))(FList '(lambda(X)(cons X NIL)) '(5 17 0 3))=> ((5)(17)(0)(3))Рассмотренная нами функция FList встроена во многие диалектыЛиспа (в том числе – в MuLisp и Common Lisp) под именем mapcar.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
