common-lisp
Types de listes
Recherche…
Listes simples
Les listes simples sont le type de liste le plus simple dans Common Lisp. Ils sont une séquence ordonnée d'éléments. Ils prennent en charge les opérations de base telles que l'obtention du premier élément d'une liste et le reste d'une liste en temps constant, prennent en charge l'accès aléatoire en temps linéaire.
(list 1 2 3)
;=> (1 2 3)
(first (list 1 2 3))
;=> 1
(rest (list 1 2 3))
;=> (2 3)
Il existe de nombreuses fonctions qui fonctionnent sur des listes "simples", dans la mesure où elles ne concernent que les éléments de la liste. Celles-ci incluent find , mapcar et bien d'autres. (Bon nombre de ces fonctions fonctionneront également sur les concepts de séquence 17.1 pour certaines de ces fonctions.
Listes d'association
Les listes simples sont utiles pour représenter une séquence d'éléments, mais il est parfois plus utile de représenter une sorte de clé pour valoriser le mappage. Common Lisp propose plusieurs méthodes pour y parvenir, y compris de véritables tables de hachage (voir 18.1 Concepts de table de hachage ). Il existe deux manières principales ou représentant des mappages de valeur dans Common Lisp: les listes de propriétés et les listes d'associations . Cet exemple décrit les listes d'associations.
Une liste d'associations, ou alist est une liste "simple" dont les éléments sont des paires en pointillés dans lesquelles la voiture de chaque paire est la clé et le cdr de chaque paire est la valeur associée. Par exemple,
(defparameter *ages* (list (cons 'john 34) (cons 'mary 23) (cons 'tim 72)))
peut être considéré comme une liste d'associations qui mappe des symboles indiquant un nom personnel avec un entier indiquant l'âge. Il est possible d'implémenter des fonctions de récupération en utilisant des fonctions de liste simples, comme member . Par exemple, pour retrouver l’âge de John , on pourrait écrire
(cdr (first (member 'mary *age* :key 'car)))
;=> 23
La fonction membre retourne la queue de la liste en commençant par une cellule cons dont la voiture est Marie, qui est, ((Mary. 23) (tim. 72)), premier renvoie le premier élément de la liste, qui est (Marie. 23) , et cdr renvoie le côté droit de cette paire, qui est 23 . Bien qu'il s'agisse d'un moyen d'accéder à des valeurs dans une liste d'associations, une convention comme les listes d'associations a pour but de s'abstraire de la représentation sous-jacente (une liste) et de fournir des fonctions de plus haut niveau.
Pour les listes d'association, la fonction de récupération est assoc , qui prend une clé, une liste d'association et des mots-clés de test facultatifs (clé, test, test-not) et renvoie la paire pour la clé correspondante:
(assoc 'tim *ages*)
;=> (tim . 72)
Étant donné que le résultat sera toujours une contre-cellule si un élément est présent, si assoc renvoie un résultat nul , l'élément ne figurait pas dans la liste:
(assoc 'bob *ages*)
;=> nil
Pour mettre à jour les valeurs d'une liste d'associations, setf peut être utilisé avec cdr . Par exemple, lorsque l’anniversaire de John arrive et que son âge augmente, l’une des actions suivantes peut être effectuée:
(setf (cdr (assoc 'john *ages*) 35)
(incf (cdr (assoc 'john *ages*)))
incf fonctionne dans ce cas car il est basé sur setf .
Les listes d'association peuvent également être utilisées comme type de carte bidirectionnelle, car les mappages de clé à valeur doivent être récupérés en fonction de la valeur à l'aide de la fonction d'assoc inversée, rassoc .
Dans cet exemple, la liste des associations a été créée en utilisant list et cons explicitement, mais les listes d'associations peuvent également être créées à l'aide de pairlis , qui prend une liste de clés et de données et crée une liste d'associations:
(pairlis '(john mary tim) '(23 67 82))
;=> ((john . 23) (mary . 67) (tim . 82))
Une seule clé et une paire de valeurs peuvent être ajoutées à une liste d'associations à l'aide d' acons :
(acons 'john 23 '((mary . 67) (tim . 82)))
;=> ((john . 23) (mary . 67) (tim . 82))
La fonction assoc parcourt la liste de gauche à droite, ce qui signifie qu'il est possible de "masquer" des valeurs dans une liste d'association sans les supprimer d'une liste ni mettre à jour la structure de la liste, simplement en ajoutant de nouveaux éléments à la liste. début de la liste. La fonction acons est fournie pour cela:
(defvar *ages* (pairlis '(john mary tim) '(34 23 72)))
(defvar *new-ages* (acons 'mary 29 *ages*))
*new-ages*
;=> ((mary . 29) (john . 34) (mary . 23) (tim . 72))
Et maintenant, une recherche pour Mary retournera la première entrée:
(assoc 'mary *new-ages*)
;=> 29
Listes de propriété
Les listes simples sont utiles pour représenter une séquence d'éléments, mais il est parfois plus utile de représenter une sorte de clé pour valoriser le mappage. Common Lisp propose plusieurs méthodes pour y parvenir, y compris de véritables tables de hachage (voir 18.1 Concepts de table de hachage ). Il existe deux manières principales ou représentant des mappages de valeur dans Common Lisp: les listes de propriétés et les listes d'associations . Cet exemple décrit des listes de propriétés.
Une liste de propriétés, ou plist , est une liste "simple" dans laquelle les valeurs alternées sont interprétées comme des clés et leurs valeurs associées. Par exemple:
(defparameter *ages* (list 'john 34 'mary 23 'tim 72))
peut être considéré comme une liste de propriétés qui mappe des symboles indiquant un nom personnel avec un entier indiquant l'âge. Il est possible d'implémenter des fonctions de récupération en utilisant des fonctions de liste simples, comme member . Par exemple, pour retrouver l’âge de John , on pourrait écrire
(second (member 'mary *age*))
;=> 23
La fonction membre renvoie la fin de la liste en commençant par mary , c'est-à-dire (Mary 23 tim 72) , et second renvoie le deuxième élément de cette liste, à savoir 23 . Bien qu'il s'agisse d'une façon d'accéder aux valeurs dans une liste de propriétés, le but d'une convention comme les listes de propriétés est de s'abstraire de la représentation sous-jacente (une liste) et de fournir des fonctions de plus haut niveau.
Pour les listes de propriétés, la fonction de récupération est getf , qui prend la liste de propriétés, une clé (plus communément appelée indicateur ) et une valeur par défaut facultative à renvoyer si la liste de propriétés ne contient pas de valeur pour la clé.
(getf *ages* 'tim)
;=> 72
(getf *ages* 'bob -1)
;=> -1
Pour mettre à jour les valeurs dans une liste de propriétés, setf peut être utilisé. Par exemple, lorsque l’anniversaire de John arrive et que son âge augmente, l’une des actions suivantes peut être effectuée:
(setf (getf *ages* 'john) 35)
(incf (getf *ages* 'john))
incf fonctionne dans ce cas car il est basé sur setf .
Pour rechercher plusieurs propriétés dans une liste de propriétés, utilisez get-properties .
La fonction getf parcourt la liste de gauche à droite, ce qui signifie qu'il est possible de "masquer" des valeurs dans une liste de propriétés sans les supprimer d'une liste ni mettre à jour la structure de la liste. Par exemple, en utilisant la liste * :
(defvar *ages* '(john 34 mary 23 tim 72))
(defvar *new-ages* (list* 'mary 29 *ages*))
*new-ages*
;=> (mary 29 john 34 mary 23 tim 72)
Et maintenant, une recherche pour Mary retournera la première entrée:
(getf *new-ages* 'mary)
;=> 29
