Основные методы обработки списков
Следующие функции используются, когда рассматриваются лишь списки.
APPEND - функция двух аргументов x и y, сцепляющая два списка в один.
(DEFUN append (x y) (COND ((null x) y) ((QUOTE T) (CONS (CAR x) (append (CDR x) y) ) ) ) ) (append '(A B) '(C D E)) ;= (A B C D E)
MEMBER - функция двух аргументов x и y, выясняющая встречается ли S-выражение x среди элементов списка y.
(DEFUN member (x y) (COND ((null y) (QUOTE Nil)) ((equal x (CAR y)) (QUOTE T)) ((QUOTE T) (member x (CDR y)) ) ) (member ' A '( B (A) C)
PAIRLIS - функция трех аргументов x, y, al, строит список пар соответствующих элементов из списков x и y - связывает и присоединяет их к списку al. Полученный список пар, похожий на таблицу с двумя столбцами, называется ассоциативным списком или ассоциативной таблицей. Такой список может использоваться для связывания имен переменных и функций при организации вычислений интерпретатором.
(DEFUN pairlis (x y al) (COND ((null x) al) ((QUOTE T) (CONS (CONS (CAR x) (CAR Y) ) (pairlis (CDR x) (CDR y) al) ) ) ) )
(pairlis '(A B C) '(u t v) '((D . y)(E . y))) ;= ((A . u)(B . t)(C . v)(D . y)(E . y))
ASSOC - функция двух аргументов x и al. Если al - ассоциативный список, подобный тому, что формирует функция pairlis, то assoc выбирает из него первую пару, начинающуюся с x. Таким образом, это функция поиска определения или значения по таблице, реализованной в форме ассоциативного списка.
(DEFUN assoc (x al) (COND ((equal x (CAAR al)) (CAR al)) ((QUOTE T) (assoc x (CDR al)) ) ) ) (assoc 'B '((A . (m n)) (B . (CAR x)) (C . w) (B . (QUOTE T)))) ;= (B . (CAR x))
Частичная функция - рассчитана на наличие ассоциации.
SUBLIS - функция двух аргументов al и y, предполагается, что первый из аргументов AL устроен как ассоциативный список вида ((u1 . v1) ... (uK . vK)), где u есть атомы, а второй аргумент Y - любое S-выражение. Действие sublis заключается в обработке Y, такой что вхождения переменных Ui, связанные в ассоциативном списке со значениями Vi, заменяются на эти значения.
Другими словами в S-выражении Y вхождения переменных U заменяются на соответствующие им V из списка пар AL. Вводим вспомогательную функцию SUB2, обрабатывающую атомарные S-выражения, а затем - полное определение SUBLIS:
(DEFUN sub2 (al z) (COND ((null al) z) ((equal (CAAR al) z) (CDAR al)) ((QUOTE T) (sub2 (CDR al) z)) ) )
(DEFUN sublis (al y) (COND ((ATOM y) (sub2 al y)) ((QUOTE T)(CONS (sublis al (CAR y)) (sublis al (CDR y)) ) )))
(sublis '((x . Шекспир)(y . (Ромео и Джульетта))) '(x написал трагедию y)) ;= (Шекспир написал трагедию (Ромео и Джульетта))
Пример 5.1.
(html, txt)
INSERT – вставка z перед вхождением ключа x в список al.
(DEFUN insert (al x z) (COND ((null al) Nil) ((equal (CAR al) x) (CONS z al)) ((QUOTE T) (CONS (CAR al) (insert (CDR al) x z))) ) )
(insert '(a b c) 'b 's) ; = (a s b c)
ASSIGN – модель присваивания переменным, хранящим значения в ассоциативном списке. Происходит замена значения, связанного с данной переменной в первой найденной паре, на новое заданное значение. Если не было пары вообще, то новую пару из переменной и ее значения размещаем в конец а-списка, чтобы она могла работать как глобальная.
(DEFUN assign (x v al) (COND ((Null al) (CONS (CONS x v) Nil )) ((equal x (CAAR al))(CONS (CONS x v) (CDR al))) ((QUOTE T) (CONS (CAR al) (assign x v (CDR al)))) ) ) (assign 'a 111 '((a . 1)(b . 2)(a . 3))) ;= ((a . 111)(b . 2)(a . 3)) (assign 'a 111 '((c . 1)(b . 2)(a . 3))) ;= ((c . 1)(b . 2)(a . 111)) (assign 'a 111 '((c . 1)(d . 3))) ;= ((c . 1)(d . 3) (a . 111))
Упражнение 5.1: Введите функции с именами – Пусто, Пара_в_список, Список_в_пару, входит_ли, Соединение, Элемент, Связывание, Ассоциация, Ряд_подстановок, Вставка, Присваивание, как аналоги вышеприведенных функций.
Упражнение 5.2: Напишите определение функции REVERSE – обращение списка, т.е. перечисление его элементов в обратном порядке.
Ответ:
(defun reverse (m) (cond ((null m) NIL) (T (append(reverse(cdr m)) (list(car m)) )) ))
Теперь посмотрим ее вариант как пример использования накапливающих параметров и вспомогательных функций:.
(defun rev (m n) (cond ((null m) N) (T (rev(cdr m) (cons (car m) n))) ))
(defun reverse (m) (rev m Nil) )
Такое определение экономнее расходует память.
| (Append Список … ) | Сцепляет списки, полученные как аргументы |
| (Assoc Атом А-список) | Находит в А- списке пару, левая часть которой - Атом |
| (Eq Данное1 Данное2) | Истина при идентичных данных |
| (Equal Структура1 Структура2 ) | Истина при эквивалентных структурах |
| (Delete Объект Список ) | Строит копию Списка без заданного объекта |
| (Intersection Список … ) | Пересечение списков |
| (Last Список ) | Последний элемент сруктуры, представляющей список. Можно задавать длину завершающего отрезка списка. |
| (Lenth Список ) | Длина списка |
| (List Форма … ) | Строит список из значений Форм |
| (Member Объект Список ) | Ищет Объект в Списке |
| (Null Форма) | Истина для Nil |
| (Pairlis Атомы Данные А-спиок) | Пополняет А-список парми из Атомов и значений соответсвующих Данных. |
| (Reverse Список ) | Копия Списка с обратным порядком элементов |
| (Set-difference Список … ) | Разность множеств, представленных Списками |
| (Sort Список Предикат ) | Упорядочивает Список согласно Предикату |
| (Sublis А-список Структура ) | Преобразует Структуру согласно А-списку методом подстановки данных вместо связанных с ними атомов. |
| (Subst Новое Старое Структура ) | Преобразует Структуру, заменяя Старое на Новое. |
| (Union Список … ) | Объединение множеств, представленных Списками. |
