TD/TP n°3 : Inside list world

1. cons, car, cdr et list

Une expression du langage Lisp est soit un atome, soit une liste d'expressions. Une liste d'expressions est faite de 0, 1 ou plusieurs expressions entre parenthèses.

La liste la plus élémentaire est la liste vide, notée ( ) ou encore nil.
> ( )
NIL
Toute autre liste peut être représentée comme une paire de deux cellules, la première cellule s'appelle le car et la deuxième le cdr. La fonction cons permet de construire une paire : ses deux paramètres correspondent alors au car et cdr de la paire ainsi construite.
> (cons 'a 'b)
(A . B)
> (setq L1 (cons 'a 'b))
(A . B)
> L1
(A . B)
> (car L1)
A
> (cdr L1)
B
La liste (a . (b . c)) est notée plus simplement (a b . c). Cette règle de simplification est récurrente, ainsi (a . (b . (c . d))) est notée (a b c . d). Par contre elle n'est pas symétrique (sinon elle serait ambigüe) et (((a . b) . c) . d) ne sera pas simplifiée.

Par ailleurs, une paire dont le cdr est nil sera simplifiée de la manière suivante : (a . nil) s'écrit (a).

La fonction list correspond à la création d'une liste contenant dans l'ordre ses arguments, suivis de nil.
(list 'a 'b 'c) correspond donc à (cons 'a (cons 'b (cons 'c nil))) et vaut (a b c).

Des fonctions composées existent et permettent d'invoquer car ou cdr jusqu'à 4 fois successivement.
Exemple : (cdddr L1) correspond à (cdr (cdr (cdr L1))).

Exercice 1 :
Evaluer les expressions suivantes et comprendre le résultat obtenu.
> (setq l2 (cons 'a (cons "bonjour" (cons 2 (cons 'd nil))))) ; faire la même construction avec la fonction list uniquement
> (car (cdr (cdr l2)))
Faire la construction d'une liste L2 telle que l'évaluation de (caaaar L2) renvoie (a), en n'utilisant que setq et cons, puis en n'utilisant que setq et list.
Il existe d'autres fonctions de base sur les listes appelées first, last et rest. Ces fonctions s'utilisent avec un argument de type liste. Comparer les avec les fonctions car et cdr, en évaluant des constructions qui les font intervenir.

2. Fonctions supplémentaires

Exercice 2 :
Fusionner des listes crées précédemment. Tester la fonction append avec des listes dont le dernier élément n'est pas nil. Que ce passe-t-il dans ce cas ? Exercice 3 :
Calculer la longueur de listes précédemment construites. On fera des évaluations pour des listes dont le dernier élément est nil et d'autres pour lesquelles le dernier élément ne vaut pas nil. Que remarque-t-on ? Exemple : (nth 3 L3) renvoie le 3ème élément de la liste L3.
Exercice 4 :
Tester nth et last sur des listes crées précédemment. Tester avec des listes dont le dernier élément est nil et d'autres dont le dernier élément n'est pas nil.
> (member 'a '(b c a d e))
(a d e)
Mapping
Les fonctions suivantes ont un premier argument qui est une fonction f et un deuxième argument qui est une liste. Eventuellement elles ont également d'autres arguments qui sont des listes si f est une fonction à plusieurs arguments.
Pour plus d'information sur ces fonctions, vous pouvez consulter le chapitre sur les fonctions d'application du  Traité de programmation en Common Lisp de R. Strandh et I. Durand.

Exercice 5 :
Tester ces 6 fonctions pour f prenant les valeurs car puis cdr et sur l'argument liste '((a b) (c d) (e f)).

Fonctions de remplacement physique dans des listes

Exercice 6 :
Evaluer les expressions suivantes et comprendre les résultats retournés
> (setq a '(a b c))
> (setq b a)
> (rplaca b '(c d))
> a
> (rplacd b '(e f))
> a  
Que fait la fonction reverse qui possède un seul argument de type list ?

3. Exercices d'application

Exercice 7 :
Ecrire une fonction qui calcule la concaténation de deux listes.
 
Exercice 8 :
Ecrire une fonction qui calcule le nombre d'éléments d'une liste.
 
Exercice 9 :
Ecrire une fonction qui effectue le tri d'une liste par insertion.
 
Exercice 10 :
Ecrire une fonction qui renvoie le dernier élément d'une liste.
 
Exercice 11 :
Ecrire une fonction qui ajoute 1 à chaque élément d'une liste d'entiers.
 
Exercice 12 :
Ecrire une fonction qui calcule la somme des éléments d'une liste d'entiers.

Exercice 13 :
Ecrire une fonction qui calcule le nombre d'occurence d'un symbole dans une liste.

Exercice 14 :
Ecrire une fonction qui remplace toutes les occurences d'un élément d'une liste par un autre élément.
 
Exercice 15 :
Ecrire une fonction qui extrait tous les éléments de rang pair d'une liste.
 
Exercice 16 :
Ecrire une fonction qui fusionne 2 listes ordonnées en une liste ordonnée.

Exercice 17 :
Ecrire une fonction qui fusionne 2 listes non ordonnées en une liste ordonnée.

Exercice 18 :
Ecrire une fonction qui a pour argument une liste et qui renvoie une liste de paires telles que ces dernières associent chaque symbole apparaissant dans la liste originale et son nombre d'occurence.