Listes
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
où 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 :
Ces fonctions ne s'appliquent évidemment pas à la liste vide.
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.
