Retour au sommaire.

En programmation impérative, il existe une structure de données basique, permettant de coder une collection d'éléments simplement, en l'absence de besoin de fonctionnalités avancées tel qu'effectuer des recherches efficaces, gérés des ordres, etc. Il s'agit des tableaux, et leur utilisation suffit dès lors qu'il s'agit juste de gérer une collection de valeurs indistinctes, qui seront traitées globalement.

Il n'y a pas de tableau en programmation fonctionnelle. Les tableaux sont directement des blocs contigüs de mémoire, mais la mémoire est une notion bas-niveau qui n'apparait pas en programmation fonctionnelle. En revanche, les langages fonctionnels proposent aussi une structure de données simple qui recouvre une partie des fonctionnalités des tableaux : les listes.

Une liste est une séquence d'éléments. Par séquence, nous entendons que les éléments sont rangés de façon linéaire, chaque élément est avant un autre élément, et après encore un autre élément (sauf les extrémités). Il y a donc un premier élément, un deuxième élément, un troisième élément, etc. Le premier élément est considéré être à gauche (par convention), le dernier à droite. Le premier élément est aussi appelé la tête de la liste.

Contrairement aux tableaux, les listes se manipulent uniquement par leur extrémité gauche. Accéder au $n$^e élément d'une liste demande $n$ étapes élémentaires. De même, l'insertion d'éléments ne peut se faire qu'en tête de la liste. En ce sens, les listes sont à rapprocher des piles des langages impératifs, si ce n'est que les listes sont persistentes. Ainsi, les listes admettent trois opérations de bases :

• l'ajout d'un élément en tête se fait par le constructeur de liste (::) : 'elt -> 'elt list -> 'elt list. Comme indiqué par le type, (::) prend comme terme gauche un élément et comme terme droit une liste d'éléments du même type. De plus, (::) est associatif à droite, de sorte que one::two::list se comprend comme one::(two::list), ce qui permet de ne pas avoir besoin de parenthéser les expressions de construction de liste.

  1. let list1 = [1;2;3;4]
     
  2. let list2 = 0 :: list1 (* = [0;1;2;3;4] *)
     
• l'obtention de l'élément de tête se fait par la fonction List.hd (hd pour HeaD). À condition que la liste soit non-vide.

  1. let zero = List.hd list2
     
  2. let one = List.hd list1
     
  3. let will_raise_an_exception = List.hd []
     
• il est tentant de décrire la troisième opération comme une suppression de l'élément de tête, mais ce n'est pas correct : comme nous l'avons expliqué une instance d'une structure de données ne peut pas être modifiée. Il s'agit plus précisément d'extraire la liste de tous les éléments après la tête, ce qu'on appelle la queue de la liste (pensez au serpent). La fonction List.tl : 'elt list -> 'elt list (pour TaiL) extrait la queue d'une liste.

  1. let list1_again = List.tl list2 (* = [1;2;3;4] *)
     
  2. let list3 = List.tl list1 (* = [2;3;4] *)
     
  3. let will_raise_an_exception = List.tl []
     

Ajoutons que la liste vide est notée [], et que l'expression e1::e2::e3::...::en::[] peut s'écrire plus simplement [e1;e2;e3;...;en]

List.hd et List.tl ne sont pas définies si la liste est vide. en pratique, prendre la tête ou la queue d'une liste vide provoque une exception, donc une erreur, lors de l'exécution du programme. Il faut donc systématiquement vérifier si la liste est non-vide avant d'utiliser ces fonctions, en comparant à la liste vide

Grâce à ces fonctions élémentaires, nous pouvons écrire tous les algorithmes possibles sur les listes. Notamment en manipulant les listes avec des fonctions récursives, comme dans l'exemple précédent. Mais ce n'est pas une bonne solution.

• nous avons dit que List.hd et List.tl provoquent des exceptions sur la liste vide. Il est malheureusement trop facile d'oublier de tester le cas spécial, et donc ce style de programmation encourage les erreurs, donc est à éviter.

• le style récursif n'est pas non plus évident, il faut vérifier les cas de bases, les conditions de terminaisons, la complexité. Le style à boucle de la programmation impérative n'est pas mieux loti.

• l'usage veut que la plupart des opérations que nous programmons avec des listes sont les mêmes. Il est inutile de les réécrire à chaque fois, nous devrions en faire des fonctions suffisamment générales pour être réutilisables dans la plupart des applications. Avec l'expérience, les opérations les plus courantes ont été identifiées et classifiées en quelques fonctions. L'usage d'arguments fonctionnels permet effectivement de factoriser des fonctions une fois pour toute, et nous allons maintenant apprendre à raisonner sur les listes en terme de ces fonctions générales.

Remarques sur les bibliothèques de listes.

Dans la suite de ce cours, nous donnerons les fonctions du module List de la librairie standard, ainsi que les fonctions équivalentes du module Core.Std.List, de la librairie alternative Core.Std. Pour utiliser Core.Std dans un toplevel, il faut utiliser les directives :

Notons que depuis l'écriture de ce cours, Core a un peu évolué, mais le cours n'est pas à jour. En particulier, toutes les fonctions de listes nécessitant de tester l'égalité d'un élément prennent dorénavant explicitement un prédicat d'égalité, via un argument nommé equal (l'égalité polymorphe, utilisée par défaut, est une cause notoire de perte d'efficacité en OCaml, il est donc préférable de ne pas l'utiliser pour les applications ayant un impératif de performance).

Core.Std.List définit plus de fonctions, et avec plus de cohérence que la librairie standard. Mais l'utilisation des deux librairies est très similaire, comprendre l'une, c'est comprendre l'autre. Core.Std.List réutilise les noms des fonctions de la librairie standard, c'est donc facile de passer de l'une à l'autre. Cela illustre aussi que les opérations que nous allons introduire sont universelles, quasiment toutes les fonctions que nous allons voir sont définies dans toutes les librairies de listes de tous les langages fonctionnels.

Retour au sommaire.