Concaténation

Une opération fondamentale sur les listes est la concaténation de deux listes. La fonction de concaténation s'appelle append :

* (append '(a b) '(1 2))

(A B 1 2)
*

Cette fonction ne modifie pas ses arguments. Elle calcule une troisième liste contenant les éléments de la première liste suivis de ceux de la deuxième. C'est donc une fonction sans effet de bord. Exemple :

* (defparameter *l1* '(a b))

*L1*
* (defparameter *l2* '(1 2))

*L2*
* *l1*

(A B)
* *l2*

(1 2)
* (append *l1* *l2*)

(A B 1 2)
* *l1*

(A B)
* *l2*

(1 2)
*

Ici on remarque que la valeur des deux variables *l1* et *l2* n'a pas changé. Pour ce résultat, la fonction append copie les cellules de la première liste (voir la figure 8.7).

Figure 8.7: Fonctionnement de append

La fonction append prend un nombre arbitraire d'arguments, y compris zéro. Toutes les listes sauf la dernière seront copiées :

* (append)

NIL
* (append '(a b c))

(A B C)
* (append '(a b c) '(d e f) '(g h i))

(A B C D E F G H I)
*

Le dernier argument n'est pas forcément une liste, mais peut être n'importe quel objet Common Lisp, auquel cas une liste généralisée est renvoyée :

* (append '(a b c) "bonjour")

(A B C . "bonjour")
* (append "bonjour")

"bonjour"
* (append '(a) '() '(c) #c(1 1))

(A C . #C(1 1))
*

Le fait que append copie toutes les listes (sauf la dernière) garantit l'absence d'effet de bord, ce qui facilite considérablement la mise au point du programme. Par contre, l'efficacité peut être compromise par la création de nouvelles cellules pour ces listes.

Parfois, l'application n'a pas besoin de l'ancienne valeur de ces listes. Il est donc raisonnable de réutiliser les cellules. Pour ce cas, Common Lisp propose une version destructive de append : nconc. C'est une convention souvent (mais pas toujours) respectée en Common Lisp que les fonctions dont le nom commence par la lettre `n' sont des fonctions destructives.

L'utilisation de fonctions destructives est extrêmement délicate. D'abord, il faut s'assurer que l'application n'a plus besoin de l'ancienne valeur de la liste détruite. De plus, il est interdit de se servir d'une liste créée par quote dans un contexte où elle risque d'être détruite. Pire, l'implémentation de Common Lisp n'est pas obligée de détecter ce type d'utilisation, ce qui donne des défauts (en Anglais : bugs) très difficiles à trouver.

Voici un exemple d'utilisation de nconc :

* (defparameter *l* (list 'a 'b 'c))

*L*
* *l*

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

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

(A B C 1 2 3)
*

On remarque que la valeur de *l* change après application de nconc. En fait, nconc parcourt toutes les listes sauf la dernière, puis remplace le cdr de la dernière cellule par un pointeur sur le début de la liste suivante.

Exercice : Pourquoi est-ce que la valeur de *ll* ne change pas dans l'exemple suivant :

* (defparameter *ll* '())

*LL*
* *ll*

NIL
* (nconc *ll* '(1 2 3))

(1 2 3)
* *ll*

NIL
*

Une erreur classique lors de l'utilisation de fonctions destructives est de détruire la valeur renvoyée par une fonction alors que cette fonction construit la valeur avec quote. Le résultat de cette opération n'étant pas défini par la norme Common Lisp, il peut varier d'une implémentation à une autre. Voici ce qui peut arriver en CMU Common Lisp :

* (defun f () '(a b c))

F
* (f)

(A B C)
* (nconc (f) '(1 2 3))

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

(A B C 1 2 3)
*