Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter

Support de cours · chapitre 4

Analyse par cas

Choisir selon une condition ou selon la forme d'une valeur. L'alternative, les exceptions, le filtrage, les fonctions anonymes et les n-uplets.

Préambule

  • La résolution d'un problème passe par sa décomposition en sous-problèmes.
  • La forme la plus simple de décomposition est l'analyse par cas : on énumère un ensemble de cas, qui forment une partition du domaine de la fonction.
  • Chaque cas est la restriction du problème à un sous-domaine. Les cas doivent couvrir tout le domaine, et s'exclure mutuellement.

L'alternative

La construction de l'alternative en Caml

L'alternative correspond au calcul « si condition alors expression₁ sinon expression₂ », qui s'écrit :

if condition then expression1 else expression2

avec :

  • condition, une expression booléenne ;
  • expression1 et expression2, deux expressions du même type, qui est aussi le type de l'alternative.
if 1 < 2 then "oui" else "non" ;;
let abs x = if x < 0 then -x else x ;;
abs (-5) ;;

Imbrications et propriétés

if true then 1 else "un" ;;

Il est possible d'imbriquer les alternatives. Par exemple, l'équivalence logique de deux booléens :

let equiv a b =
  if a then (if b then true else false)
  else (if b then false else true) ;;
equiv false false ;;

Ce qui se simplifie en let equiv a b = if a then b else not b.

Les exceptions

Une exception dans un monde parfait

Toute fonction doit rendre une valeur, quel que soit son argument. Que fait-on quand on demande une valeur qui n'est pas définie ?

1 / 0 ;;

Ce résultat s'appelle une exception : ici Division_by_zero, en quelque sorte un échec. En général, une exception provoque l'arrêt du programme. En Caml, une exception est une valeur : on peut donc la rattraper, ce que l'on verra plus tard.

Déclencher une exception

Deux fonctions de base déclenchent une exception, failwith et invalid_arg :

failwith "boum" ;;
invalid_arg "f" ;;
failwith ;;

Ces deux fonctions prennent un argument de type string, le message. Leur résultat est de type 'a, un type polymorphe : il s'accorde avec n'importe quel autre type, et on peut donc déclencher une exception dans n'importe quelle branche.

let inverse x =
  if x = 0 then failwith "inverse : division par zéro"
  else 1.0 /. float_of_int x ;;
inverse 4 ;;
inverse 0 ;;

La branche then est de type 'a, la branche else de type float : l'alternative est de type float.

Le filtrage

Le filtrage

  • On peut aussi utiliser le filtrage (pattern matching en anglais) pour différencier les cas.
  • Le filtrage met en correspondance des motifs (patterns) et des valeurs.
  • Il ressemble à certaines constructions d'autres langages (comme le switch du C), mais il est beaucoup plus puissant : il ne teste pas seulement la valeur filtrée, mais aussi sa structure.

Filtrage explicite

Exemple : on veut écrire la fonction ainsi définie

$$f(x) = \begin{cases} 18 & \text{si } x = 0\\ 24 & \text{si } x = 1\\ x^2 & \text{sinon} \end{cases}$$

Exemple de filtrage

Il faut donc établir les correspondances

$$\begin{cases} 0 \longrightarrow 18\\ 1 \longrightarrow 24\\ y \longrightarrow y^2 \end{cases}$$

ce qui se fait en Caml par :

let f x = match x with
  | 0 -> 18
  | 1 -> 24
  | y -> y * y ;;
f 0 ;;
f 5 ;;

Le motif y est un nom : il filtre n'importe quelle valeur, et lui donne ce nom dans l'expression associée.

Construction générale du filtrage

match expression with
| motif1 -> expression1
| motif2 -> expression2
  ...
| motifn -> expressionn

La première barre | est facultative.

Importance de l'ordre et complétude

Inversons les cas de l'exemple précédent :

let g x = match x with
  | y -> y * y
  | 0 -> 18
  | 1 -> 24 ;;
g 0 ;;

Le motif y filtre toutes les valeurs : les deux cas suivants ne servent jamais. Caml le signale, pour chacun, par un avertissement (warning) : la fonction est acceptée, mais elle ne fait pas ce qu'on voulait.

let h x = match x with
  | 0 -> 18
  | 1 -> 24 ;;
h 2 ;;

Caml a vérifié le filtrage et trouvé un cas oublié ; il en donne même un exemple. Il ne faut jamais laisser passer ces avertissements.

Filtrage de plusieurs valeurs

On peut filtrer plusieurs paramètres d'une fonction, en imbriquant les filtrages. Par exemple, le et logique :

let and_ a b =
  match a with
  | true -> (match b with
             | true -> true
             | false -> false)
  | false -> false ;;

Sans elles, le dernier cas | false -> false est lu comme un cas du match b, pas du match a :

let and_ a b =
  match a with
  | true -> match b with
            | true -> true
            | false -> false
  | false -> false ;;

Motif universel

Il existe un motif qui s'apparie avec toute valeur sans lui donner de nom : le motif universel, noté _. On peut le voir comme un « sinon », lorsque toutes les autres valeurs ont été décrites.

let and_ a b =
  match a with
  | true -> (match b with
             | true -> true
             | _ -> false)
  | _ -> false ;;

Oui, à condition de ne plus avoir besoin de nommer la valeur dans ce cas, ou d'utiliser le paramètre x :

let f x = match x with
  | 0 -> 18
  | 1 -> 24
  | _ -> x * x ;;

Filtres « ou »

Si plusieurs valeurs donnent le même résultat, on peut les regrouper :

let f x = match x with
  | 1 | 2 | 3 -> 1
  | 4 | 5 | 6 -> 2
  | _ -> 5 ;;
f 5 ;;

Ces filtres à plusieurs cas, séparés par |, s'appellent des filtres « ou ». Ils filtrent l'union des cas filtrés par leurs composants.

Filtres gardés

Oui, avec une garde : un motif peut être suivi d'une condition, introduite par when.

let sign x = match x with
  | 0 -> 0
  | y when y > 0 -> 1
  | _ -> -1 ;;
sign (-3) ;;

Filtrage et fonctions anonymes

Fonctions anonymes

Il existe une autre syntaxe pour définir les fonctions. Par exemple :

$$successeur : \begin{cases} \mathbb{Z}\longrightarrow\mathbb{Z}\\ x\longmapsto x+1 \end{cases}$$

se traduit simplement en Caml par une fonction anonyme, function x -> x + 1, à laquelle on donne un nom :

let successeur = function x -> x + 1 ;;

Fonctions anonymes à plusieurs arguments

(Ce point sera revu plus en détail plus tard.)

Pour une fonction à plusieurs arguments, il faut introduire chaque paramètre par une construction function paramètre ->.

let moyenne = function a -> function b -> (a + b) / 2 ;;
moyenne 3 7 ;;

La fonction moyenne est donc :

  • la fonction qui à a associe (function a ->)…
  • … la fonction qui à b associe, pour a fixé, $\frac{a+b}{2}$ (function b -> (a + b) / 2).

Une notation enfin clarifiée

(Ce point sera revu plus en détail plus tard.)

La fonction moyenne est de type int -> int -> int, exactement comme average au chapitre précédent : les deux écritures définissent la même fonction.

-> est associatif à droite : ce type se lit int -> (int -> int). C'est le type de la fonction qui, à un entier, associe une fonction qui, à un entier, associe un entier. C'est pour cela que average 10 était une fonction.

Filtrage « anonyme »

Le filtrage utilise -> (associe), avec la même signification que dans les fonctions anonymes. On peut donc combiner les deux : function suivi directement de cas de filtrage.

La fonction sign est la fonction qui :

  • à 0 associe 0 ;
  • à un entier strictement positif associe 1 ;
  • à tout autre entier (un entier négatif !) associe -1.

Soit, en Caml :

let sign = function
  | 0 -> 0
  | y when y > 0 -> 1
  | _ -> -1 ;;

Avec function, le paramètre n'a pas de nom : le motif universel _ ne peut donc être utilisé que si l'expression associée ne dépend pas de la valeur du paramètre. Pour s'en servir, on utilise un motif nommé, comme y ci-dessus.

let est_zero = function
  | 0 -> true
  | _ -> false ;;
est_zero 3 ;;

Filtrage et produit cartésien

Un couple s'écrit entre parenthèses, ses composantes séparées par une virgule. On en extrait les composantes avec fst et snd, ou en le déstructurant par un motif :

(1, "un") ;;
let p = (3, 4) ;;
fst p ;;
snd p ;;
let (a, b) = p in a * b ;;
let norme2 (x, y) = x * x + y * y ;;
norme2 p ;;

On construit de même des triplets, quadruplets, n-uplets, et des couples de couples :

(1, 'a', "b", 2.0) ;;
((1, 2), (3, 4)) ;;

fst et snd ne s'appliquent qu'aux couples ; pour les n-uplets, on déstructure.

Filtrage de plusieurs valeurs

Le produit cartésien permet de filtrer plusieurs valeurs en même temps, en filtrant le couple qu'elles forment. Écrivons l'implication logique, qui n'est fausse que si a est vrai et b faux.

Avec les quatre cas explicites :

let implies a b = match (a, b) with
  | (true, true) -> true
  | (true, false) -> false
  | (false, true) -> true
  | (false, false) -> true ;;

Trois cas donnent true. On traite d'abord le seul cas faux, et le motif universel se charge des autres :

let implies a b = match (a, b) with
  | (true, false) -> false
  | _ -> true ;;
implies true false ;;
implies false true ;;

Le motif universel _ peut donc remplacer n'importe quoi, de n'importe quel type, même structuré !

Avec une fonction anonyme, la fonction prend un couple en argument : son type change.

let implies = function
  | (true, false) -> false
  | _ -> true ;;
implies (false, false) ;;

Enfin, les parenthèses autour des couples sont facultatives dans les motifs :

let implies a b = match a, b with
  | true, false -> false
  | _ -> true ;;