Cours 4

Htmligure
Version & licenses
Creative Commons License

Les listes

Guyslain
Thursday, 21 July 2016

Retour au sommaire.

Nous avons mentionné que les listes sont un type inductif, certes avec des constructeurs un peu particulier : ils ne respectent pas les conventions d'être des identifiants commençant par une majuscule, et :: s'utilise en position infixe.

  1. type 'elt list =
  2. | []
  3. | (::) of 'elt * 'elt list

Pour le reste, il s'agit en tout point d'un type inductif, et on peut donc les manipuler avec des algorithmes inductifs. De fait, c'est ainsi que sont définies les fonctionnelles de listes vues au cours précédent.

Essayons d'écrire directement, par un algorithme inductif, la fonction testant que tous les entiers d'une liste sont pairs :

  1. let rec are_all_even = function
  2. | [] -> true
  3. | head :: tail -> is_even head && are_all_even tail

Pour obtenir la fonction for_all, il suffit de remarquer que la seule chose spécifique au test de parité est l'appel is_even head dans le deuxième cas. En remplaçant is_even par une condition arbitraire, prise en argument, on obtient :

  1. let rec for_all is_valid = function
  2. | [] -> true
  3. | head :: tail -> is_valid head && for_all is_valid tail

Il faut bien sûr redonner l'argument supplémentaire lors de l'appel récursif. Toutes les fonctionnelles de listes s'obtiennent de cette façon : à partir de schémas d'induction sur les listes, on généralise les actions qui ne sont pas directement liées à la manipulation des listes, en les abstrayant comme des fonctions prises en argument. Dérivons fold_right de cette manière.

À la base, nous pouvons partir de la fonction sommant les éléments d'une liste. En OCaml par induction on obtient :

  1. let rec sum_of_list = function
  2. | [] -> 0
  3. | head::tail -> head + sum_of_list tail

Les seules termes qui sont propres au calcul de la somme, et non à la récursion, c'est le 0 de la ligne 2 , et le + de la ligne 3 . On les abstrait,et on obtient fold_right :

  1. let rec fold_right reduce value_when_empty = function
  2. | [] -> value_when_empty
  3. | head::tail -> reduce head (fold_right reduce value_when_empty tail)

  5. let sum_of_list = fold_right (+) 0

fold_left est moins naturel, pour le comprendre il est plus simple de commencer par la version Java :

  1. int sumOfList(List<Integer> ints) {
  2. int sum = 0;
  3. for (Integer i : ints) {
  4. sum = sum + i;
  5. }
  6. return sum;

Ici, la valeur d'initialisation, ainsi que la somme à chaque itération, peuvent être abstraites. La valeur d'initialisation est abstraite par initValue, qui peut avoir un type arbitraire. La somme est abstraite par une fonction combine.

  1. (* An example of functional programming in Java ! (require Java 8) *)
  2. (* the reduce method of interface Stream is actually more complicated *)

  4. <U,T> U reduce(List<T> list, <U> initValue, BiFunction<U,T,U> combine) {
  5. U accum = initValue;
  6. for (T value : list) {
  7. accum = combine.apply(accum,value);
  8. }
  9. return accum;

La fonctionnelle fold_left d'OCaml peut être comprise comme une version inductive de cette boucle. Écrivons l'induction pour la somme d'une liste. Ce qui change est qu'on doit commencer par la somme de la valeur initiale, et du premier élément de la liste. Il faut donc une valeur initiale en argument de la fonction. Notons que le résultat de l'addition devient la valeur de la variable locale sumen Java. Pour l'induction, c'est l'argument de valeur initiale qui remplit le rôle de sum.

  1. let rec sum_of_list init_value = function
  2. | [] -> init_value
  3. | head :: tail ->
  4. let partial_sum = init_value + head in
  5. sum_of_list partial_sum tail

Il suffit maintenant d'abstraire la fonction appliquée à la valeur initial et la tête.

  1. let rec fold_left combine init_value = function
  2. | [] -> init_value
  3. | head :: tail ->
  4. let partial_result = combine init_value head in
  5. fold_left combine partial_result tail

Le même travail peut être effectué sur chacune des fonctionnelles. Cependant, ce n'est pas nécessaire : l'intérêt des fonctionnelles est justement de ne pas avoir à réécrire systématiquement des fonctions bas-niveaux inductives.

Néanmoins, il est parfois intéressant d'utiliser des inductions pour certaines manipulations de listes. Les fonctionnelles capturent la plupart des schémas d'induction courants pour les listes, mais pas tous. Il faut donc être capable de repérer avec aisance les cas d'application des fonctionnelles de listes, et lorsque les fonctionnelles de listes sont inadaptés, revenir sur une induction, puis se demander si l'induction n'est pas généralisable en une fonctionnelle naturelle qui pourrait être réutilisée.

Retour au sommaire.