Основные методы обработки списков
Следующие функции полезны, когда рассматриваются лишь списки.
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) d)) ; = T (member 'a '(b (a) d)) ; = NIL
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) ) ; = (Шекспир написал трагедию (Ромео и Джульетта))
Пример 3.1.
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))
REVERSE — обращение списка — два варианта, второй с накапливающим параметром и вспомогательной функцией:
(DEFUN reverse (m) (COND ((null m) NIL) (T (append(reverse(CDR m)) (list(CAR m)) )) ) )
(DEFUN reverse (m) (rev m Nil)) (DEFUN rev (m n) (COND ((null m)N) (T (rev(CDR m) (CONS (CAR m) n)) ) ) )
