Un des traits principaux de la programmation fonctionnelle est la capacité à manipuler des fonctions de la même façon que toutes les autres données. Cela permet par exemple de pouvoir passer des fonctions en arguments, ou bien de pouvoir en retourner.
De façon plus générale, il faut même comprendre que les fonctions sont elle-mêmes des données : on peut donc les utiliser pour représenter des entités, dès lors que c'est une représentation adaptée. On peut donc représenter nos données par des tuples, des enregistrements, des types algébriques, des objets ou bien par des fonctions.
Ce cours va principalement montrer à quel point cette idée de représenter par des fonctions peut être naturelle et conduire et des programmes très simples. Pour cela, nous allons voir quelques exemples.
Tout cela est donc permis par le fait que les fonctions peuvent être passées en arguments d'autres fonctions, ou retournées par d'autres fonctions. Une fonction travaillant sur des fonctions s'appelle une fonctionnelle, ou une fonction d'ordre supérieure. Nous avons déjà introduit plein de fonctionnelles. Par exemple, sur les listes, les fonctions exists, map, filter, fold_left, etc. sont des fonctionnelles puisqu'elles prennent toutes une fonction en argument.
Mais nous avons aussi vu que la plupart de ces fonctions peuvent être vues, non comme des fonctions travaillant sur des listes, mais comme des fonctions transformant une fonction normale en fonction sur les listes. Elles prennent en argument une fonction, et retourne une fonction sur les listes.
Par exemple, ce parenthésage du type de map met en évidence que map construit une fonction à partir d'une fonction. Les fonctions transformant des fonctions en fonctions sont en général appelées des combinateurs.
Examinons un exemple plus complet que nous avons déjà croisé plus tôt. Lorsque nous avons parlé des consommateurs, nous avons introduit un type pour les prédicats, ainsi qu'un certain nombre d'opérations :
Il est temps de voir comment programmer ce module. La première question à se poser est : qu'est-ce qu'un prédicat ? C'est une fonction vers l'ensemble des booléens. À partir de cette réponse, le type à utiliser pour représenter les prédicats est évident :
On utilise donc un type fonction. Immédiatement, cela implique que presque toutes les fonctions du module Predicate sont en fait des combinateurs ! Voyons un peu. Commençons par les définitions les plus simples :
test consiste simplement à appliquer le prédicat à la valeur à tester. L'application se note (@@). always et never sont des prédicats : des fonctions prenant une valeur et retournant un booléen, ici toujours le même.
negate inverse le prédicat, c'est donc une fonction qui prend une valeur, et retourne la négation de ce que dit le prédicat. is pourrait s'écrire plus astucieusement let is = (=). Comme quoi nous sommes en train de manipuler des fonctions ! De même, checks doit transformer une fonction de type 'value -> bool en un prédicat, de même type : c'est donc l'identité. On passe aux fonctions intéressantes :
On prend deux fonctions en arguments, on en retourne une nouvelle.
Et oui, List.for_all et List.exists sont des combinateurs : elles transforment comme promis des prédicats en prédicats.
Pas de difficulté particulière pour ces trois dernières fonctions. Globalement, écrire ce module n'a pas couté bien cher, toutes les fonctions s'écrivent en une ligne, et plusieurs sont même complètement triviales. Pourtant, il peut se révéler utile. Imaginons un type pour coder les identités de personnes, avec des accesseurs pour obtenir diverses informations (nom, âge, etc.). On peut maintenant trouver toutes les personnes d'une liste vérifiant certains critères :
Le même code sans le module Predicate :
est quand même bien plus verbeux !
