На этом шаге мы рассмотрим ассоциативные списки.
Начиная с этого шага, мы опишем фундаментальные типы данных в диалекте muLISP81. Заметим, что в нем отсутствуют такие фундаментальные структуры данных, как вещественные числа, строки, массивы, последовательности и структуры.
Ассоциативный список (A-список, список пар) - это фундаментальный тип данных, представляющий собой список точечных пар вида: ( (A1 . T1) (A2 . T2) ... (AN . TN) )
Первый элемент пары (CAR) называют ключом, а второй (CDR) - связанными с ключом данными. Обычно ключом является атом. Связанные с ним данные могут быть атомами, списками или какими-нибудь другими объектами языка LISP.
Приведем формальное определение A-списка в форме Бэкуса-Наура:
<Ассоциативный список> ::=
NIL | (<Точечная пара> . <Ассоциативный список>)
<Точечная пара> ::=
(<Атом> . <Атом>) | (<Атом> . <Точечная пара>) |
(<Точечная пара> . <Атом>) |
(<Точечная пара> . <Точечная пара>)
Приведем графическое представление A-списка:
Рис.1. Графическое представление A-списка
С помощью A-списка можно объединить разнотипные компоненты данных в единый комплекс данных.
В работе со списками пар нужно уметь строить ассоциативные списки, искать данные по ключу и обновлять их.
1. Построим функцию PAIRLIS, с помощью которой можно построить A-список из списка KEY ключей и списка DATA, сформированного из соответствующих им данных. Третьим аргументом является "старый" A-список A-LIST, в начало которого добавляются новые пары:
(PAIRLIS KEY DATA A-LIST)
Определим PAIRLIS следующим образом:
(DEFUN PAIRLIS (LAMBDA (KEY DATA A-LIST) ;Построение A-списка из списка ключей KEY и ; ; списка данных DATA ; ( (NULL KEY) A-LIST ) ( (NULL DATA) A-LIST ) (CONS (CONS (CAR KEY) (CAR DATA)) (PAIRLIS (CDR KEY) (CDR DATA) A-LIST) ))
2. Функции (REKEY ALIST) и (REDATA ALIST) "расщепляют" A-список ((X1 . E1)...(Xk . Ek)) и формируют отдельно список ключей (X1 ... Xk) и список данных (E1 ... Ek).
(DEFUN REKEY (LAMBDA (ALIST)
(COND ( (NULL ALIST) NIL )
( T (CONS (CAR (CAR ALIST))
(REKEY (CDR ALIST))) )
)
))
; ------------------------- ;
(DEFUN REDATA (LAMBDA (ALIST)
(COND ( (NULL ALIST) NIL )
( T (CONS (CDR (CAR ALIST))
(REDATA (CDR ALIST))) )
)
))
3. Функция (ASSOC KEY ALIST) ищет в списке пар ALIST данные, соответствующие ключу KEY, сравнивая искомый ключ с ключами пар слева направо.
ASSOC можно было бы определить (упрощенно) следующим образом:
(DEFUN ASSOC1 (LAMBDA (KEY ALIST) ; Поиск в списке пар ALIST данных, ; ; соответствующих ключу KEY ; (COND ( (NULL ALIST) NIL ) ( (EQ (CAAR ALIST) KEY) (CAR ALIST) ) ; Возвращается первая найденная пара, ; ; содержащая ключ KEY ; ( T (ASSOC1 KEY (CDR ALIST)) ) ) ))
Заметьте, что в качестве значения ASSOC возвращает точечную пару или NIL, если ключа KEY в ассоциативном списке нет.
Построим функцию RASSOC, которая ищет ключ по известным данным DATA в списке ALIST (RASSOC - это сокращение от английских слов "Reverse" и "ASSOCiate"):
(DEFUN RASSOC (LAMBDA (DATA ALIST) ; Поиск в списке пар ALIST ключа, ; ; соответствующего данным DATA ; (COND ( (NULL ALIST) NIL ) ( (EQ (CDAR ALIST) DATA) (CAR ALIST) ) ; Возвращается пара, содержащая данные DATA ; ( T (RASSOC DATA (CDR ALIST)) ) ) ))
4. Ассоциативный список можно обновлять и использовать в режиме стека. Новые пары добавляются к нему только в начало списка, хотя в списке уже могут быть данные с тем же ключом. Это осуществляется функцией ACONS:
(DEFUN ACONS (LAMBDA (X Y ALIST)
; Добавление в начало списка ALIST пары (X . Y) ;
(CONS (CONS X Y) ALIST)
))
Поскольку ASSOC просматривает список слева направо и доходит лишь до первой пары с искомым ключом, то более старые пары как бы остаются "в тени" более новых. Преимуществом этого является простота изменения связей и возможность возврата к значениям старых связей. Недостатком является то, что поиск данных замедляется пропорционально количеству элементов в списке.
5. Если старое значение больше не потребуется, то ассоциативный список ALIST можно изменить, физически изменив данные, связанные с ключом. Это делается при помощи изменяющей значение поля CDR псевдофункции RPLACD: (RPLACD (ASSOC KEY ALIST) DATA).
Значением первого аргумента вызова будет точечная пара, поле CDR которой соответствующее ключу KEY, затем заменяется на данные DATA из второго аргумента.
Определим псевдофункцию PUTASSOC (PUT ASSOCiation):
(DEFUN PUTASSOC (LAMBDA (KEY DATA ALIST) ; Изменение данных, соответствующих ключу KEY, ; ; на данные DATA ; ( (NULL ALIST) NIL ) ( (EQ (CAAR ALIST) KEY) (RPLACD (CAR ALIST) DATA) ) ( (NULL (CDR ALIST)) (RPLACD ALIST (LIST (CONS KEY DATA))) ) ; Добавление новой пары (KEY . DATA) ; ( PUTASSOC KEY DATA (CDR ALIST) ) ))
Псевдофункция PUTASSOC работает со списком не на логическом, а на физическом уровне. Это означает, что если мы использовали старый A-список в каком-нибудь другом значении, то это значение может измениться в результате побочного эффекта обновления из-за действия PUTASSOC.
Пример. Библиотека функций для работы с ассоциативными списками.
(DEFUN TEST (LAMBDA NIL
; Инициализация ;
(SETQ A '(JAPAN RUSSIA))
(SETQ B '(TOKIO MOSCOW))
; ------------------------------------------ ;
(PRIN1 "Построим A-список из списков A и B: ")
(PRINT (SETQ ALIST (PAIRLIS A B NIL)))
; ----------------------------------------- ;
(PRIN1 "Проверим составные части A-списка: ")
(PRINT (REKEY ALIST))
(PRINT (REDATA ALIST))
; ------------------------------------------------- ;
(PRIN1 "Найдем данные, соответствующие ключу RUSSIA: ")
(PRINT (ASSOC1 RUSSIA ALIST))
(PRIN1 "Найдем данные, соответствующие ключу JAPAN: ")
(PRINT (ASSOC1 JAPAN ALIST))
; -------------------------------------------------- ;
(PRIN1 "Найдем ключ, соответствующий данным MOSCOW: ")
(PRINT (RASSOC MOSCOW ALIST))
; -------------------------------------------------- ;
(PRINT "Добавление в начало A-списка точечной пары: ")
(PRINT (SETQ ALIST (ACONS USA WASHINGTON ALIST)))
; ---------------------------------------------------- ;
(PRINT "Изменение данных, соответствующих ключу RUSSIA: ")
(PUTASSOC RUSSIA SPB ALIST)
))
; ----------------------------------- ;
(DEFUN PAIRLIS (LAMBDA (KEY DATA ALIST)
; Построение A-списка из списка ключей KEY и списка ;
; данных DATA путем добавления новых пар к существу- ;
; ющему списку ALIST ;
( (NULL KEY) ALIST )
( (NULL DATA) ALIST )
( CONS (CONS (CAR KEY) (CAR DATA))
(PAIRLIS (CDR KEY) (CDR DATA) ALIST) )
))
; ----------------------------- ;
(DEFUN ASSOC1 (LAMBDA (KEY ALIST)
; Поиск в списке пар ALIST данных, соответствующих ;
; ключу KEY ;
(COND ( (NULL ALIST) NIL )
( (EQ (CAAR ALIST) KEY) (CAR ALIST) )
; 1Возвращается первая найденная пара, ;
; 1 содержащая ключ KEY ;
( T (ASSOC1 KEY (CDR ALIST)) )
)
))
; ------------------------------ ;
(DEFUN RASSOC (LAMBDA (DATA ALIST)
; Поиск в списке пар ALIST ключа, соответствующего ;
; данным DATA ;
(COND ( (NULL ALIST) NIL )
( (EQ (CDAR ALIST) DATA) (CAR ALIST) )
; Возвращается пара, содержащая данные DATA ;
( T (RASSOC DATA (CDR ALIST)) )
)
))
; ---------------------------- ;
(DEFUN ACONS (LAMBDA (X Y ALIST)
; Добавление в начало списка ALIST ;
; точечной пары (X . Y) ;
(CONS (CONS X Y) ALIST)
))
; ------------------------------------ ;
(DEFUN PUTASSOC (LAMBDA (KEY DATA ALIST)
; Изменение данных, соответствующих ключу KEY, ;
; на данные DATA ;
( (NULL ALIST) NIL )
( (EQ (CAAR ALIST) KEY) (RPLACD (CAR ALIST) DATA) )
( (NULL (CDR ALIST))
(RPLACD ALIST (LIST (CONS KEY DATA))) )
; Добавление новой пары (KEY . DATA) ;
( PUTASSOC KEY DATA (CDR ALIST) )
))
; ------------------------ ;
(DEFUN REKEY (LAMBDA (ALIST)
; Восстановление списка ключей по известному А-списку ;
(COND ( (NULL ALIST) NIL )
( T (CONS (CAR (CAR ALIST))
(REKEY (CDR ALIST))) )
)
))
; ------------------------- ;
(DEFUN REDATA (LAMBDA (ALIST)
; Восстановление списка данных по известному А-списку ;
(COND ( (NULL ALIST) NIL )
( T (CONS (CDR (CAR ALIST))
(REDATA (CDR ALIST))) )
)
))
Замечание. В версии muLISP85 функции ASSOC и RASSOC модифицируются следующим образом.
Функция (ASSOC KEY A-LIST TEST) выполняет линейный поиск в ассоциативном списке A-LIST точечной пары, для которой при сравнении ее CAR-элемента с ключом KEY по тесту TEST приэнак не равен NIL. Если тест-аргумент равен NIL или не задан, то функция ASSOC использует EQL-тест.
Функция (ASSOC-IF TEST A-LIST) ищет в ассоциативном списке A-LIST точечную пару, для которой признак проверки ее CAR-элемента по тесту TEST не есть NIL.
Для обоих функций справедливо следующее: если точечная пара, удовлетворяющая тесту, найдена, эта пара выдается; иначе возвращается NIL. Например:
$ (SETQ CAPITALS '((USA .WASHINGTON) (FRANCE . PARIS) (JAPAN . TOKYO))) ((USA .WASHINGTON) (FRANCE . PARIS) (JAPAN . TOKYO)) $ (ASSOC 'FRANCE CAPITALS) (FRANCE . PARIS) $ (ASSOC 'AUSTRALIA CAPITALS) NIL
Функцию можно определить так:
(DEFUN ASSOC (KEY ALIST TEST)
( (ATOM ALIST) NIL )
( (ATOM (CAR ALIST)) (ASSOC KEY (CDR ALIST) TEST) )
( ( (NULL TEST) (SETQ TEST 'EQL) ) )
( (FUNCALL TEST KEY (CAAR ALIST)) (CAR ALIST) )
( ASSOC KEY (CDR ALIST) TEST)
)
Функция (RASSOC KEY A-LIST TEST) выполняет линейный поиск в ассоциативном списке A-LIST точечной пары, для которой при сравнении ее CDR-элемента с ключем KEY по тесту TEST признак не равен NIL. Если тест-аргумент есть NIL или не задан, то функция RASSOC использует EQL-тест.
Функция (RASSOC-IF TEST A-LIST) выполняет в ассоциативном списке поиск пары, для которой признак проверки ее CDR-элемента по тесту TEST не равен NIL.
Для обеих функций справедливо следующее: если пара, удовлетворяющая тесту, найдена, эта пара возвращается; в противном случае возвращается NIL. Например:
$ (RASSOC 'PARIS CAPITALS) (FRANCE . PARIS) $ (RASSOC 'CANBERRA CAPITALS) NIL
Функцию можно определить так:
(DEFUN RASSOC (KEY ALIST TEST)
( (ATOM ALIST) NIL )
( (ATOM (CAR ALIST)) (RASSOC KEY (CDR ALIST) TEST) )
( ( (NULL TEST) (SETQ TEST 'EQL) ) )
( (FUNCALL TEST KEY (CDAR ALIST)) (CAR ALIST) )
( RASSOC KEY (CDR ALIST) TEST )
)
На следующем шаге мы рассмотрим список свойств.
