На этом шаге мы приведем задачи на обработку списков.
Пример 1. Функция, определяющая, равны ли первый и последний элементы списка L, состоящего из атомов.
Решение:
(DEFUN RAWN (LAMBDA (L)
(COND ( (NULL L) NIL )
( (EQ (LENGTH L) 1) NIL )
( T (COND ( (EQ (CAR L) (LAST (CDR L))) T )
( T NIL )
)
)
)
))
;-------------------- ;
(DEFUN LAST (LAMBDA (L)
(COND ( (NULL L) NIL )
( (NULL (CDR L)) (CAR L) )
( T (LAST (CDR L)) )
)
))
Тестовые примеры:
$ (RAWN '(1 2 3)) NIL $ (RAWN '(1 2 3 4 5 1)) T $ (RAWN '((1) 2 3 4 5 (1))) T
Заметим, что приведенное решение является неоптимальным. Постарайтесь улучшить его!
Пример 2.
(DEFUN NTH (LAMBDA (N LST) ; Функция возвращает N-й элемент списка LST ; (COND ( (EQ N 1) (CAR LST) ) ( T (NTH (- N 1) (CDR LST) ) ) ) )) ; ------------------------- ; (DEFUN DELETE (LAMBDA (N LST) ; Функция удаляет N-й элемент из списка LST ; (COND ( (EQ N 1) (CDR LST) ) ( T (CONS (CAR LST) (DELETE (- N 1) (CDR LST))) ) ) )) ; --------------------------- ; (DEFUN INSERT (LAMBDA (X N LST) ; Функция вставляет элемент X на N-ю позицию ; ; в список LST ; (COND ( (NULL LST) (CONS X LST) ) ( (EQ N 1) (CONS X LST) ) ( T (CONS (CAR LST) (INSERT X (- N 1) (CDR LST))) ) ) ))
Пример 3.
(DEFUN SORTING (LAMBDA (L) ; Сортировка неупорядоченного списка L ; (COND ( (NULL L) NIL ) ( T (INSERT (CAR L) (SORTING (CDR L))) ) ) )) ; ----------------------- ; (DEFUN INSERT (LAMBDA (A L) ; Функция INSERT добавляет элемент A в упорядоченный ; ; список L так, чтобы сохранилась упорядоченность ; (COND ( (NULL L) (LIST A) ) ( (< A (CAR L)) (CONS A L) ) ( T (CONS (CAR L) (INSERT A (CDR L))) ) ) )) ; -------------------------- ; (DEFUN RASSTAV (LAMBDA (NEW L) ; Функция RASSTAV позволяет элементы списка NEW ; ; вставить в упорядоченный список L ; (COND ( (NULL NEW) L ) ( T (INSERT (CAR NEW) (RASSTAV (CDR NEW) L)) ) ) ))
Тестовые примеры:
$ (SORTING '(5 4 3 2 1 6)) (1 2 3 4 5 6) $ (RASSTAV '(4 3 1) '(1 2 5 6)) (1 1 2 3 4 5 6)
Пример 4. Функция, которая возвращает список всех атомов, встречающихся в данном списке LST, вместе с частотой их появления. Так как результат представляет собой множество пар, несущественно, в каком порядке эти пары расположены. Например:
(НИ ТО НИ ДРУГОЕ) --> ((НИ 2) (ТО 1) (ДРУГОЕ 1)).
Решение:
(DEFUN KOLAM (LAMBDA (LST)
(TH (LIST-SET LST) LST)
))
; ------------------------- ;
(DEFUN LIST-SET (LAMBDA (LST)
; Функция LIST-SET преобразует список LST в множество ;
(COND ( (NULL LST) NIL )
( (MEMBER (CAR LST) (CDR LST))
(LIST-SET (CDR LST)) )
( T (CONS (CAR LST) (LIST-SET (CDR LST))) )
)
))
; ------------------------ ;
(DEFUN TH (LAMBDA (LST LST0)
; Построение нового списка, содержащего элементы вида ;
; (Элемент Количество_повторений_этого_элемента_ ;
; в_списке) ;
(COND ( (NULL LST) NIL)
( T (CONS (LIST (CAR LST)
(KOL (CAR LST) LST0))
(TH (CDR LST) LST0)) ))
))
; ---------------------- ;
(DEFUN KOL (LAMBDA (M LST)
; Подсчет количества повторений элемента M в списке LST ;
(COND ( (NULL LST) 0 )
( (EQ (CAR LST) M)
(+ (KOL M (CDR LST)) 1) )
( T (KOL M (CDR LST)))
)
))
Тестовые примеры:
$ (KOLAM '(1 2 1 2 3 3 3 4)) ((1 2) (2 2) (3 3) (4 1)) $ (KOLAM '(1 5)) ((1 1) (5 1))
Пример 5. Функция, переставляющая элементы списка так, чтобы одинаковые элементы стали соседями. Например:
(A B C A B B) --> (A A B B B C)
Решение:
(DEFUN SOSEDI (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( T (COND ( (MEMBER (CAR LST) (CDR LST))
(CONS (CAR LST)
(SOSEDI
(CONS (CAR LST)
(DELETEFIRST
(CAR LST)
(CDR LST))))) )
( T (CONS (CAR LST)
(SOSEDI (CDR LST))) )
)
)
)
))
; ------------------------------ ;
(DEFUN DELETEFIRST (LAMBDA (A LST)
; Удаление первого вхождения элемента А в список LST ;
(COND ( (NULL LST) NIL )
( (EQUAL (CAR LST) A) (CDR LST) )
( T (CONS (CAR LST)
(DELETEFIRST A (CDR LST))) ))
))
Тестовые примеры:
$ (SOSEDI '(1 2 3 11 1 3)) (1 1 2 3 3 11) $ (SOSEDI '(0 1)) (0 1) $ (SOSEDI '()) NIL
Пример 6. Предикат, проверяющий, является ли последовательность элементов заданного числового списка упорядоченной по возрастанию.
Решение:
(DEFUN UPV (LAMBDA (LST)
(COND ( (EQUAL LST (SORTING LST)) PRIN1 "Да" )
( T PRIN1 "Нет" )
)))
; ------------------------ ;
(DEFUN SORTING (LAMBDA (LST)
; Сортировка неупорядоченного списка ;
(COND ( (NULL LST) NIL )
( T (INSERT (CAR LST) (SORTING (CDR LST))) )
)
))
; ------------------------- ;
(DEFUN INSERT (LAMBDA (A LST)
; Добавляет элемент А в упорядоченный список LST так, ;
; чтобы сохранилась упорядоченность ;
(COND ( (NULL LST) (LIST A) )
( (< A (CAR LST)) (CONS A LST) )
( T (CONS (CAR LST) (INSERT A (CDR LST))) )
)
))
Тестовые примеры:
$ (UPV '(1 2 3 4)) Да $ (UPV '(1 2 3 1)) Нет $ (UPV '()) Да
Пример 7. Под фильтром понимается функция, которая оставляет или удаляет элементы, удовлетворяющие заданному условию.
Ниже определены фильтры:
1) (DELETE-IF-PREDICAT LST) 2) (DELETE-IF-NON-PREDICAT LST),
Решение:
(DEFUN DELETE-IF-PREDICAT (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( (EQ (PREDICAT (CAR LST)) F )
(CONS (CAR LST)
(DELETE-IF-PREDICAT (CDR LST))) )
( T (DELETE-IF-PREDICAT (CDR LST)) )
)
))
; --------------------------------------- ;
(DEFUN DELETE-IF-NON-PREDICAT (LAMBDA (LST)
(COND ( (NULL LST) NIL )
( (EQ (PREDICAT (CAR LST)) T )
(CONS (CAR LST)
(DELETE-IF-NON-PREDICAT (CDR LST))) )
( T (DELETE-IF-NON-PREDICAT (CDR LST)) )
)
))
; ----------------------- ;
(DEFUN PREDICAT (LAMBDA (X)
; Предикат проверяет равенство элемента 0 ;
(COND ( (EQ X 0) T )
( T F )
)
))
Тестовые примеры:
$ (DELETE-IF-PREDICAT '(1 0 4 0 5)) (1 4 5) $ (DELETE-IF-PREDICAT '()) NIL $ (DELETE-IF-PREDICAT '(0 0)) NIL $ (DELETE-IF-NON-PREDICAT '(1 0 3 0 5)) (0 0) $ (DELETE-IF-NON-PREDICAT '(0 0 0)) (0 0 0) $ (DELETE-IF-NON-PREDICAT '(1 5)) NIL $ (DELETE-IF-NON-PREDICAT '()) NIL
Пример 8. Функция ищет в списке атомов такой атом, который встречается непосредственно перед заданным атомом.
Решение:
(DEFUN PATOM (LAMBDA (X LST)
(NTH (- (NATOM X LST) 1) LST)
))
; ---------------------- ;
(DEFUN NTH (LAMBDA (N LST)
; Функция возвращает N-й элемент списка LST ;
(COND ( (EQ N 1) (CAR LST) )
( T (NTH (- N 1) (CDR LST)) )
)
))
; ------------------------ ;
(DEFUN NATOM (LAMBDA (X LST)
; Функция возвращает позицию заданного элемента ;
(COND ( (NULL LST) 0)
( (EQ X (CAR LST)) 1)
( (MEMBER X LST) (+ 1 (NATOM X (CDR LST))) )
)
))
Тестовые примеры:
$ (PATOM 5 '(9 7 2 7 5 3)) 7 $ (PATOM 2 '(9 7 2 7 5 3)) 7 $ (PATOM 3 '(9 7 2 7 5 3)) 5
Пример 9.
(DEFUN SWAP (LAMBDA (N M LST) ; Обмен значениями N-го и M-го элементов списка LST ; (INSERT (NTH N LST) M (DELETE M (INSERT (NTH M LST) N (DELETE N LST)))) )) ; ---------------------- ; (DEFUN NTH (LAMBDA (N LST) ; Функция возвращает N-й элемент списка LST ; (COND ( (EQ N 1) (CAR LST) ) ( T (NTH (- N 1) (CDR LST)) ) ) )) ; --------------------------- ; (DEFUN INSERT (LAMBDA (X N LST) ; Функция вставляет элемент X на N-ю позицию ; ; в список LST ; (COND ( (NULL LST) (CONS X LST) ) ( (EQ N 1) (CONS X LST) ) ( T (CONS (CAR LST) (INSERT X (- N 1) (CDR LST))) ) ) )) ; ------------------------- ; (DEFUN DELETE (LAMBDA (N LST) ; Функция удаляет N-й элемент из списка LST ; (COND ( (EQ N 1) (CDR LST) ) ( T (CONS (CAR LST) (DELETE (- N 1) (CDR LST))) ) ) ))
Задачи для самостоятельного решения
- Определить функцию DISTL (распределение слева), действие которой рассмотрим на примере:
(A (B1 B2 ... BN)) --> ((A B1) (A B2) ... (A BN)) - Определить функцию DISTR (распределение справа), действие которой рассмотрим на примере:
((A1 A2 ... AN) B) -- > ((A1 B) (A2 B) ... (AN B)). - Определите функцию A такую, что (A N) возвращает список (THE ANSWER IS N). Так значением (A 12) будет
(THE ANSWER IS 12).
- Определить функцию COPY, такую, что (COPY X N) возвращает список из N копий целого числа X. Например, (COPY 3 5) есть список (3 3 3 3 3).
- Определить функцию LASTHALF, которая возвращает список из последних n атомов в списке из 2xN атомов. Так, если X есть (2 4 6 8), то (LASTHALF X) вернет (6 8).
- Напишите функцию DEPTH, такую, что (DEPTH L) возвращает максимальную глубину подсписков списка L. Так, если L есть (1 4 (2 6 (3 7) 8)), то (DEPTH L) возвратит 3.
- Определить функцию NOSUBS, такую что, (NOSUBS L) возвращает T, если список L не имеет подсписков, и NIL в противном случае.
- Отыскать в списке атомов такой атом, который встречается за один атом перед заданным атомом.
- Опишите функцию, которая возвращает список частот всех атомов, встречающихся в данном списке LST. Например: (НИ ТО НИ ДРУГОЕ) --> (2 1 1).
- Описать функцию, возвращающая список, в котором каждый атом из данного списка атомов LST имеет ровно одно вхождение.
- Установите, являются ли два списка X и Y конгруэнтными (имеющими одинаковую структуру).
- Определить функцию (EQUALL L), возвращающую T, если L - список, чьи элементы (на самом верхнем уровне) все равны друг другу и NIL в противном случае.
- Напишите функцию INDEXMAX, которая возвращает номер максимального числа в списке числовых атомов, не имеющего подсписков.
- Напишите функцию, возвращающую последний элемент списка.
- Напишите функцию, которая из данного списка строит список списков его элементов. Например, (A B ... F) -- > ((A) (B) ... (F)).
- Напишите функцию, зависящую от трех аргументов X, N и V, добавляющую X на N-е место в список V.
- Напишите функцию, удаляющую повторные вхождения элементов в список. Например: (A B D D A) --> (A B D).
- Напишите функцию, удаляющую из списка все элементы, стоящие на четных местах.
- Определите функцию, которая по данному списку строит список его элементов, встречающихся в нем более одного раза.
- Определите функцию, которая переставляет элементы списка так, чтобы одинаковые элементы стали соседями, а затем обращает его. Например, (A B C A B B) --> (C B B B A A)
- Напишите функцию, заменяющую в списке W атом Y на число, равное глубине вложения Y в W.
Например, если
то функция должна вернуть список ((2 B) 1 (C (3 (4 D)))).
Y = A W = ((A B) A (C (A (A D)))),
- Напишите функцию, "обрывающую" список, если он состоит более чем из N элементов.
- Определите функцию, строящую N-уровневый список, элементом которого на самом глубоком уровне является N. Например, если N=5, то функция вернет (((((5))))).
- Определить, имеются ли в числовом списке С два подряд идущих нулевых элемента.
- Из числового списка В, первый элемент которого неотрицателен, убрать все отрицательные элементы, заменив их на значения предыдущих элементов.
- Написать программу определения количества элементов числового списка LST, удовлетворяющих условию
0 < Элемент <= Номер_элемента в списке LST - В числовом списке подсчитать количество четверок идущих подряд элементов, в каждой из которых все элементы различны.
- Найти наибольшее из всевозможных попарных произведений элементов числового списка.
- Найти, сколько различных элементов содержит данный числовой список.
- Найти длину самой длинной последовательности нулей в числовом списке.
- Проверить, является ли последовательность элементов числового списка упорядоченной по убыванию.
- Выясните, является ли данный список подсписком другого списка.
- Замените отрицательные элементы числового списка на 0.
- Выясните, есть ли в числовом списке два одинаковых элемента.
- Даны два числовых списка. Проверьте, есть ли в них одинаковые элементы, и, если есть, найдите наибольший.
- Найдите значение и номер чаще всего встречающегося элемента списка.
- Дан одноуровневый список. Все его элементы, не равные нулю, переписать (сохраняя их порядок) в начало списка, а нулевые элементы - в конец.
- Напишите функцию, подсчитывающую число разбиений заданного натурального N. Разбиением целого числа называется представление его в виде суммы целых чисел.
Например, разбиениями числа 4 являются 4, 3+1, 2+2, 2+1+1, 1+1+1+1.
Указание. Возможный путь решения этой задачи можно посмотреть в книге: Баррон Д. Рекурсивные методы в программировании. - М.: Мир, 1974.
- Напишите функцию для проверки, совпадают ли первый элемент списка Х и последний элемент списка Y.
- Одноуровневый список LST содержит латинские буквы. Написать функцию для подсчета количества гласных букв в данном списке.
- Опишите назначение приведенной ниже функции:
(DEFUN BOUNDP (LAMBDA (X) (COND ( (NOT (ATOM X)) NIL ) ( (EQ X (QUOTE X)) T ) ( T NIL ) ) )) - Напишите функцию для проверки совпадения ли второго и предпоследнего элемента данного числового списка.
- Напишите функцию, возвращающую N последних элементов списка LST.
- Реализуйте на языке LISP функцию языка программирования APL, называемую внешним произведением. Она возвращает все возможные произведения элементов левого аргумента на элементы правого.
- Реализуйте на языке LISP операции сложения, умножения и транспонирования многомерных массивов.
- Реализуйте на языке LISP функцию языка программирования APL, называемую перестройка (обозначается @, действие
которой разберем на примерах:
1) Команда : 2 3 @ 4 7 8 2 4 6 Результат выполнения: 4 7 8 2 4 6 2) Команда : 4 2 @ 7 8 4 Результат выполнения: 7 8 4 7 8 4 7 8 3) Команда : 3 4 @ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Результат выполнения: 1 2 3 4 5 6 7 8 9 10 11 12Числа, стоящие слева от знака операции, определяют структуру результирующей матрицы, а именно: число строк и число столбцов матрицы. Числа, стоящие справа от знака операции, используются для построения массива, они располагаются по строкам.
Здесь уместно сделать два замечания.
Во-первых, если у Вас недостаточно элементов для того, чтобы построить массив, APL возвращается к началу "кучи" данных, находящихся в правой части, и начинает вновь выбирать из нее элемент за элементом.
Во-вторых, если у нас, напротив, слишком много элементов, то выбирается ровно столько, сколько нужно, остальные игнорируются.
- Напишите функцию INTERN, проверяющую, есть ли атом с данным именем в списке OBLIST. Если такой атом уже имеется, то функция возвращает имя этого атома, если нет - то добавляет в OBLIST новый атом.
- Определите функцию, зависящую от двух аргументов U и V, являющихся списками, которая возвращает список всех элементов U, не содержащихся в V и элементов V, не содержащихся в U.
- Даны два конгруэнтных (имеющих одинаковую структуру) списка X и Y. Определите функцию, которая по элементу N из списка X возвращает соответствующий элемент в списке Y.
- Эквивалентность представлений программ и данных в языке LISP позволяет легко писать многие весьма нетривиальные программы,
которые при программировании на языках императивного программирования требуют гораздо больших усилий.
Некоторые из них стали классическими задачами языка LISP;
типичной является задача построения авторепликативной (самовоспроизводящейся) функции.
Напишите функцию SRF, значением которой является ее собственное определение. SRF не имеет входных параметров.
Если SRF определяется как
то результатом вызова (SRF) является список(SRF (LAMBDA () (...Тело...))),
(SRF (LAMBDA () (...Тело...))).
На следующем шаге мы приведем задачи на обработку строк.
