На этом шаге мы рассмотрим функции, модифицирующие структуры.
В языке LISP есть специальные функции, с помощью которых можно "разорвать" структуру и "склеить" ее по-новому. Такие функции называют структуро-разрушающими или модификаторами. Модификаторы выполняют переадресацию указателей в структурах данных языка LISP. Следовательно, при использовании модификаторов важен прежде всего результат их работы, нежели значение, которую они возвращают.
Опасность применения этих операций возникает из-за возможного существования общих подсписков, о которых программист может забыть. Если какой-то список изменяется и является подсписком другого спискa, то тот список также изменится.
Эффективность этих операций обусловлена двумя причинами:
- для изменения списка не требуется дополнительной работы;
- при построении списков отпадает необходимость выполнять много копирований.
Приведем перечень функций, которые рассматриваются на этом шаге:
| Замещает CAR-элемент OBJECT1 указателем на OBJECT2 и возвращает модифицированный OBJECT1. | |
| Замещает CDR-элемент OBJECT1 указателем на OBJECT2 и возвращает модифицированный OBJECT1. | |
| Объединяет списки "физически", устанавливая указатель в поле CDR последней ячейки списка, являющегося первым аргументом, на начало списка, являющегося вторым аргументом. | |
| Замещает на элемент NEW те элементы OLD списка LIST, для которых признак проверки по тесту TEST отличен от NIL. | |
| Замещает на NEW все подвыражения OBJECT, для которых признак проверки по тесту TEST отличен от NIL. | |
| Функция уничтожает все элементы списка LIST, для которых признак проверки по тесту TEST не является NIL. | |
| Возвращает список, состоящий из элементов списков LIST1,...,LISTN в том же порядке, путем модификации последних CDR-элементов LIST1, ..., LISTN. | |
| Разбивает список LIST на два списка путем замены CDR-элемента точечной пары верхнего уровня, расположенной посередине списка LIST, на NIL. | |
| Возвращает инвертированный список LIST, сцепленный с объектом языка LISP OBJECT. | |
| Возвращает список, состоящий из всех элементов списка LIST, кроме последних N элементов, путем замещения CDR-элемента N-й точечной пары, отсчитанной от конца списка LIST, на NIL. |
Простейшими модификаторами, изменяющими физическую структуру списков, являются функции RPLACA (RePLACe cAr), RPLACD (RePLACe cDr), которые записывают новые значения в поля CAR и CDR списочной ячейки, и функция NCONC (CONCateNate), которая "физически" соединяет списки.
Замечание. Перед тем, как читать дальше, запомните, что побочным эффектом обращения к RPLACA или RPLACD может оказаться изменение значений всех выражений, во внутреннем представлении которых участвует преобразованная ячейка.
Если OBJECT1 не является ни NIL, ни числом, то функция (RPLACA OBJECT1 OBJECT2) замещает CAR-элемент OBJECT1 указателем на OBJECT2 и возвращает модифицированный OBJECT1.
Результат такого замещения зависит от типа OBJECT1.
Если OBJECT1 - список, то первый элемент списка замещается на OBJECT2. Например:
$ (SETQ FOO '(A B C)) (A B C) $ (RPLACA FOO D) (D B C) $ FOO (D B C)
Если OBJECT1 - бинарное дерево (точечная пара), то левая ветвь дерева замещается на OBJECT2.
Если OBJECT1 - символ, но не NIL, то элемент значения символа принимается за OBJECT2.
Во всех случаях возвращается модифицированный OBJECT1.
Если OBJECT1 не является ни NIL, ни числом, то функция (RPLACD OBJECT1 OBJECT2) замещает CDR-элемент OBJECT1 указателем на OBJECT2 и возвращает модифицированный OBJECT1.
Результат такого замещения зависит от типа OBJECT1.
Если OBJECT1 - список, то хвост списка замещается на OBJECT2. Например:
$ (SETQ FOO '(A B C)) (A B C) $ (RPLACD FOO '(D E)) (A D E) $ FOO (A D E)
Если OBJECT1 - бинарное дерево, то правая ветвь дерева замещается на OBJECT2.
Если OBJECT1 - символ, но не NIL, то список свойств символа замещается на OBJECT2.
Во всех случаях возвращается модифицированный OBJECT1.
Пример 1.
$ (RPLACA '(5 . 6) 11) (11 . 6) $ (RPLACD '(5 . 6) 11) (5 . 11)
Пример 2. Вычислим значения следующих выражений:
1. (RPLACD '(A) B) Результат: (A . B)
Рис.1. Исходная схема и результат
2. (RPLACA '(A) B) Результат: (B) или (B . NIL)
Рис.2. Исходная схема и результат
3. (RPLACD '(NIL) NIL) Результат: (NIL) или (NIL . NIL)
Рис.3. Исходная схема и результат
4. (RPLACD '(NIL) '(NIL)) Результат: (NIL NIL) или (NIL . (NIL . NIL))
Рис.4. Исходная схема и результат
Пример 3. Пусть значением атома X является список (A B C):
Рис.5. Исходный список
После выполнения (RPLACD (CDDR X) X) мы получим:
Рис.6. Результат выполнения операции
Значение X не имеют эквивалента в языке, так как представляют собой циклическую списочную структуру!
После выполнения (CONS (CAR (CDDR X)) X) получим
Рис.7. Результат выполнения операции
Функция NCONC объединяет списки "физически", устанавливая указатель в поле CDR последней ячейки списка, являющегося первым аргументом, на начало списка, являющегося вторым аргументом. Например:
$ (SETQ A '(1 2 3)) (1 2 3) $ (SETQ B '(4 5 6)) (4 5 6) $ (SETQ C (NCONC A B)) (1 2 3 4 5 6) $ A (1 2 3 4 5 6)
Если значением атома FOO является список, то функция (NCONC FOO FOO) создаст циклический список, и если в дальнейшем будет сделана попытка выдать на экран дисплея значение FOO, то этот процесс будет длиться бесконечно. Например:
$ (SETQ A '(1 2 3)) (1 2 3) $ (NCONC A A) (1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
Псевдофункции, подобные RPLACA, RPLACD и NCONC, изменяющие внутреннюю структуру списков, используются в том случае, если нужно сделать небольшие изменения в большой структуре данных. Но коварные побочные эффекты, вроде изменения значений внешних переменных, могут привести к сюрпризам в тех частях программы, которые "не знают" об изменениях. Это осложняет написание, документирование и сопровождение программ, поэтому функциями, изменяющими структуры, стараются пользоваться редко!
Замечание. Функции RPLACA и SET идентичны. Однако функция RPLACA возвращает свой первый аргумент, а SET - второй. Кaк правило, SET используют в том случае, когда ее первый аргумент - атом, а RPLACA - тогда, когда ее первый аргумент - точечная пара.
С учетом сказанного можно записать код функции SET так:
(DEFUN SET (SYM OBJ)
( (SYMBOLP SYM) ( (NULL SYM) OBJ )
( RPLACA SYM OBJ )
OBJ)
( BREAK (LIST 'SET SYM OBJ) '"Nonsymbolic Argument")
)
В версии muLISP85 существуют еще несколько модификаторов: NSUBSTITUTE, NSUBSTITUTE-IF, NSUBST, NSUBST-IF, DELETE, DELETE-IF, NREVERSE, NBUTLAST, TCONC, LCONC, SPLIT, SORT, MERGE.
NSUBSTITUTE [new,old,list,test] Function
NSUBSTITUTE-IF [new,test,list] Function
1.Модифицируя точечные пары высокого уровня списка LIST, функция (NSUBSTITUTE NEW OLD LIST TEST) замещает на элемент NEW те элементы OLD списка LIST, для которых признак проверки по тесту TEST отличен от NIL.
Если тест-аргумент есть NIL или не задан, то функция NSUBSTITUTE использует EQL-тест. Например:
$ (NSUBSTITUTE 5 2 '(4 2 (3 . 2) 4)) (4 5 (3 . 2) 4) $ (NSUBSTITUTE 'CANNIBALS 'NOUN '(NOUN LIKE TO EAT NOUN)) (CANNIBALS LIKE TO EAT CANNIBALS)
Функция (NSUBSTITUTE-IF NEW TEST LIST) замещает на элементы NEW те элементы списка LIST, для которых признак проверки по тесту отличен от NIL.
Приведем код функции:
(DEFUN NSUBSTITUTE (NEW OLD LST TEST)
( (ATOM LST) LST )
( ( (NULL TEST) (SETQ TEST 'EQL) ) )
( (FUNCALL TEST OLD (CAR LST))
(RPLACA LST NEW)
(NSUBSTITUTE NEW OLD (CDR LST) TEST)
)
( NSUBSTITUTE NEW OLD (CDR LST) TEST )
)
2. Модифицируя точечные пары OBJECT, функция (NSUBST NEW OLD OBJECT TEST) замещает на NEW все подвыражения OBJECT, для которых признак проверки по тесту TEST отличен от NIL. Если тест-аргумент есть NIL или не задан, функция NSUBST использует EQL-тест. Например:
$ (NSUBST 5 2 '(4 2 (3 . 5 ) 4)) (4 5 (3 . 5 ) 4)
Функция (NSUBST NEW TEST OBJECT) замещает на NEW все подвыражения OBJECT, для которых признак проверки по тесту TEST отличен от NIL.
Приведем код функции:
(DEFUN NSUBST (NEW OLD OBJ TEST)
( ((NULL TEST) (SETQ TEST 'EQL)) )
( (FUNCALL TEST OLD OBJ) NEW )
( (ATOM OBJ) OBJ )
( RPLACA OBJ (NSUBST NEW OLD (CAR OBJ) TEST) )
( RPLACA OBJ (NSUBST NEW OLD (CDR OBJ) TEST) )
)
3. Функция (DELETE ITEM LIST TEST) уничтожает все элементы списка LIST, для которых признак проверки по тесту TEST не является NIL. Если тест-аргумент есть NIL или не задан, то функция DELETE использует EQL-тест. Например:
$ (DELETE '(2 5) '((5 2) (2 5) (2 3)) 'EQUAL) ((5 2) (2 3))
Функция (DELETE-IF TEST LIST) уничтожает все элементы списка LIST, для которых при проверке по тесту TEST признак отличен от NIL. Например:
$ (DELETE-IF 'MINUS '(-2 0 7 -0.1 3)) (0 7 3)
Приведем код функции:
(DEFUN DELETE (ITEM LST TEST RLST )
( ( (NULL TEST) (SETQ TEST 'EQL) ) )
(LOOP
( (ATOM LST) )
( (FUNCALL TEST ITEM (CAR LST)) )
(POP LST)
)
( (ATOM LST) LST )
( SETQ RSLT LST )
(LOOP
( (ATOM (CDR LST)) RSLT )
( ( (FUNCALL TEST ITEM (CADR LST))
( RPLACD LST (CDDR LST) )
)
(POP LST) )
)
)
4. Функция (NCONC LIST1 ... LISTN) возвращает список, состоящий из элементов списков LIST1, ..., LISTN в том же порядке, путем модификации последних CDR-элементов LIST1, ..., LISTN.
Отметим, что функции NCONC и APPEND, заданные с одинаковыми аргументами, вернут эквивалентные списки.
Если значением FOO является список, то (NCONC FOO FOO) создаст циркулярный список, и если будет сделана попытка выдать на экран дисплея значение FOO, то этот процесс будет длиться бесконечно. Например:
$ (SETQ FOO '(D E F)) (D E F) $ (NCONC '(A B C) FOO '(G H I)) (A B C D E F G H I) $ FOO (D E F G H I)
Приведем код функции:
(DEFUN NCONC (LST1 LST2)
( (ATOM LST1) LST2 )
( RPLACD (LAST LST1) LST2 )
LST1
)
5. Функция (SPLIT LIST) разбивает список LIST на два списка путем замены CDR-элемента точечной пары верхнего уровня, расположенной посередине списка LIST, на NIL. Функция SPLIT возвращает хвост LIST, начиная с места разбиения.
Если список LIST имеет четное количество элементов, то его голова и хвост при разбиении будут иметь одинаковое количество элементов.
Если список имеет нечетное количество элементов, то голова будет иметь на один элемент больше, чем хвост. Например:
$ (SETQ NAMES '(TJM SUE JOE PAT SAM)) (TOM SUE JOE PAT SAM) $ (SPLIT NAMES) (PAT SAM) $ NAMES (TOM SUE JOE)
Приведем код функции:
(DEFUN SPLIT (LST)
( (ATOM LST) LST )
(split-aux LST (CDR LST))
)
(DEFUN split-aux (HEAD TAIL)
( (ATOM TAIL) (PROG1 (CDR HEAD) (RPLACD HEAD NIL)) )
(POP TAIL)
( (ATOM TAIL) (PROG1 (CDR HEAD) (RPLACD HEAD NIL)) )
( split-aux (CDR HEAD) (CDR TAIL) )
)
6. Функция (NREVERSE LIST OBJECT) возвращает инвертированный список LIST, сцепленный с объектом языка LISP OBJECT. Результат аналогичен результату, возвращаемому функцией (NCONC (NREVERSE LIST) OBJECT), но вызов NREVERSE с двумя аргументами более эффективен. Учтите, что функция NREVERSE модифицирует точечные пары верхнего уровня списка LIST!
Приведем реализацию функции NREVERSE:
(DEFUN NREVERSE (LAMBDA (LST OBJ)
(COND ( (ATOM LST) OBJ )
( T (NREVERSE (CDR LST) (RPLACD LST OBJ)) )
)
))
Тестовые примеры:
$ (NREVERSE '(A B C D E)) $ (SETQ FOO '(A B C)) (E D C B A) (A B C) $ (NREVERSE '(A B C) '(D E F)) $ (NREVERSE FOO) (C B A D E F) (C B A) $ (NREVERSE '(A B C) 'D) $ FOO (C B A . D) A
7. Если N - нуль или положительное целое, то функция (NBUTLAST LIST N) возвращает список, состоящий из всех элементов списка LIST, кроме последних N элементов, путем замещения CDR-элемента N-й точечной пары, отсчитанной от конца списка LIST, на NIL. Отсутствие аргумента N отождествляет N с 1. Например:
$ (SETQ FOO '(A B C)) $ (NBUTLAST '(A B C D)) (A B C) (A B C) $ (NBUTLAST FOO) $ (NBUTLAST '(A B C D) 2) (A B) (A B) $ FOO (A B) $ (NBUTLAST FOO 2) NIL $ FOO (A B)
На следующем шаге мы рассмотрим управляющие конструкции.
