Une suite de paires

Les listes Common Lisp sont construites à partir d'éléments plus simples que l'on appelle des paires (ou cons, du nom de la fonction qui les crée). Une paire comprend deux cellules de mémoire successives contenant chacune un (pointeur sur) un objet Common Lisp. Nous allons dessiner les paires comme indiqué dans la figure 8.1.

**Figure 8.1:** Représentation graphique d'une paire
$\begin{figure}\begin{center} \input paire.pstex_t \end{center} \end{figure}$

Par convention, la première cellule contient un élément de la liste et la deuxième une autre liste (potentiellement vide). De cette manière, il est possible de construire une liste par chaînage de la deuxième cellule de chaque paire (voir figure 8.2).

**Figure 8.2:** Chaînage de paires
$\begin{figure}\begin{center} \input liste.pstex_t \end{center} \end{figure}$

Pour des raisons historiques, la première cellule de la paire s'appelle le car et la deuxième s'appelle le cdr (prononcé coudère). Pour indiquer la fin de la liste, le cdr de la dernière paire est le symbole nil (voir figure 8.3).

**Figure 8.3:** Liste terminée par nil
$\begin{figure}\begin{center} \input liste2.pstex_t \end{center} \end{figure}$

Pour simplifier les figures, on dessine souvent une barre diagonale à la place de nil comme indiqué dans la figure 8.4.

**Figure 8.4:** Liste terminée par une barre diagonale
$\begin{figure}\begin{center} \input liste3.pstex_t \end{center} \end{figure}$

Les éléments d'une liste peuvent être des objets Common Lisp arbitraires. Voici par exemple une liste de trois éléments dont le premier élément est l'entier 52, le deuxième la chaîne de caractères "bonjour" et le troisième le flottant 1.234 (figure 8.5).

**Figure 8.5:** Liste à trois éléments
$\begin{figure}\begin{center} \input liste4.pstex_t \end{center} \end{figure}$

Les éléments d'une liste peuvent aussi être d'autres listes, ce qui donne des listes imbriquées. L'exemple de la figure 8.6 montre une liste dont le premier et le troisième élément sont des entiers et le deuxième est une liste de deux flottants.

**Figure 8.6:** Listes imbriquées
$\begin{figure}\begin{center} \input liste5.pstex_t \end{center} \end{figure}$

Irene DURAND
2011-10-14