Brève introduction aux foncteurs

Ce document présume que vous avez une certaine familiarité avec la POO, la programmation générique (en particulier les templates de C++) et les conteneurs standards de la STL comme std::vector.

Ce qui suit est une très brève introduction sur le sujet. Dans mes cours au Collège Lionel-Groulx et à l'Université de Sherbrooke, je montre comment exploiter les foncteurs pour faire de la magie – c'est un sujet riche et qui ouvre plusieurs chemins pour les informaticiennes et les informaticiens éveillé(e)s. Chaque chose en son temps et en son lieu...

Imaginons que vous souhaitiez réaliser la tâche suivante :

  • Lire plusieurs entiers d'un flux, par exemple de std::cin ou, comme dans l'extrait de code proposé à droite, d'un fichier ouvert en lecture, puis
  • Projeter chacun de ces entiers sur la sortie standard (std::cout), en prenant soit de les séparer l'un de l'autre par un espace pour qu'on puisse bien les distinguer

Un exemple de code réalisant cette tâche serait celui proposé à droite.

#include <iostream>
using namespace std;
template <class T>
   void afficher(const T &val) {
      cout << val << ' ';
   }
#include <vector>
#include <fstream>
#include <algorithm>
int main() {
   vector<int> v;
   ifstream ifs{"in.txt"};
   for (int val; ifs >> val; v.push_back(val))
      ;
   for_each(begin(v), end(v), afficher<int>);
}

Présumons maintenant qu'un collègue vous demande comment vous pourriez généraliser ce code pour qu'il puisse projeter les entiers lus sur n'importe quel flux, std::cout inclus. Vous avez alors un problème :

En retour, nous connaissons tous un type capable à la fois d'action et de tenir à jour un état: les objets. Comment pourrions-nous rejoindre le concept d'opération et le concept d'objet en un tout cohérent? En d'autres mots, pouvons-nous concevoir une entité qui soit à la fois objet et fonction?

La réponse est oui, et le nom technique pour une entité à la fois objet et fonction est foncteur. Les foncteurs sont relativement connus en Lisp, où ils apparaissent comme des fonctions qui sont aussi des objets, mais sont aussi très utilisés en C++ où ils apparaissent comme des objets qui sont aussi des fonctions.

#include <ostream>
template <class T>
   class Afficher {
      std::ostream &os;
   public:
      Afficher(std::ostream &os) noexcept : os{os} {
      }
      void operator()(const T &val) {
         os << val << ' ';
      }
   };
// ...

Prudence toutefois, puisque dans certains langages, comme Haskell, le mot foncteur a un autre sens. L'exemple sur http://www.haskell.org/haskellwiki/Functor est charmant :

class Functor f where
  fmap :: (a -> b) -> f a -> f b

On constate que le foncteur f prend une fonction de a vers b et génère une fonction f vers a retournant une fonction f vers b. Le foncteur est donc alors un outil de gestion de l'application de fonctions sur des paramètres, ce qui est intéressant mais constitue un concept distinct de celui décrit ici. Vous trouverez plus d'informations à ce sujet dans ../Divers--haskell/Foncteurs.html

En gros, la clé du bonheur pour un problème comme celui ci-dessus serait :

Le code ci-dessus, retouché pour exploiter un foncteur, serait alors celui proposé à droite.

Notez que le code du foncteur Afficher est un cousin (très simplifié) de celui de la classe std::ostream_iterator qui, conceptuellement, va plus loin. Un exemple du même programme mais qui utiliserait un itérateur en sortie plutôt que notre petit foncteur serait celui ci-dessous.

//...
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
int main() {
   using namespace std;
   vector<int> v;
   ifstream ifs{"in.txt"};
   for (int val; ifs >> val; v.push_back(val))
      ;
   // le pointeur sur Afficher<int> est remplacé
   // par une instance anonyme de la classe
   // Afficher<int> appliquée au flux std::cout
   for_each(begin(v), end(v), Afficher<int>{cout});
}
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
int main() {
   using namespace std;
   vector<int> v;
   ifstream ifs{"in.txt"};
   for (int val; ifs >> val; v.push_back(val))
      ;
   copy(begin(v), end(v), ostream_iterator<int>{cout, " "});
}

L'instance d' std::ostream_iterator est clairement un foncteur (remarquez la notation utilisée pour passer cet objet à l'algorithme std::copy() : c'est un appel de constructeur!).

Notez la notation qui utilise l'algorithme std::copy() plutôt que l'algorithme std::for_each(). Il faut comprendre ici que le std::ostream_iterator sert de destination pour l'écriture. Le concept est subtil et déborde un peu de ce que je peux couvrir ici, mais aura droit à son propre article un de ces quatre.

Par perversion, voici comment, avec trois foncteurs, on pourrait copier tous les int du fichier "in.txt" à la console de de la manière la plus compacte et la plus rapide possible[1] avec les outils standards à notre disposition, et sans passer par un conteneur intermédiaire.

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iterator>
int main() {
   using namespace std;
   copy(istream_iterator<int>{ifstream{"in.txt"}}, // début de la source
        istream_iterator<int>{}, // fin de la source (représente une erreur de lecture ou une fin de flux)
        ostream_iterator<int>{cout, " "});
}

Vous conviendrez sûrement que cela titille l'esprit.

Généricité par classe ou par méthode

L'exemple de foncteur Afficher ci-dessus est générique sur la base de la classe. On aura donc une classe Afficher<int> pour afficher des int, une autre classe Afficher<std::string> pour afficher des std::string, et ainsi de suite.

Dans ce cas-ci, il y a une alternative qui peut être avantageuse, soit d'utiliser une classe Afficher qui serait concrète mais qui exposerait une méthode operator() qui, elle, serait générique. On aurait alors une seule classe avec un nombre arbitrairement grand de méthodes operator(), contrairement au cas précédent où on avait un nombre arbitrairement grande de classes ayant chacune une seule méthode operator(). Les deux approches ont leurs qualités, leurs défauts et leurs cas d'utilisation.

Généricité sur la base de la classe Généricité sur la base de la méthode
#include <ostream>
template <class T>
   class Afficher {
      std::ostream &os;
   public:
      Afficher(std::ostream &os) noexcept : os{os} {
      }
      void operator()(const T &val) {
         os << val << ' ';
      }
   };
#include <ostream>
class Afficher {
   std::ostream &os;
public:
   Afficher(std::ostream &os) noexcept : os{os} {
   }
   template <class T>
      void operator()(const T &val) {
         os << val << ' ';
      }
};
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
int main() {
   using namespace std;
   vector<int> v;
   ifstream ifs{"in.txt"};
   for (int val; ifs >> val; v.push_back(val))
      ;
   // appellera Afficher<int>::operator()(const int &)
   for_each(begin(v), end(v), Afficher<int>{cout});
   vector<string> vs;
   ifstream ifs{"texte.txt"};
   for (string val; ifs >> val; vs.push_back(val))
      ;
   // appellera Afficher<string>::operator()(const string &)
   for_each(begin(v), end(v), Afficher<string>{cout});
}
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
int main() {
   using namespace std;
   vector<int> v;
   ifstream ifs{"in.txt"};
   for (int val; ifs >> val; v.push_back(val))
      ;
   // appellera Afficher::operator()(const int &)
   for_each(begin(v), end(v), Afficher{cout});
   vector<string> vs;
   ifstream ifs{"texte.txt"};
   for (string val; ifs >> val; vs.push_back(val))
      ;
   // appellera Afficher::operator()(const string &)
   for_each(begin(v), end(v), Afficher{cout});
}

Avoir recours à une classe générique est utile quand la classe a des états (des attributs, des variables locales dans certaines méthodes, des constantes) qui dépendent des types sur lesquels la généricité s'applique. Par exemple, un foncteur qui retiendrait la plus petite valeur d'une plage donnée pourrait être générique pour déterminer le type de cette valeur.

Dans le cas du foncteur Afficher, l'état est un std::ostream&, ce qui est indépendant du type T, donc une généricité sur la base de la méthode suffit amplement.

L'exemple à droite est un exemple concret d'utilisation d'algorithmes standards, de fonctions et de foncteurs :

  • Un tableau vals de N éléments de type int est déclaré
  • Ce tableau est rempli de valeurs pseudo-aléatoires (algorithme std::generate, qui applique le foncteur Distributeur{prng} à chaque élément du tableau)
  • Le contenu du tableau est affiché à la console (algorithme std::copy(), qui utilise un std::ostream_iterator<int>, mais nous aurions pu utiliser l'un ou l'autre des foncteurs Afficher décrits plus haut), et
  • Un parcours du tableau est réalisé (algorithme std::for_each()) pour identifier la plus petite valeur et l'afficher. Notez que nous utilisons l'élément vals[0] comme valeur initiale de plus_petite_valeur<int>, et que nous comparons cette valeur avec celles aux positions du tableau
  • Puisque std::for_each() retourne l'opération qu'il a appliqué sur la séquence qu'il traversait, nous utilisons la méthode valeur() de l'instance de plus_petite_valeur<int> résultante pour obtenir la plus petite valeur constatée et l'afficher à la console

Voilà du code très contemporain, qui fait beaucoup de travail de manière à la fois très rapide, très claire et très concise, le tout en trois opérations seulement.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
template <class T>
   class plus_petite_valeur {
      T val;
   public:
      plus_petite_valeur(const T &init) : val{init} {
      }
      void operator()(const T &v) {
         val = std::min(val,v);
      }
      T valeur() const {
         return val; }
      }
   };
class Distributeur {
   std::uniform_int_distribution<int> distrib;
   std::mt19937 &prng;
public:
   Distributeur(std::mt19937 &prng)
      : prng{ prng }, distrib{ 1, 100 }
   {
   }
   int operator()() {
      return distrib(prng);
   }
};
int main() {
   using namespace std;
   random_device rd;
   mt19937 prng{rd()};
   enum { N = 10 };
   int vals[N];
   generate(begin(vals), end(vals), Distributeur{prng});
   copy(begin(vals), end(vals),ostream_iterator<int>{cout, " "});
   cout << endl << for_each(
      next(begin(vals)), end(vals),
      plus_petite_valeur<int>{vals[0]}
   ).valeur() << endl;
}

Exemples simples d'utilisation de foncteurs

L'algorithme std::generate() affecte la valeur de retour d'une opération à tous les éléments d'une même séquence.

Par exemple, le code à droite affecte la valeur -1 à chaque élément du tableau tab.

On aurait aussi pu utiliser le cousin de std::generate(), nommé std::generate_n(), qui prend en paramètre un début de séquence et un nombre d'éléments à initialiser, pour en arriver au même résultat.

Visiblement, ici, l'opération servant à initialiser chacun des éléments du tableau n'est pas la plus souple qui soit: elle est une bête fonction retournant, comme il se doit, la même valeur à chacune de ses invocations. On ne pourrait pas, par exemple, s'en servir pour insérer les valeurs dans un tableau du fait que la fonction n'a pas le souvenir de la dernière valeur générée.

#include <iostream>
#include <algorithm>
#include <iterator>
int moins_un() {
   return -1;
}
int main() {
   using namespace std;
   enum { N = 100 }; // arbitraire
   int tab[N];
   generate(begin(tab), end(tab), moins_un);
   copy(begin(tab), end(tab), ostream_iterator<int>{cout, " "});
}

La fonction pourrait, en fait, se souvenir de la la dernière valeur générée si elle utilisait une variable globale ou une variable static mais cela la restreindrait alors à un seul souvenir. On ne pourrait pas vraiment s'en servir pour initialiser plusieurs séquences (du moins pas sans réinitialiser manuellement la variable servant de souvenir)

Les foncteurs, eux, sont des objets à part entière et ont leurs propres états. Pour une telle tâche, un foncteur est donc tout indiqué.

class SequenceEntiers {
   int cur; // dernière valeur générée
public:
   SequenceEntiers(int init = {}) noexcept : cur{init} {
   }
   int operator()() noexcept { // générer une valeur
      return ++cur;
   }
};
#include <iostream>
#include <algorithm>
#include <iterator>
int main() {
   using namespace std;
   enum { N = 100 }; // arbitraire
   int tab[N];
   generate(begin(tab), end(tab), SequenceEntiers{}); // voir aussi std::iota() pour ceci
   copy(begin(tab), end(tab), ostream_iterator<int>{cout, " "});
}

De la même manière, une fonction ne pourrait pas accumuler les valeurs d'une séquence, par exemple pour en faire la somme. Avec un foncteur, il est par contre possible de conserver le souvenir du cumul à date et d'exprimer l'idée de somme de valeurs, par exemple, avec une certaine élégance.

class SequenceEntiers {
   int cur;
public:
   SequenceEntiers(int init = {}) noexcept : cur{init} {
   }
   int operator()() noexcept {
      return ++cur; }
   }
};
class Somme {
   int &cumul;
public:
   Somme(int &cumul) noexcept : cumul{cumul} {
   }
   void operator()(int n) noexcept {
      cumul += n;
   }
};
#include <iostream>
#include <algorithm>
int main() {
   using namespace std;
   enum { N = 100 }; // arbitraire
   int tab[N];
   generate(begin(tab), end(tab), SequenceEntiers{});
   int cumul = 0;
   for_each(begin(tab), end(tab), Somme{cumul});
   cout << "Somme de " << tab[0] << " à " << tab[N-1] << ": " << cumul << endl;
}

Remarquez que le cumul se fait ici sur une variable locale au sous-programme appelant. Ce n'est pas strictement nécessaire (des stratégies de grande personne reposant sur l'emploi d'une classe interne au foncteur pourraient nous permettre d'éviter ce stratagème) mais c'est la stratégie la plus simple ici, du fait que l'algorithme std::for_each() travaille avec une copie de son troisième paramètre.

Si l'état servant de variable cumulative au foncteur Somme était un simple attribut de type int, alors la copie de cet attribut serait modifiée et l'original resterait intact, ce qui nous empêcherait de connaîtrele résultat du calcul.

Ce n'est pas une faiblesse des foncteurs mais bien un choix d'implémentation des bibliothèques standards de C++ que de travailler principalement avec des paramètres par valeur, ce qui évite beaucoup, beaucoup d'effets de bord mais demande, dans certains cas (dont celui-ci), un peu de soins particuliers.

La manière idiomatique de réaliser le cumul des valeurs d'une séquence est, au choix, de procéder par copie (en utilisant un algorithme tel que std::for_each()), ou – mieux encore – d'utiliser un algorithme conçu à cet effet, par exemple std::accumulate() de la bibliothèque <numeric>.

Pour les fins du présent article, je me limiterai à l'approche reposant sur for_each() :

class SequenceEntiers {
   int cur;
public:
   SequenceEntiers(int init = {}) noexcept : cur{init} {
   }
   int operator()() noexcept {
      return ++cur;
   }
};
class Somme {
   int cumul;
public:
   Somme(int init = {}) noexcept : cumul{init} {
   }
   void operator()(int n) noexcept {
      cumul += n;
   }
   int valeur() const noexcept {
      return cumul;
   }
};
#include <iostream>
#include <algorithm>
int main() {
   using namespace std;
   enum { N = 100 }; // arbitraire
   int tab[N];
   generate(begin(tab), end(tab), SequenceEntiers({});
   cout << "Somme de " << tab[0] << " à " << tab[N-1] << ": "
        << for_each(begin(tab), end(tab), Somme{}).valeur() << endl;
}

Pourquoi utiliser un foncteur

Certains auront l'impression que le code s'alourdit avec les foncteurs, en partie à cause des exemples trop simples proposés ici.

En réalité, les foncteurs sont un outil puissant, polyvalent et extrêmement utile. On aura recours aux foncteurs :

Lectures complémentaires

Quelques liens pour enrichir le propos.


[1]En fait, il y a une manière encore plus rapide, mais elle a recours à des stratégies de plus bas niveau...


Valid XHTML 1.0 Transitional

CSS Valide !