Vous avez écrit un programme pour calculer la moyenne de trois notes. Il est naturel de se demander comment faire pour calculer la moyenne de n notes. C'est ce que nous allons voir maintenant.
 
Deux notions importantes  
Notion de séquence en informatique  
Considérons le problème de la moyenne de n notes. La donnée d'un tel problème est une séquence finie de notes (en particulier s'il y a des coefficients).
 
Une telle séquence peut être vue de différentes façons:

• de façon complètement informelle comme la donnée de n₀, n₁,...,n_p-1;
• ce que l'on peut aussi noter n(0), n(1),... n(p-1): c'est une application de { 0, 1, 2,... p-1 } dans 0 .. 20 (nous verrons plus tard cette vision des séquences);
• mais on peut aussi la voir, d'une façon récursive, comme étant constituée par:
  • la première note,
  • et les autres notes qui constituent encore une séquence de notes (où il y a moins de notes que dans la séquence complète).
  
  Récursivement, on arrive alors à une séquence qui n'a qu'un élément et, pourquoi ne pas continuer, on arrive à la séquence qui n'a pas d'élément et que l'on nomme la séquence vide.

 
En Scheme, cette dernière vision des séquences est mise en oeuvre par la notion de liste (cf. la section suivante).
 
Notion de structures de données  
Jusqu'à présent, les données et les résultats des fonctions que nous avons étudiées étaient des entiers, des réels ou des booléens. Il s'agissait d'informations simples, même lorsque nous avons écrit une fonction qui calcule la moyenne de trois notes où nous manipulions trois informations simples, représentées par trois variables dans la définition de la fonction.
 
Pour calculer la moyenne de n notes, on ne peut pas écrire la définition d'une fonction qui aurait n variables représentant les n notes données: il faut que la donnée des n notes soit une (unique) donnée de la fonction. Mais alors cette donnée est constituée de plusieurs informations et, pour retrouver chacune d'elles, on doit structurer la donnée dans ce qu'on nomme une structure de données.
 
Encore faut-il pouvoir

• fabriquer une telle donnée structurée,
• retrouver les différentes informations présentes dans la donnée structurée.

 
Pour ce faire, on peut utiliser des fonctions que l'on nomme des fonctions de base:

• un constructeur (le type du résultat d'une telle fonction est la structure de données) permet de fabriquer une donnée structurée, éventuellement à partir d'une valeur structurée;
• un accesseur (le type de la donnée d'une telle fonction est la structure de données) permet de retrouver une information présente dans une donnée structurée, sous réserve que la donnée contienne une telle information;
• un reconnaisseur (le type de la donnée d'une telle fonction est la structure de données et son résultat est un booléen) permet de savoir quelle est la forme d'une donnée structurée, essentiellement pour savoir si on peut lui appliquer un accesseur.

 
 
Structure de données «liste»  
Une liste est une structure de données qui regroupe une séquence d'éléments de même type. Par exemple, la donnée de la fonction qui calcule la moyenne de n notes est une liste de nombres naturels.
 
Nous noterons LISTE[Note] (Note étant le type nat/<=20/) un tel type et la signature de la fonction est donc:  
 

 
D'une façon générale, nous noterons alpha, beta... ou a, b... un type quelconque (autrement dit, on pourra remplacer ces noms de type par n'importe quel type) et LISTE[alpha] une liste d'éléments de type alpha, LISTE[beta] une liste d'éléments de type beta... LISTE[a] une liste d'éléments de type a, LISTE[b] une liste d'éléments de type b...

Pour en savoir plus: « Listes »

Étudions maintenant les fonctions de base sur les listes (à savoir les constructeurs list et cons, les accesseurs car et cdr et le reconnaisseur pair?).
 
Constructeurs  
Pour construire une liste, on utilise la fonction list:  
 

 
Par exemple,  
(list 3 5 2 5) -> (3 5 2 5)
 
(list) -> ()  

 
On peut aussi construire une liste, à partir d'une autre liste, en utilisant la fonction cons:  
 

 
Par exemple:  
(cons 7 (list 3 5 2 5)) -> (7 3 5 2 5)
 
(cons 5 (cons 2 (cons 5 (list)))) -> (5 2 5)  

 
Noter la signature de la fonction cons

1. elle a deux données
   1. un élément de n'importe quoi (d'où le premier alpha),
   2. une liste (d'où LISTE[...]) de ce même n'importe quoi (d'où le deuxième alpha);
    
   
2. elle rend une liste (d'où le second LISTE[ ]) de ce même n'importe quoi (d'où le troisième alpha).

 
On peut aussi le dire autrement: dans la pratique, on a un certain type, nommons le alpha, et on veut construire une liste d'éléments de type alpha. Pour ce faire, on peut utiliser la fonction cons, avec comme premier argument un élément de type alpha et comme second argument une liste de type LISTE[alpha], le résultat étant de type LISTE[alpha].
 
Noter aussi la signature de la fonction list: c'est une fonction qui a un nombre quelconque d'arguments, tous du même type (d'où les points de suspension), le type étant quelconque (d'où le premier alpha) et elle rend une liste (d'où le LISTE[ ]) de ce même n'importe quoi (d'où le deuxième alpha).
 
Remarque: en fait, on n'a pas besoin du constructeur list, sauf pour construire la liste vide. En effet, par exemple,
(list 5 2 3) équivaut à (cons 5 (cons 2 (cons 3 (list))))
 

Pour en savoir plus: « Constructeurs de listes »

 
Accesseurs Le premier élément d'une liste non vide est donné par la fonction car:  
 

 
Par exemple:  
(car (list 3 5 2 5)) -> 3  

 
Le reste d'une liste non vide est donné par la fonction cdr:  
 

 
Par exemple:  
(cdr (list 3 5 2 5)) -> (5 2 5)  
Remarques:

• pour toute liste l et toute valeur x, on a
  1. (car (cons x l)) º x
  2. (cdr (cons x l)) º l
  
  qui est une propriété caractéristique des listes.
• pour toute liste non vide l, on a
   
  l º (cons (car l) (cdr l)).

 
 
Reconnaisseur  
Il faut aussi savoir si une liste n'est pas vide: ceci est possible grâce au prédicat pair?:  
 

 
Par exemple:  
(pair? (list 3 5 2 5)) -> #T
 
(pair? (list)) -> #F  

 
Exemples de définitions simples sur les listes  
Exemple 1: pour avoir le deuxième élément d'une liste donnée:  

;;; Essai:
 
(deuxieme (list 3 5 2 5)) -> 5  

 
Exemple 2: pour avoir le reste après le deuxième élément d'une liste donnée:  

;;; Essai:
 
(reste2 (list 3 5 2 5)) -> (2 5)  

 
Exemple 3: prédicat lg>1? pour déterminer si une liste donnée a au moins 2 éléments (par exemple (lg>1? (list 3)) --> false et (lg>1? (list 3 4)) --> true.  

Essais:
 
(lg>1? (list 3 5 2 5)) --> #t
 
(lg>1? (list)) --> #f
 
(lg>1? (list 3)) --> #f
 
(lg>1? (list 3 5)) --> #t  

 
Rappel: and est une forme spéciale (si le premier argument est faux, on n'évalue pas le second); indispensable ici car, lorsque la liste donnée est vide, (cdr L) donne une erreur.
 
Abréviations  
Abréviationscadr cdr  

 
En fait on devra souvent désigner le deuxième, troisième... élément d'une liste ou ce qui reste après le deuxième, troisième... élément d'une liste. Aussi Scheme a des abréviations qui permettent de désigner ces valeurs. La règle de formation de ces abréviations est très simple: on écrit « c », puis, éventuellement, un « a » puis des « d » et enfin un « r ». Par exemple, caddr est une telle abréviation. Une telle abréviation remplace une expression combinant des car et des cdr, le « a » correspondant à un car et un « d » correspondant à un cdr.
 
Par exemple  
Exemple: (caddr L) º (car (cdr (cdr L)))  

 
(caddr L) est une abréviation pour (car (cdr (cdr L))).
 
Remarque: on verra plus tard que l'on peut mettre d'autres a.