Retour au sommaire.
Fonctionnelles de test.
Les tests constituent une catégorie d'opérations non-élémentaires possibles sur les listes : tester la présence d'un élément vérifiant une propriété, tester si tous les éléments vérifient une propriété, etc.
L'exemple du test d'existence.
Il arrive souvent de vouloir souhaiter savoir si un ensemble de valeurs contient une valeur ayant telle ou telle propriété : existe-t-il une valeur négative, une chaîne de caractère contenant "foo" , un objet dont le poids est supérieur à la limite,... Il n'est pas utile de réécrire à chaque fois une fonction qui effectue le test pour chaque élément, puis retourne un résultat booléen : la seule chose qui change selon les différents cas, c'est le prédicat (la propriété, sous forme d'une fonction à image booléenne) utilisé. Donc la seule chose qui doit être réécrite à chaque fois est le prédicat. Il nous faut une fonction qui, étant donné un prédicat et une liste, donne pour résultat un booléen signifiant la présence d'un élément validant la propriété. C'est la fonction List.exists !
val List.exists : ('elt -> bool) -> 'elt -> 'bool
val Core.Std.List.exists : 'elt -> f:('elt -> bool) -> 'bool
let contains_even_number integers =
let is_even n = n mod 2 = 0 in
List.exists is_even integers
let contains_negative_number integers =
let is_negative n = n < 0 in
List.exists is_negative integers
let contains_empty_string strings =
List.exists (fun string -> string = "") strings
let contains_heavy_object objects =
let is_heavy obj = get_weight obj > max_allowed_weight in
List.exists is_heavy objects
Quelques remarques :
Ces fonctions sont clairement toutes les mêmes ! Seul le prédicat change, ce qui était notre intention. Par ailleurs toute la partie algorithmique a disparu (elle est capturée dans la définition de exists).
Dans contains_empty_string, le prédicat utilisé est une fonction anonyme, l'expression d'une fonction écrite directement plutôt qu'une variable pour abstraire le prédicat. C'est bien évidemment possible, mais c'est un style à utiliser avec modération. Il est plus facile de lire une variable dont le nom explique le rôle de la fonction, que de lire directement la fonction.
Toutes ces fonctions peuvent s'écrire plus simplement encore :
let contains_even_number =
let is_even n = n mod 2 = 0 in
List.exists is_even
let contains_negative_number =
let is_negative n = n < 0 in
List.exists is_negative
let contains_empty_string =
List.exists (fun string -> string = "")
let contains_heavy_object =
let is_heavy obj = get_weight obj > max_allowed_weight in
List.exists is_heavy
Pour comprendre ce format, revenons au type de List.exists, et rajoutons les parenthèses inutiles :
val List.exists : ('elt -> bool) -> ('elt list -> bool)
Avec ce point de vue, exists est une fonction à un seul argument, le prédicat, retournant un prédicat sur les listes. C'est une fonction qui transforme un prédicat sur les éléments en un prédicat sur les listes. Elle fait passer le prédicat du monde des éléments vers le monde des listes, et on retrouvera ce schéma dans de nombreuses fonctionnelles. Illustrons :
let is_even n = n mod 2 = 0
let _yes = is_even 2
let _no = is_even 3
let _no = is_even (-1)
let contains_even_number = List.exists is_even
let _yes = contains_even_number [1;2;3;4;5]
let _no = contains_even_number [1;3;5;7]
let _no = contains_even_number []
Comparons avec un langage impératif comme Java. Si on considère les ArrayList, cette classe contient une méthode contains mais qui ne peut que tester la présence d'un élément donné, et non vérifier la présence d'un élément satisfaisant une propriété. Pour cela il faudrait pouvoir passer la propriété à tester en argument, mais une telle propriété est une fonction, on est donc obligé d'utiliser de la programmation fonctionnelle. Avec Java 8 , c'est désormais possible en utilisant l'interface Stream, qui a en Java le rôle qu'ont les listes en OCaml. Nous en reparlerons au dernier cours.
D'autres fonctionnelles.
Dans le premier exemple, on a construit un prédicat de liste à partir d'une prédicat d'élément, selon le principe que la liste est valide si elle contient un élément valide. Une autre solution naturelle aurait été de dire qu'une liste est valide si tous ses éléments sont valides :
val List.for_all : ('elt -> bool) -> 'elt list -> bool
val Core.Std.List.for_all : 'elt -> f:('elt -> bool) -> 'bool
let are_all_even = List.for_all is_even
let are_all_heavy =
let is_heavy obj = get_weight obj > max_allowed_weight in
List.for_all is_heavy
let _yes = are_all_even [2;4;6;8]
let _no = are_all_even [2;4;6;9;10]
let _yes = are_all_even []
Si on veut simplement tester la présence d'un élément dans une liste, on peut utiliser la fonction mem (pour MEMber, les fonctions de la librairie standard ne sont malheureusement pas toutes très bien nommées) :
val List.mem : 'elt -> 'elt list -> bool
val Core.Std.List.mem : 'elt list -> 'elt -> bool
let _yes = List.mem 3 [1;2;3;4]
let _no = List.mem 5 [1;2;3;4]
mem n'est pas une fonctionnelle.
Lorsqu'on teste l'existence d'une valeur particulière dans une liste, c'est en général pour utiliser cette valeur. Si List.exists
predicate s'évalue en true, il existe un élément satisfaisant predicate, et on aimerait bien savoir lequel. Il suffit d'utiliser une autre fonctionnelle : List.find predicate.
val List.find : ('elt -> bool) -> 'elt list -> 'elt
let four = List.find is_even [1;3;4;5;2]
let will_raise_an_exception = List.find is_even [1;3;5;7]
À nouveau, il faut bien tester l'existence avant de chercher l'élément, sinon une erreur se produira à l'exécution. Une meilleure solution est d'utiliser une variante de find, comme celle de la librairie alternative Core :
val Core.Std.List.find : 'elt list -> f:('elt list -> bool) ->'elt option
puisqu'une option représente soit un élément, soit rien, cette fonction est totalement définie. De plus, son résultat étant une option, on sera obligé pour utiliser le contenu de l'option de vérifier s'il est bien défini, ce qui nous empèche d'oublier des cas.
Retour au sommaire.
