Alists and Plists

One of the data-structures that even early LISP implementations possessed, were ‘plists‘. It was only by reading up on LISP lately, that I discovered that many LISP implementations maintained a hidden plist, in which certain Properties of Symbols were stored. This could easily have been found in the CIR of the Atom, the naming of which was later simplified to CDR. Alternatively, this plist could have been the only datum of the Symbol, hence stored at its CAR.

In short, this was an early associative list, consisting of Key:Value pairs, where the Key was supplied by the programmer, in order to retrieve the Value from the plist.

Plists were later superseded by ‘alists‘. An alist has a better storage format, but again stores Key:Value associations. One big advantage of an alist, is the ability to perform a reverse look-up, in which a sought Value is supplied, and the List of Keys returned, that point to this Value.

I think it is agreed, that Hash Tables eventually manage forward-look-ups better than either a plist or an alist, especially if large numbers of Keys are stored. Yet, it is written that for short collections of data, the simplicity with which an alist is stored, actually allows it to work more quickly than a Hash Table, in LISP.

Now, if it was necessary to perform reverse look-ups, yet the large number of objects require a Hash Table, then the most sensible approach might be to create two Hash Tables, one for the forward look-up, and another for the reverse look-up? In that case, if a Hash Table is predicted to serve a one-to-many relationship, then the care should also be taken from the beginning, to encapsulate all the value-sets that result from one Key, into Sets, even if in many cases, there may be only one element in the Set.

Alternatively a system could be devised, so that only one result from the reverse look-up is the correct one.