Listes pour représenter des ensembles

Une liste n'est pas une excellente façon de représenter un ensemble car plusieurs opérations de base sont inefficaces. Tester si un objet est élément d'un ensemble coûte $O(n)$ où $n$ est la taille de l'ensemble. La calcul de l'union, ou de l'intersection, entre deux ensembles coûte $O(n^2)$.

Mais pour des ensembles de petite taille, ces coûts sont souvent acceptables. De plus, Common Lisp propose plusieurs fonctions et macros pour la manipulation d'ensembles représentés par des listes. Il est donc facile pour le programmeur d'utiliser des listes, surtout dans une phase de prototypage.

La manipulation d'ensembles nécessite l'existence d'une fonction pour tester l'égalité de deux objets de l'ensemble. Cette fonction ne peut pas en général être déterminée par le langage de programmation, mais doit être fournie par le programmeur. Ceci se conçoit facilement en considérant des applications qui manipulent des personnes. Une application peut considérer deux personnes égales si elles ont le même numéro de sécurité sociale, un autre, si elles ont le même nom, etc.

Les fonctions Common Lisp qui manipulent des ensembles prennent donc un argument pour déterminer la fonction d'égalité à utiliser. Souvent, une telle fonction est la combinaison d'un accesseur (que nous appelons clé) et d'un test simple (comme eq, eql ou equal). Par exemple, si les objets de l'ensemble sont des personnes représentées par des listes dont le premier élément est le numéro de sécurité sociale, l'accesseur sera car et le test eql. Ceci explique que les fonctions Common Lisp qui manipulent des ensembles prennent trois paramètres de type mot-clé (voir section 6.3.3), le premier appelé key, le deuxième test et le troisième test-not. La valeur par défaut de l'argument key est la fonction identité. Au plus l'un des deux autres peut être fourni. Le test-not permet simplement d'éviter les négations. Si aucun des deux n'est fourni, c'est la fonction eql qui sera utilisée.

La fonction adjoin prend deux paramètres, un élément à rajouter et une liste représentant un ensemble, ainsi que les deux paramètres mots-clés indiqués ci-dessus. Elle renvoie une nouvelle liste représentant l'union entre le singleton et l'ensemble :

* (defparameter *l* '(((a) 1) ((b) 2) ((c) 3)))

*L*
* (adjoin '((b) 2) *l*)

(((B) 2) ((A) 1) ((B) 2) ((C) 3))
* (adjoin '((b) 2) *l* :test #'equal)

(((A) 1) ((B) 2) ((C) 3))
* (adjoin '((b) 2) *l* :key #'car)

(((B) 2) ((A) 1) ((B) 2) ((C) 3))
* (adjoin '((b) 2) *l* :key #'caar)

(((A) 1) ((B) 2) ((C) 3))
* (adjoin '((b) 2) *l* :key #'car :test #'equal)

(((A) 1) ((B) 2) ((C) 3))
*

La macro pushnew permet de modifier la valeur d'une variable (ou plus généralement une place) avec le résultat d'un appel à adjoin :

* (defparameter *l* '(((a) 1) ((b) 2) ((c) 3)))

*L*
* *l*

(((A) 1) ((B) 2) ((C) 3))
* (pushnew '((b) 2) *l* :key #'car)

(((B) 2) ((A) 1) ((B) 2) ((C) 3))
* *l*

(((B) 2) ((A) 1) ((B) 2) ((C) 3))
*

Les fonctions union et intersection sont utilisées pour calculer respectivement l'union et l'intersection de deux ensembles représentés par des listes. Les arguments sont les deux ensembles et les trois arguments mots-clés indiqués ci-dessus. Ces deux fonctions sont sans effet de bord.

Les deux fonctions nunion et nintersection sont des versions destructives de union et intersection. La fonction nunion peut modifier ses deux arguments et la fonction nintersection son premier argument.

La fonction set-exclusive-or (et sa version destructive nset-exclusive-or) renvoie l'ensemble des éléments figurant dans exactement un des deux ensembles donnés en arguments.

La fonction set-difference (et sa version destructive nset-difference) renvoie l'ensemble des éléments figurant dans le premier ensemble mais pas dans le deuxième.

La fonction subsetp permet de vérifier si un ensemble est sous-ensemble d'un autre ensemble.