Il nous reste une dernière famille de fonctionnelles de listes : celle qui calcule une seule valeur, qui dépend de chaque élément d'une liste. Typiquement, calculer la somme des valeurs de la liste, calculer l'élément maximum ou minimum d'une liste, etc. La valeur retournée peut-être un type simple, mais peut aussi être une nouvelle liste, une fonction, ou n'importe quel type. L'important est que la valeur obtenue dépend de toute la liste globalement. Cela ne doit pas dépendre d'un seul élément (sinon on cherche cet élément et on calcule avec), et ne doit pas considérer les éléments de façon complètement indépendante les uns des autres (sinon, on peut probablement utiliser map, filter, etc).
La façon la plus simple de comprendre l'opération de réduction intervient dans le cadre de l'utilisation d'opérateurs binaires associatifs. Par exemple, l'addition des entiers, ou la conjonction de booléens. Pour additionner tous les entiers d'une liste, il faut faire :
Pour calculer une conjonction de tous les booléens d'une liste, on fait :
On veut donc une opération reduce, dont l'effet est décrit par :
avec (++) un opérateur binaire. C'est une version simpliste de la fonction générale de réduction. En effet :
Néanmoins, reduce suffit pour certains calculs, en particulier les sommes, les calculs de maximum ou de minimum. On peut donc utiliser :
La deuxième version gère le cas de la liste vide, en retournant une valeur optionnelle. La première version produira une erreur sur la liste vide, il faut donc s'en méfier.
On peut utiliser reduce pour refaire exists et for_all :
Par contre ces deux versions sont moins efficaces, car elles calculent toujours le prédicat sur tous les éléments de la liste, alors que List.for_all et List.exists s'arrêtent au plus tôt dans leur calcul, dès que le résultat est déterminė (par évaluation paresseuse des opérateurs booléens).
Attaquons-nous aux trois problèmes :
reduce fonctionne avec un seul type, l'opérateur servant à réduire doit être de type 'elt -> 'elt -> 'elt, pour une liste de type 'elt list. Celui-ci va demander plus d'effort pour être corrigé. Le point principal est que nous souhaitons que le type du résultat de la réduction puisse être différent du type des éléments de la liste. Notre opérateur doit donc être de type :
avec 'result le type du résultat de la réduction. Par ailleurs, on veut que chaque résultat partiel influe sur le résultat final, donc 'result doit apparaître aussi en argument de l'opérateur. Nous n'avons donc pas le choix, l'opérateur est de type :
Les deux versions vont exister, selon qu'on parenthèse par la droite ou par la gauche. Dans les deux cas (seul l'ordre des arguments change), ce type s'interprète comme un consommateur de 'elt, et possèdant un état de type 'result. On va renommer 'result en 'state du coup.
Voici donc les deux fonctions de réduction. En anglais fold veut dire plier, il s'agit donc de replier la liste sur elle-même pour en faire quelque chose de petit.
Attardons-nous sur List.fold_left. L'usage de cette fonction est
Une première remarque à la vue de cette fonction est qu'elle ressemble beaucoup à l'exécution dans un automate fini : on part d'un état initial, et pour chaque lettre (chaque élément de la liste), on applique la transition, jusqu'à atteindre un état final. C'est une façon tout à fait valide de comprendre cette fonctionnelle, mais cela ne nous donnera pas beaucoup d'intuition sur comment et quand l'utiliser.
Par analogie avec ce qu'on a vu pour reduce, on peut définir fold_left par ces équations :
La première reformulation exprime que fold_left construit une expression en utilisant init, chaque élément de la liste, et la fonction f. En remplaçant f par une opérateur binaire ++ associatif à gauche, on obtient
C'est donc bien reduce avec un terme supplémentaire à gauche.
La deuxième et la troisième formulation exprime fold_left comme une séquence d'opérations : en partant de init, appliquer f avec e1, puis le résultat à f avec e2, etc. C'est la vision de f comme un consommateur, qui accumule des résultats intermédiaires à chaque fois qu'il consomme un élément.
Cela suggère que fold_left est la version fonctionnelle du programme suivant :
ou avec un code plus idiomatique (f est remplacé par la méthode accept de l'état):
Il y a encore une autre façon de comprendre fold_left, en considérant son type, et en le parenthésant :
fold_left transforme une fonction sur les 'elt en une fonction sur les 'elt list. Plus précisément, elle transforme une fonction transformant un état en un autre par rapport à un élément, en une fonction transformant un état en un autre par rapport à tous les éléments d'une liste. C'est donc, comme map, un combinateur transformant une fonction binaire en une fonction sur les listes. fold_left étend f en répétant f sur chaque élément.
fold_right fonctionne sur le même principe que fold_left, mais parenthèse à droite. Il lit donc la liste de la droite à la gauche. Ses arguments reflètent aussi cet ordre. En général, en OCaml, fold_left est préféré, ne serait-ce que pour une raison d'efficacité : fold_left est légèrement plus rapide.
fold_left généralise reduce, donc ce que nous avons fait avec reduce peut être refait avec fold_left.
On peut écrire reduce en utilisant uniquement fold_left.
S'il fallait partir sur une île déserte avec une seule fonction, il faudrait prendre fold_left ! On peut écrire toutes les autres fonctions de listes avec. Faisons quelques exemples intéressants. concat étend la concaténation de deux listes, à la concaténation d'une liste de listes, c'est donc l'extension de append aux listes. Petit piège, @ est associatif à droite, il faut donc utiliser fold_right. Pour le reste il suffit de remarquer que l'élément neutre pour la concaténation est la liste vide, ce qui nous donne la valeur initiale.
On peut refaire map (et bind est similaire). Cette fois, on va plutôt utiliser l'analogie du consommateur qui accumule les résultats intermédiaires. Pour map, on accumule les images des éléments par la fonction. Par ailleurs l'image de la liste vide doit être la liste vide, donc l'état initial est la liste vide.
Notons qu'on accumule les images dans l'ordre inverse (le premier se retrouve dernier), ce qui nous oblige à renverser la liste finale avec List.rev.
Mais bien sûr, on peut faire List.rev avec fold_left :
