Adloun

Listes et filtrage

Cours · OCaml (option informatique), chapitre 2 · prépas MPSI et MP, option informatique · le début du chapitre, la suite sur Adloun

Une liste : des valeurs rangées dans l'ordre, repérées par un indice qui commence à 0.

2.1 Introduction et motivation

Le chapitre précédent manipulait des valeurs isolées — un entier, un booléen, un couple. Pour calculer sérieusement, il faut des collections : une suite de notes, les sommets d'un graphe, les caractères d'un mot. En OCaml, la structure de donnée fondamentale est la liste — non par hasard, mais parce qu'elle épouse exactement le style du langage : on la construit et on l'inspecte par filtrage, et on la parcourt par récursion.

Ce chapitre est doublement central. D'une part il introduit la liste, omniprésente jusqu'à la fin du cours. D'autre part il présente le filtrage par motifs (match), le mécanisme qui, en OCaml, remplace à lui seul la plupart des if imbriqués : on décrit la forme de la valeur examinée, et le compilateur vérifie qu'aucun cas n'a été oublié. On rencontrera aussi le type option, manière propre et sûre de modéliser l'absence de résultat — l'équivalent honnête du None de Python, mais contrôlé par le typeur.

2.2 Le type liste

Une liste OCaml est une suite finie, ordonnée et homogène de valeurs : tous ses éléments ont le même type. Une liste d'entiers a le type int list, une liste de booléens bool list, etc.


# [1; 2; 3];;
- : int list = [1; 2; 3]
# ["a"; "b"];;
- : string list = ["a"; "b"]
# [];;
- : 'a list = []
Attention

Les éléments sont séparés par des points-virgules ;, pas par des virgules. [1, 2, 3] n'est pas une erreur de syntaxe mais un piège : la virgule y forme un n-uplet, si bien que [1, 2, 3] est une liste à un seul élément, le triplet (1, 2, 3) — de type (int * int * int) list. Une liste homogène d'entiers s'écrit [1; 2; 3].

2.2.1 Les deux constructeurs

Toute liste est bâtie à partir de deux constructeurs seulement :

Définition 2.1Constructeurs des listes
  • [] (« liste vide », lu nil) : la liste sans aucun élément ;
  • :: (« cons ») : x :: r est la liste dont le premier élément (la tête) est x et dont le reste (la queue) est la liste r.

La notation [1; 2; 3] n'est qu'un sucre syntaxique pour 1 :: 2 :: 3 :: []. L'opérateur :: associe à droite, donc 1 :: (2 :: (3 :: [])).


# 1 :: [2; 3];;
- : int list = [1; 2; 3]
# 0 :: 1 :: 2 :: [];;
- : int list = [0; 1; 2]
iRemarque

:: ajoute un élément en tête, en temps constant, sans modifier la liste de départ : les listes sont immuables. x :: r ne « change » pas r ; elle construit une nouvelle liste qui partage r comme queue. On ne peut pas, en revanche, ajouter efficacement en fin de liste : c'est la tête qui est le point d'accès naturel.

2.3 Le filtrage par motifs

Pour examiner une valeur selon sa forme, OCaml offre le filtrage (pattern matching) :

Exercices du chapitre

La suite du cours · Tous les exercices du chapitre