Listes et filtrage

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>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 = []

2.2.1 Les deux constructeurs

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

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

2.3 Le filtrage par motifs

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

match expression with
| motif_1 -> resultat_1
| motif_2 -> resultat_2
| ...

L'expression est confrontée aux motifs dans l'ordre ; le premier qui « colle » fournit le résultat. Sur une liste, deux motifs suffisent à tout couvrir : [] (la liste est vide) et x :: reste (elle a au moins un élément, de tête x et de queue reste).

let decrire l =
  match l with
  | [] -> "liste vide"
  | [x] -> "un seul élément"
  | x :: y :: _ -> "au moins deux éléments"

2.4 La récursion sur les listes

Comme une liste est, par construction, soit vide, soit « une tête suivie d'une queue (qui est une liste plus courte) », elle s'analyse naturellement par récursion, sur exactement ce découpage.

let rec longueur l =
  match l with
  | [] -> 0
  | _ :: reste -> 1 + longueur reste

let rec somme l =
  match l with
  | [] -> 0
  | x :: reste -> x + somme reste

2.5 Concaténation et coût

2.5.1 L'opérateur @

La concaténation @ met bout à bout deux listes de même type.

# [1; 2] @ [3; 4; 5];;
- : int list = [1; 2; 3; 4; 5]

On peut réécrire @ pour comprendre ce coût :

let rec concatene l1 l2 =
  match l1 with
  | [] -> l2
  | x :: reste -> x :: concatene reste l2

On voit que chaque élément de l1 provoque un :: : il y en a exactement la longueur de l1.

2.6 Le type option

Comment une fonction signale-t-elle « il n'y a pas de résultat » — la tête d'une liste vide, la recherche d'un absent ? En OCaml, on ne renvoie pas une valeur bidon : on emploie le type option.

let tete_option l =
  match l with
  | [] -> None
  | x :: _ -> Some x

# tete_option [10; 20];;
- : int option = Some 10
# tete_option [];;
- : int option = None

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>2.7 Exercices résolus

Niveau $\star$ (application directe du cours)

[true; false; true] ;;   1 :: 2 :: [] ;;   [3] @ [] ;;   [[1]; [2; 3]] ;;

- : bool list = [true; false; true]
- : int list = [1; 2]
- : int list = [3]
- : int list list = [[1]; [2; 3]]

let rec longueur l =
  match l with
  | [] -> 0
  | _ :: reste -> 1 + longueur reste

let rec produit l =
  match l with
  | [] -> 1
  | x :: reste -> x * produit reste

Niveau $\star \star$ (raisonnement intermédiaire)

let rec appartient x l =
  match l with
  | [] -> false
  | t :: reste -> x = t || appartient x reste

let rec dernier l =
  match l with
  | [] -> failwith "liste vide"
  | [x] -> x
  | _ :: reste -> dernier reste

let rec indice x l =
  match l with
  | [] -> None
  | t :: reste ->
      if x = t then Some 0
      else
        match indice x reste with
        | None -> None
        | Some i -> Some (i + 1)

let rec concatene l1 l2 =
  match l1 with
  | [] -> l2
  | x :: reste -> x :: concatene reste l2

Niveau $\star \star \star$ (approfondissement)

let rec renverse_naif l =
  match l with
  | [] -> []
  | x :: reste -> renverse_naif reste @ [x]

let renverse l =
  let rec aux acc l =
    match l with
    | [] -> acc
    | x :: reste -> aux (x :: acc) reste
  in
  aux [] l

let rec nb_occ x l =
  match l with
  | [] -> 0
  | t :: reste ->
      if t = x then 1 + nb_occ x reste
      else nb_occ x reste

let rec maximum l =
  match l with
  | [] -> failwith "liste vide : pas de maximum"
  | [x] -> x
  | x :: reste ->
      let m = maximum reste in
      if x > m then x else m

2.8 Exercices d'entraînement

Légende : $\star$ application directe, $\star \star$ raisonnement intermédiaire, $\star \star \star$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Construire et lire des listes.

• [11.] $\star$ Donner le type et la valeur de 5 :: [], [] @ [1; 2], [true] @ [false], [(1, 2); (3, 4)].
• [12.] $\star$ Écrire tete et queue (avec failwith sur la liste vide) par filtrage.
• [13.] $\star \star$ Écrire nieme l n renvoyant le n-ième élément (à partir de $0$), failwith si l'indice est hors borne.

Thème B — Parcours et accumulation.

• [14.] $\star$ Écrire somme_carres l (somme des carrés des entiers de l).
• [15.] $\star \star$ $⧫$ Écrire compte_pairs l (nombre d'entiers pairs) et tous_positifs l (tous les éléments sont $>0$ ?).
• [16.] $\star \star$ Écrire intervalle a b qui construit la liste [a; a+1; ...; b] (et [] si a > b).

Thème C — Transformations.

• [17.] $\star \star$ $⧫$ Écrire incremente l qui renvoie une nouvelle liste où chaque entier est augmenté de $1$ (sans modifier l).
• [18.] $\star \star$ Écrire garde_pairs l qui renvoie la sous-liste des éléments pairs, dans l'ordre.
• [19.] $\star \star \star$ Écrire aplatis l qui, d'une int list list, fait une int list en concaténant ; discuter son coût selon qu'on concatène à gauche ou via un accumulateur.

Thème D — option et recherche.

• [20.] $\star \star$ Écrire dernier_option l : 'a option (sans exception).
• [21.] $\star \star$ $⧫$ Écrire maximum_option l : int option renvoyant None sur la liste vide.
• [22.] $\star \star \star$ Écrire premier_pair l : int option renvoyant le premier élément pair s'il existe, None sinon, en s'arrêtant dès qu'il est trouvé.