Résumé du chapitre 7

Listes 


Ce chapitre a été l'occasion de rencontrer une structure de données composée (non atomique) : le type Liste. Il permet de représenter tous les types définis par produit cartésien.

Les éléments du produit cartésien A_1xA_2x...xA_n peuvent être représentés par des listes dont le premier élément est dans A_1, le second dans A_2, ..., le dernier dans A_n.

L'ensemble de toutes les listes est défini par

Liste = (U(n=1 a l'infini)Objet^n )U nil

nil désigne la liste vide.

En SCHEME, on représente les listes entre parenthèses, les éléments sont séparés par des espaces. Pour exprimer une constante de type Liste, il est nécessaire de la précéder du quote. Cela permet de faire la distinction entre une telle constante et une expression composée.

Les opérateurs de manipulation des listes comme structure permettant de définir des produits cartésiens sont :

Remarquant que les produits cartésiens ne permettent de définir que des objets composés dont la structure est de taille finie et connue par avance, nous avons montré que les listes fournissent également la possibilité de manipuler des données composées de taille non connue a priori. Cela nous a amené à considérer les listes comme structure récursive.

Abstraitement, une liste peut être définie par :

Cette définition est récursive car le second point fait appel à la notion de liste elle-même.

Une liste se construit par ajout en tête d'éléments à partir de la liste vide.

En SCHEME, un élément de type Liste est :

Fonctions de base sur les listes

Prédicats
Test de typage : list?
Test de vacuité : null?
Constructeur
Accès aux éléments

Nous avons également vu comment définir par abstraction un type : cela consiste en la définition par construction du type en spécifiant les différents opérateurs manipulant ses données et sans tenir compte de la moindre implémentation.


next up previous
Next: Résumé du chapitre 9 Up: No Title Previous: Résumé du chapitre 6

Eric.Wegrzynowski
Thu Mar 20 13:58:10 MET 1997