Table des matières

1. Tris (1 point)

#include <vector>

// Nommons notre type pour plus de facilité de lecture et d'écriture
using int_tab_t = std::vector< int >;

// IL EST IMPORTANT D'UTILISER DES PARENTHÈSES ICI, ET PAS DES ACCOLADES :
// int_tab_t tab{ 10 };               // Tableau de 1 seul entier valant 10
   int_tab_t tab( 10 );               // Tableau de 10 entiers

int premier{ tab[0] };      // Accès au premier élément
tab[tab.size() - 1] = 5;    // Modification du dernier élément

1.1. Affichage d'un tableau

• Écrire une fonction print_tab() qui reçoit en argument un tableau d'entiers passé par référence constante et qui affiche ce tableau sur la sortie standard (les éléments dans l'ordre séparés par des espaces, le tout encadré par des crochets : voir l'exemple ci-dessous).
  

• Écrire une fonction test_11() qui affiche son nom, qui crée un tableau tab avec l'instruction

    // Tableau de 6 entiers ayant les valeurs indiquées
    const int_tab_t tab{ 1, -2, 3, -4, 5, -6 };

et qui affiche ce tableau.

• Écrire la fonction main() qui appelle test_11(). Compiler et exécuter votre programme. Le résultat attendu est :

1.2. Remplissage d'un tableau avec des nombres aléatoires

• Écrire une fonction random_tab() qui reçoit en argument un tableau d'entiers passé par référence non constante et qui remplace tous les éléments de ce tableau par des valeurs aléatoires comprises entre -10 et 10.
  

• Écrire une fonction test_12() qui crée un tableau de 10 entiers et appelle random_tab() puis print_tab() avec le tableau comme argument.
  
• Ajouter à la fonction main() un appel à test_12(). Exécuter plusieurs fois votre programme pour vérifier que tous les nombres demandés, et seulement eux, peuvent apparaître dans le tableau.
  

1.3. Tri par ordre croissant

• Écrire une fonction sort_tab_1() qui reçoit en argument un tableau d'entiers passé par référence non constante et qui tri les éléments de ce tableau par ordre croissant.
  

• Écrire une fonction test_13() qui crée un tableau de 10 entiers, appelle dans l'ordre random_tab(), print_tab(), sort_tab_1(), et de nouveau print_tab() avec le tableau comme argument.
  
• Ajouter à la fonction main() un appel à test_13(). Vérifier la bonne exécution en exécutant plusieurs fois votre programme.
  

1.4. Tri selon un autre critère

Un algorithme de tri est en général indépendant de la façon de comparer les éléments, les bibliothèques utilisent diverses solutions selon les langages pour indiquer comment doit être effectuée la comparaison :

• En Python, la fonction sort() utilise 2 arguments passés par mot-clé : une fonction permettant d'extraire la clef de comparaison d'un élément et un booléen pour demander un tri en ordre inverse.
• En Java, le second argument de la méthode Arrays.sort() est un objet dédié à la comparaison (implémentant l'interface Comparator).
• En C, le dernier argument de la fonction qsort() est un pointeur sur une fonction de comparaison.
• En C++, le dernier argument de la fonction sort() est un objet fonction de comparaison.

• Nous allons commencer par utiliser un pointeur sur fonction. Écrire deux fonctions less() et greater() qui reçoivent en argument 2 entiers et qui retournent true si le premier est plus petit (pour less()) ou plus grand (pour greater()) que le second, false sinon.
  
• Écrire une fonction sort_tab_2() qui reprend le code de sort_tab_1(), mais qui reçoit comme second argument un pointeur sur une fonction de comparaison ; le tri se fera en utilisant cette fonction.
  

• Écrire une fonction test_14() qui crée un tableau de 10 entiers et l'initialise avec random_tab() et l'affiche, puis le trie avec sort_tab_2() et l'affiche à nouveau, une première fois en utilisant less(), une seconde avec greater().
  
• Ajouter à la fonction main() un appel à test_14(). Vérifier la bonne exécution en exécutant plusieurs fois votre programme.
  
  

1.5. Tri avec fonction lambda

Dans les langages fonctionnels, les fonctions sont dites Fonctions de première classe et il n'est pas nécessaire de passer par l'intermédiaire d'un pointeur.

En C++, c'est le type std::function qui permet de définir des variables contenant des fonctions (ou autres entités qui se comportent comme des fonctions). Comme C++ est un langage fortement typé, le type de la fonction est pris en compte et apparait comme paramètre de généricité de std::function :

double plus_un( int x ) { return x + 1.0; }

void f()
{
    double six{ plus_un( 5 )};
    // double( int ) est le type d'une fonction qui prend un int en argument
    // et retourne un double
    std::function< double( int ) > int_to_double_f{ plus_un };
    // static_cast est utilisé pour rendre explicite la conversion du flottant en entier
    double sept{ int_to_double_f( static_cast< int >( six ))};

    // Une fonction lambda (voir ci-dessous) est une fonction, et peut donc être
    // utilisée dans une affectation d'une variable ayant le bon type.
    int_to_double_f = []( int y ) { return y - 1.0; };
    // Les crochets indiquent le début de la définition de la fonction lambda (et 
    // remplacent donc le nom de la fonction). Le type de retour est ici automatiquement 
    // déduit, il pourrait être explicitement indiqué en ajoutant -> double avant 
    // l'accolade ouvrante.

    six = int_to_double_f( static_cast< int >( sept ));
}

• Définir une fonction sort_tab_3(), identique à sort_tab_2() sauf que son second argument est de type std::function.
  
  

Cette solution n'apporte pour l'instant aucun avantage : elle nécessite toujours d'avoir nos fonctions less() et greater().

Une autre facilité offerte par les langages fonctionnels est la possibilité de définir des fonctions sans nom à l'endroit où on en a besoin, on parle de fonction anonyme ou fonction lambda (voir un exemple de définition ci-dessus).

• Écrire une fonction test_15(), identique à test_14() sauf qu'elle utilise sort_tab_3() et des fonctions lambda (à la place de less()et de greater()) pour faire un tri, croissant puis décroissant, sur la valeur absolue des nombres.
  
• Ajouter à la fonction main() un appel à test_15(). Vérifier la bonne exécution en exécutant plusieurs fois votre programme.
  
  

2. Listes (1,5 point)

La programmation fonctionnelle est souvent associée aux listes, en général définies sous la forme : une liste est soit vide, soit constituée d'un élément suivi d'une liste ; contrairement aux tableaux, il n'est pas possible d'accéder à un élément (ou de connaître le nombre d'éléments) en temps constant (ces opérations ont une complexité linéaire), par contre l'ajout d'un élément n'importe où se fait en temps constant (complexité linéaire pour les tableaux).

2.1. Création, affichage

#include <forward_list>

// Type liste unidirectionnelle d'entiers
using int_list_t = std::forward_list< int >;

  int_list_t list;                   // Liste vide
  list.push_front( 1 );              // Liste avec un élément : ( 1 )
  list.push_front( 2 );              // Liste avec deux éléments : ( 2 1 )

  // Addition de tous les éléments de la liste
  int somme{ 0 };
  for( auto i : list ) somme += i;

• Écrire une fonction random_list(), sans argument, qui retourne une liste d'entiers ayant des valeurs aléatoires entre 0 et 99 ; le nombre d'éléments de la liste retournée sera lui-même une valeur aléatoire entre 0 et 9.

• Écrire une fonction print_list() qui reçoit en argument une liste d'entiers passée par référence constante et qui affiche cette liste sur la sortie standard (les éléments dans l'ordre séparés par des espaces, le tout encadré par des parenthèses : voir l'exemple ci-dessous).
  
• Écrire une fonction test_21() qui crée une liste avec random_list() puis l'affiche avec print_list().
  
• Écrire la fonction main() qui appelle test_21(). Compiler et exécuter votre programme. Le résultat attendu est, par exemple :

2.2. Application

• Écrire une fonction map_iter() qui reçoit en argument une liste d'entiers passée par référence constante et une fonction de type int( int ), et qui retourne par valeur une liste contenant les résultats de l'application de la fonction aux éléments de la liste initiale.

• Écrire une fonction test_22() qui crée une liste d'entiers aléatoires, l'affiche avec print_list(), lui applique map_iter() avec une fonction lambda multipliant par 3 et affiche le résultat obtenu.
  
• Modifier main() pour tester le fonctionnement de test_22().
  

2.3. Filtrage

• Écrire une fonction filter_iter() qui reçoit en argument une liste d'entiers passée par référence constante et une fonction de type bool( int ) (un prédicat), et qui retourne par valeur une liste contenant uniquement les éléments de la liste initiale vérifiant le prédicat. Vous ignorerez là aussi que la liste retournée est inversée.
  
• Écrire une fonction test_23() qui crée une liste d'entiers aléatoires et l'affiche avec print_list(), lui applique map_iter() avec une fonction lambda multipliant par 3 et affiche le résultat obtenu, puis applique filter_iter() sur le résultat de map_iter() afin de ne conserver que les éléments pairs et affiche le résultat ; vérifier le bon fonctionnement en ajoutant l'appel à main().
  

2.4. Capture

• Le coefficient de multiplication (3) est pour l'instant connu à la compilation. Écrire une fonction test_24() identique à test_23() mais qui utilise comme coefficient de multiplication un nombre compris entre 1 et 5 déterminé aléatoirement via un appel à rand() ; ce coefficient doit être calculé, mémorisé dans une variable locale et affiché avant l'appel à map_iter(). Vérifier le bon fonctionnement en ajoutant l'appel à main().
  

2.5. Réduction

• Écrire une fonction reduce() qui reçoit en argument une liste d'entiers passée par référence constante, un entier et une fonction de type int( int, int ) ; la fonction reçue est appliquée à tous les éléments de la liste de la manière suivante : son premier argument est l'entier reçu en argument par reduce() la première fois, le résultat du précédent appel les autres fois ; son second argument est l'élément courant de la liste ; reduce() retourne le résultat obtenu par le dernier appel de la fonction.
  
• Écrire une fonction test_25() qui crée une liste d'entiers aléatoires, l'affiche avec print_list(), et effectue un appel à reduce() afin de calculer le plus petit des éléments de la liste, et un autre pour le plus grand, vérifier le bon fonctionnement en affichant ces valeurs.
  

3. Récursion (1 point)

3.1. Récursion pour reduce()

reduce() peut-être écrite de manière récursive si on sait déterminer la fin de la récursion, ce qui revient ici à savoir si on est arrivé à la fin de la liste. L'utilisation d'un foreach ne permet pas cette détection, il faut donc utiliser les itérateurs qui sont sous-jacents.

  // Le typage par inférence pourrait être utilisé ici pour la variable it
  for( std::forward_list< int >::iterator it{ l.begin() }; it != l.end(); ++it ) {
    *it = *it * 3;
  }

using int_list_iter_t = int_list_t::const_iterator;

• Écrire une fonction fold_left_aux() de manière récursive ; elle effectue le même calcul que reduce() (l'appel récursif doit se faire après l'application de la fonction reçue en argument), mais ses arguments sont un itérateur constant sur l'élément courant, un itérateur constant de fin, un entier et la fonction de réduction.

int add( int a, int b ) { return a + b; }

int bad()
{
    int i{ 5 };
    return add( i++, i );  // Peut retourner 10 ou 11
}

• Écrire une fonction fold_left()² avec la même signature que reduce() et qui se contente d'appeler fold_left_aux() avec les bons arguments.
• Définir une fonction test_31(), identique à test_25() mais qui remplace l'appel à reduce() par celui à fold_left().
  

3.2. Récursion pour map() et filter()

En utilisant le même principe (fonction auxiliaire et itérateurs), il est possible d'écrire map() et filter() de manière récursive, ce qui a aussi comme conséquence que la liste résultat n'ait pas les éléments inversés (à condition de faire les appels dans le bon ordre !).

• Écrire la fonction map_aux() qui reçoit en argument un itérateur constant sur l'élément courant, un itérateur constant de fin et la fonction à appliquer. Définir map() pour qu'elle appelle map_aux() avec les bons arguments.

// Récursivité non terminale
unsigned fac1( unsigned n ) { return n == 0 ? 1 : n * fac1( n - 1 ); }

// Fonction auxiliaire avec récursivité terminale
void fac2aux( unsigned n, unsigned & res ) { if( n != 0 ) fac2aux( n - 1, res *= n ); }
unsigned fac2( unsigned n ) { unsigned res{ 1 }; fac2aux( n, res ); return res; }

• Écrire la fonction filter_aux() qui reçoit en argument un itérateur constant sur l'élément courant, un itérateur constant de fin et le prédicat. Définir filter() pour qu'elle appelle filter_aux() avec les bons arguments.

• Définir une fonction test_32(), identique à test_24() mais qui remplace les appels à map_iter() et filter_iter() par ceux à map() et filter().
  

4. Partie avancée (0,5 point)

4.1. Application partielle

L'exemple de l'application (map()) a été réalisé en utilisant l'opérateur de multiplication dans une fonction lambda. Il est bien sûr possible d'utiliser, à la place de cette dernière, n'importe quelle autre fonction ayant le bon type.

Il existe par ailleurs, dans la bibliothèque standard C++, une définition sous forme fonctionnelle de la multiplication (std::multiplies) et des autres opérateurs (techniquement, ce sont des objets fonctions).

void g()
{
    // Création d'un objet fonction
    std::multiplies< double > mul_double;
    // Il est bien sûr possible de stocker cet objet fonction dans une
    // variable de type std::function
    std::function< double( double, double ) > f_double{ mul_double };

    // Utilisation de l'objet fonction
    double res{ mul_double( 3.0, -7 )};
    // Utilisation via la variable std::function
    res = f_double( 3.0, -7 );
}

Cependant, cette fonction std::multiplies() a besoin de 2 arguments, alors que, dans notre cas, l'un des arguments est fixé. Il est en général possible, dans les langages fonctionnels, de créer une nouvelle fonction en fixant un ou plusieurs arguments d'une fonction existante, cela s'appelle l'application partielle.

• Définir une fonction test_41(), identique à test_32() mais qui utilise comme second argument de map() une fonction obtenue par application partielle sur std::multiplies(). Vérifier le bon fonctionnement.
  

4.2. Réduction inversée

• Écrire une fonction fold_right() qui récurse avant d'appliquer la fonction reçue en argument.
• Écrire une fonction test_42() qui montre sur un exemple que fold_left() et fold_right() ne donnent pas toujours le même résultat pour une même fonction utilisée pour faire la réduction.