Examining the physical form of representation of lists, we already marked, that a dotted pair, or a list cell, consists of two parts: first fields and rest. Any object (atom, the character, other list, a vector, the object etc.) can be value of the field. The list can be defined through nil and list pair as follows:
Thus the list is the chain of list cells linked through the rest field which in the field rest the last cell contains nil. first fields of these cells represent list units.
The set of operations with lists derivates the main mechanism of data representation in a Lisp with which help it is possible to build the big complexes of data of objects of various types. Any object can be a list unit the same as also a value. Using lists, it is possible to define new types and data structures.
The association list or simply a-list is the data structure often used in a Lisp and grounded on lists and dotted pairs, for operation with which there are ready functions. The association list consists of dotted pairs, therefore it also name as the list of pairs:
((a1 . t1) (a2 . t2) … (an . tn))
The first unit of pair name as a key and the second (rest) - the data linked to a key. Usually a key is the symbol. The data linked to it can be symbols, lists or any other objects. By means of a-list it is possible to unite the varied components of data named by keys in the uniform complex of data.
In operation with lists of pairs it is necessary to know how to build lists, to search data on a key and to refresh them.
By means of the intrinsic function pairlist it is possible to build the-list of the list of keys and the list generated from data corresponding to them. The object is the old a-list in which beginning new pairs are added:
(a-list pairlist keys data)
Let's give an example:
>('dictionary set '((one . 1))) ((one . 1)) >('dictionary set (dictionary pairlist '(three two) '(3 2))) ((three . 3) (two . 2) (one . 1))
pairlist it would be possible to define as follows:
(nil defmethod pairlist (keyl datal) (nil if keyl (nil cons (nil cons (keyl first) (datal first)) (this pairlist (keyl rest) (datal rest))) this))
It is possible to consider the association list as mapping from set of keys in a range. Data it is possible to receive by means of function
(a-list assoc key)
Which searches in the list of pairs given corresponding to a key, comparing a required key with keys of pairs from left to right. assoc it would be possible to define (simply) as follows:
(nil defmethod assoc ()) ('cons defmethod assoc (a) (nil if (a = ((this first) first)) (this first) ; value - pair entirely ((this rest) assoc a)))
>(dictionary assoc 'two) (two . 2) >('cons defmethod value (word) ((this assoc word) rest)) (lambda (word) ((this assoc word) rest))) >(dictionary value 'two) 2
Notice, that as value assoc returns pair entirely, and not just required data, or nil if the key is not present. There is still a function rassoc (return assoc) which searches for a key on the set data.
The association list can be refreshed and used in stack regulations. New pairs are added to it only in the list beginning though in the list there can be data with the same key. It is carried out by function acons:
(nil acons x y a-list) ≡ (nil cons (nil cons x y) a-list)
As assoc views the list from left to right and reaches only first pair with a required key older pairs as though remain in a shade newer. A-lists used thus well solve, for example, a problem of support of varying links of variables and a calculation context.
Advantage of such usage is simplicity of change of links and possibility of return to values of old links. Disadvantage is that the data retrieval is decelerated proportionally to length of the list.
If old value any more is not required, a-list can be changed, physically having changed the data linked to a key. It can be made, for example, changing value of rest field pseudo-function setrest:
((a-list assoc key) setrest new-value)
The given way to change value of the field needs to be used very accurately that there were no problems with other parts of the program which data in the pure state as can transfer the list.