Table des matières

1. Tableaux et tris

1.1. Affichage d'un tableau basique

• Écrire une fonction print_tab() qui reçoit en argument un tableau d'entiers (tableau basique du langage C) 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).
  

Solution possible

#include <iostream>

void print_tab( const int tab[], int size )
{
    std::cout << '[';
    for( int i = 0; i < size; ++i ) {
        std::cout << ' ' << tab[i];
    }
    std::cout << " ]" << std::endl;
}

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

      // Tableau basique de 6 entiers ayant les valeurs indiquées
      int tab[]{ 1, -2, 3, -4, 5, -6 };
  

  
  et qui affiche ce tableau.

Solution possible

void test_11()
{
    std::cout << "*** test_11 ***\n";

    int tab[]{ 1, -2, 3, -4, 5, -6 };
    print_tab( tab, sizeof( tab ) / sizeof( tab[0] ));
}

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

• Utiliser le manipulateur hex avant l'appel à print_tab() et vérifier que vous obtenez :

Solution possible

#include <iomanip>

void test_11()
{
    std::cout << "*** test_11 ***\n";

    int tab[]{ 1, -2, 3, -4, 5, -6 };
    std::cout << std::hex;
    print_tab( tab, sizeof( tab ) / sizeof( tab[0] ));
}

1.2. Affichage d'un tableau C++

• Écrire une fonction print_tab() qui reçoit en argument un tableau d'entiers (vector du langage C++) et qui affiche ce tableau sur la sortie standard.
  

#include <vector>

// C'est un type générique. Pour un tableau d'entiers : std::vector< int >
// Nommons ce 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

Solution possible

#include <vector>

using int_tab_t = std::vector< int >;

void print_tab( const int_tab_t & tab )
{
    std::cout << "[";
    for( auto v : tab ) std::cout << " " << v;
    std::cout << " ]\n";
}

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

      // Tableau de 6 entiers ayant les valeurs indiquées
      // IL FAUT ICI UTILISER DES ACCOLADES :
      int_tab_t tab{ -1, 2, -3, 4, -5, 6 };
  

  
  et qui affiche ce tableau.

Solution possible

void test_12()
{
    std::cout << "*** test_12 ***\n";

    int_tab_t tab{ -1, 2, -3, 4, -5, 6 };
    print_tab( tab );
}

• Ajouter dans main() l'appel à test_12(). Compiler et exécuter votre programme, vérifier le résultat.

1.3. Affichage d'un tableau quelconque

Une autre fonction print_tab() serait nécessaire pour l'affichage d'un tableau de taille fixe, connue à la compilation (array). C++20 a introduit le type span pour généraliser le concept d'une vue, de taille connue à la compilation ou non, sur une séquence finie et contigüe d'éléments de même type (une étendue). Pour notre exercice avec les entiers, nous pouvons définir :

#include <span>

using int_span_t = std::span< int >;   // par défaut : taille dynamique de l'étendue

• Écrire une fonction print_span() qui reçoit en argument une étendue et qui affiche celle-ci sur la sortie standard.
  

Solution possible

#include <span>

using int_span_t = std::span< int >;
using const_int_span_t = std::span< const int >;

void print_span( const_int_span_t span )
{
    std::cout << "[";
    for( auto v : span ) std::cout << " " << v;
    std::cout << " ]\n";
}

• Écrire une fonction test_13() qui affiche son nom, qui utilise la fonction print_span()pour afficher à la fois un tableau basique et un tableau C++.

Solution possible

void test_13()
{
    std::cout << "*** test_13 ***\n";

    int tab1[]{ 1, -2, 3, -4, 5, -6 };
    print_span( tab1 );
    int_tab_t tab2{ -1, 2, -3, 4, -5, 6 };
    print_span( tab2 );
}

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

• Écrire une fonction random_span() qui reçoit en argument une étendue d'entiers et qui remplace tous les éléments de celle-ci par des valeurs aléatoires comprises entre -10 et 10.
  

Solution possible

#include <cstdlib>
#include <ctime>

void random_span( int_span_t span )
{
    for( auto & v : span ) v = std::rand() % 21 - 10;
}

• Écrire une fonction test_14() qui crée un tableau de 10 entiers et appelle random_span() puis print_span() avec le tableau comme argument.
  

Solution possible

void test_14()
{
    std::cout << "*** test_14 ***\n";

    int_tab_t tab( 10 );
    random_span( tab );
    print_span( tab );
}

• Ajouter à la fonction main() un appel à test_14(). Exécuter plusieurs fois votre programme pour vérifier que tous les nombres demandés, et seulement eux, peuvent apparaître dans le tableau.
  

Solution possible

int main()
{
    std::srand( std::time( nullptr ));

    //test_11();
    //test_12();
    //test_13();
    test_14();
    return 0;
}

1.5. Tri par ordre croissant

• Écrire une fonction sort_span() qui reçoit en argument une étendue d'entiers et qui trie les éléments de cette étendue par ordre croissant.
  

Solution possible

#include <utility>

void sort_span( int_span_t tab )
{
    for( size_t i{ 0 }; i < tab.size(); ++i ) {
        size_t min_index{ i };
        for( size_t j{ i + 1 }; j < tab.size(); ++j ) {
            if( tab[j] < tab[min_index] ) min_index = j;
        }
        std::swap( tab[i], tab[min_index] );
    }
}

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

Solution possible

void test_15()
{
    std::cout << "*** test_15 ***\n";

    int_tab_t tab( 10 );
    random_span( tab );
    print_span( tab );
    sort_span( tab );
    print_span( tab );
}

1.6. 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.
  

Solution possible

bool less( int a, int b )
{
    return a < b;
}

bool greater( int a, int b )
{
    return a > b;
}

• Modifier la fonction sort_span() pour recevoir comme second argument un pointeur sur une fonction de comparaison ; le tri se fera en utilisant cette fonction.
  

Solution possible

void sort_span( int_span_t tab, bool ( *comp )( int, int ))
// ou
//void sort_span( int_span_t tab, bool comp( int, int ))
{
    for( size_t i{ 0 }; i < tab.size(); ++i ) {
        size_t min_index{ i };
        for( size_t j{ i + 1 }; j < tab.size(); ++j ) {
            if( comp( tab[j], tab[min_index] )) min_index = j;
        }
        std::swap( tab[i], tab[min_index] );
    }
}

• Modifier la fonction test_15() pour trier le tableau une première fois en utilisant less(), une seconde avec greater().
  

Solution possible

void test_15()
{
    std::cout << "*** test_15 ***\n";

    int_tab_t tab( 10 );
    random_span( tab );
    print_span( tab );
    sort_span( tab, &less );
    print_span( tab );
    sort_span( tab, greater );
    print_span( tab );
}

• Vérifier la bonne exécution en exécutant plusieurs fois votre programme.
  
  

1.7. 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 ));
}

• Modifier la fonction sort_span() pour que son second argument soit du type std::function.
  
  

Solution possible

#include <functional>

void sort_span( int_span_t tab, std::function< bool( int, int ) > comp )
{
    for( size_t i{ 0 }; i < tab.size(); ++i ) {
        size_t min_index{ i };
        for( size_t j{ i + 1 }; j < tab.size(); ++j ) {
            if( comp( tab[j], tab[min_index] )) min_index = j;
        }
        std::swap( tab[i], tab[min_index] );
    }
}

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).

• Ajouter dans la fonction test_15() des appels à sort_span() pour faire un tri, croissant puis décroissant, sur la valeur absolue des nombres.
  

Solution possible

void test_15()
{
    std::cout << "*** test_15 ***\n";

    int_tab_t tab( 10 );
    random_span( tab );
    print_span( tab );
    sort_span( tab, &less );
    print_span( tab );
    sort_span( tab, greater );
    print_span( tab );
    sort_span( tab, []( int a, int b ) { return std::abs( a ) < std::abs( b ); } );
    print_span( tab );
    sort_span( tab, []( int a, int b ) { return std::abs( a ) > std::abs( b ); } );
    print_span( tab );
}

• Vérifier la bonne exécution en exécutant plusieurs fois votre programme.
  
  

2. Listes

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.

Solution possible

int_list_t random_list()
{
    int_list_t list;
    size_t nb{ static_cast< size_t >( std::rand() % 10 )};
    for( size_t i{ 0 }; i < nb; ++i ) list.push_front( std::rand() % 100 );
    return list;
}

• Écrire une fonction print_list() qui reçoit en argument une liste d'entiers 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).
  

Solution possible

void print_list( const int_list_t & list )
{
    std::cout << "(";
    for( auto i : list ) std::cout << " " << i;
    std::cout << " )\n";
}

• Écrire une fonction test_21() qui crée une liste avec random_list() puis l'affiche avec print_list().
  

Solution possible

void test_21()
{
    std::cout << "*** test_21 ***\n";

    print_list( random_list() );
}

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

Solution possible

int main()
{
    std::srand( std::time( nullptr ));
    test_21();
}

2.2. Application

• Écrire une fonction map_iter() qui reçoit en argument une liste d'entiers et une fonction de type int( int ), et qui retourne une nouvelle liste contenant les résultats de l'application de la fonction aux éléments de la liste initiale (qui n'est donc pas modifiée).

Solution possible

int_list_t map_iter( const int_list_t & list, std::function< int( int ) > func )
{
    int_list_t res;
    for( auto i : list ) res.push_front( func( i ));
    return res;
}

• É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.
  

Solution possible

void test_22()
{
    std::cout << "*** Test 22 ***\n";

    auto list{ random_list() };
    print_list( list );
    auto res{ map_iter( list, []( int a ) { return a * 3; })};
    print_list( res );
}

• 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 et une fonction de type bool( int ) (un prédicat), et qui retourne 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.
  

Solution possible

int_list_t filter_iter( const int_list_t & list, std::function< bool( int ) > func )
{
    int_list_t res;
    for( auto i : list ) if( func( i )) res.push_front( i );
    return res;
}

• É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().
  

Solution possible

void test_23()
{
    std::cout << "*** Test 23 ***\n";

    auto list{ random_list() };
    print_list( list );
    list = map_iter( list, []( int a ) { return a * 3; });
    print_list( list );
    list = filter_iter( list, []( int a ) { return a % 2 == 0; });
    print_list( list );
}

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().
  

Solution possible

void test_24()
{
    std::cout << "*** Test 24 ***\n";

    auto list{ random_list() };
    print_list( list );
    int coef{ std::rand() % 5 + 1 };
    std::cout << "coef = " << coef << "\n";
    list = map_iter( list, [coef]( int a ) { return a * coef; });
    print_list( list );
    list = filter_iter( list, []( int a ) { return a % 2 == 0; });
    print_list( list );
}

2.5. Réduction

• Écrire une fonction reduce() qui reçoit en argument une liste d'entiers, 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.
  

Solution possible

int reduce( const int_list_t & list, int init,
            std::function< int( int, int ) > func )
{
    for( int i : list ) init = func( init, i );
    return init;
}

• É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 la somme des éléments pairs de la liste, et un autre pour la somme des éléments impairs, vérifier le bon fonctionnement en affichant ces valeurs.
  

Solution possible

void test_25()
{
    std::cout << "*** Test 25 ***\n";

    auto list{ random_list() };
    print_list( list );
    std::cout << "somme pairs = "
              << reduce( list, 0,
                         []( int a, int b ) { return b % 2 == 0 ? a + b : a; })
              << "\n";
    std::cout << "somme impairs = "
              << reduce( list, 0,
                         []( int a, int b ) { return b % 2 != 0 ? a + b : a; })
              << "\n";
}

3. Récursion

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
}

Solution possible

int fold_left_aux( int_list_iter_t it, int_list_iter_t end, int init,
                   std::function< int( int, int ) > func )
{
    if( it == end ) return init;
    init = func( init, *it );
    return fold_left_aux( ++it, end, init, func );

    // À la place des 2 dernières instructions :
    // Écriture concise incorrecte
    //return fold_left_aux( ++it, end, func( init, *it ), func );
    // Écriture concise correcte
    //return fold_left_aux( std::next( it ), end, func( init, *it ), func );
}

• É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.

Solution possible

int fold_left( const int_list_t & list,
               int init,
               std::function< int( int, int ) > func )
{
    return fold_left_aux( list.cbegin(), list.cend(), init, func );
}

• Définir une fonction test_31(), identique à test_25() mais qui remplace l'appel à reduce() par celui à fold_left().
  

Solution possible

void test_31()
{
    std::cout << "*** Test 31 ***\n";

    auto list{ random_list() };
    print_list( list );
    std::cout << "somme pairs = "
              << fold_left( list, 0,
                            []( int a, int b ) { return b % 2 == 0 ? a + b : a; })
              << "\n";
    std::cout << "somme impairs = "
              << fold_left( list, 0,
                            []( int a, int b ) { return b % 2 != 0 ? a + b : a; })
              << "\n";
}

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; }

Solution possible

Version sans accumulateur :

int_list_t map_aux( int_list_iter_t it, int_list_iter_t end,
                    std::function< int( int ) > func )
{
    if( it == end ) return int_list_t{};
    auto current{ *it };
    auto res{ map_aux( ++it, end, func )};
    res.push_front( func( current ));
    return res;
}

int_list_t map( const int_list_t & list, std::function< int( int ) > func )
{
    return map_aux( list.cbegin(), list.cend(), func );
}

Version avec accumulateur :

void map_aux( int_list_iter_t it, int_list_iter_t end,
              std::function< int( int ) > func, int_list_t & res )
{
    if( it == end ) return;
    map_aux( std::next( it ), end, func, res );
    res.push_front( func( *it ));
}

int_list_t map( const int_list_t & list, std::function< int( int ) > func )
{
    int_list_t res;
    map_aux( list.cbegin(), list.cend(), func, 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.

Solution possible

int_list_t filter_aux( int_list_iter_t it, int_list_iter_t end,
                                     std::function< bool( int ) > func )
{
    if( it == end ) return int_list_t{};
    auto current{ *it };
    auto res{ filter_aux( ++it, end, func )};
    if( func( current )) res.push_front( current );
    return res;
}

int_list_t filter( const int_list_t & list, std::function< bool( int ) > func )
{
    return filter_aux( list.cbegin(), list.cend(), func );
}

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

Solution possible

void test_32()
{
    std::cout << "*** Test 32 ***\n";

    auto list{ random_list() };
    print_list( list );
    int coef{ std::rand() % 5 + 1 };
    std::cout << "coef = " << coef << "\n";
    list = map( list, [coef]( int a ) { return a * coef; });
    print_list( list );
    list = filter( list, []( int a ) { return a % 2 == 0; });
    print_list( list );
}

4. Pour aller plus loin

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.
  

Solution possible

#include <functional>

void test_41()
{
    std::cout << "*** Test 41 avec lambda ***\n";

    // Avec une fonction lambda
    auto list{ random_list() };
    print_list( list );
    int coef{ std::rand() % 5 + 1 };
    std::cout << "coef = " << coef << "\n";
    auto mul_coef = [coef]( int a ) { return std::multiplies< int >()( a, coef ); };
    list = map( list, mul_coef );
    print_list( list );
    list = filter( list, []( int a ) { return a % 2 == 0; });
    print_list( list );

    // Avec std::bind
    using namespace std::placeholders;  // for _1, _2, _3...

    std::cout << "*** Test 41 avec std::bind ***\n";

    list = random_list();
    print_list( list );
    coef = std::rand() % 3 + 1;
    std::cout << "coef = " << coef << "\n";
    list = filter(
            map( list, std::bind( std::multiplies< int >(), _1, coef )),
            []( int a ) { return a % 2 == 0; }
    );
    print_list( list );
}

4.2. Réduction inversée

La fonction fold_left() parcourt la liste de gauche à droite en appelant la fonction reçue en argument avec comme premier opérande le résultat de la précédente itération (ou la valeur initiale pour la première itération) et comme second opérande l'élément courant de la liste. Ainsi, pour la liste  ( 1 2 3 ) et la fonction  + , fold_left() effectue  (( 0 + 1 ) + 2 ) + 3 .

Les langages fonctionnels proposent classiquement aussi une fonction fold_right() qui parcourt la liste de droite à gauche en appelant la fonction reçue en argument avec comme premier opérande l'élément courant de la liste et comme second opérande le résultat de l'itération suivante (ou la valeur initiale pour la dernière itération). Avec le même exemple, fold_right() effectue  1 + ( 2 + ( 3 + 0 ))) .

• Écrire une fonction récursive fold_right().
• É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.

Solution possible

int fold_right_aux( int_list_iter_t it, int_list_iter_t end, int init,
                    std::function< int( int, int ) > func )
{
    if( it == end ) return init;
    // Version jusqu'en 2024.
    //return func( fold_right_aux( std::next( it ), end, init, func ), *it );
    // À partir de 2025, version conforme à OCaml ou Haskell (mais voir question suivante)
    return func( *it, fold_right_aux( std::next( it ), end, init, func ));
}

int fold_right( int_list_t & list, int init,
               std::function< int( int, int ) > func )
{
    return fold_right_aux( list.cbegin(), list.cend(), init, func );
}

void test_42()
{
    std::cout << "*** Test 42 ***\n";

    auto list{ random_list() };
    print_list( list );
    auto minus = []( int x, int y ) { return x - y; };
    std::cout << "fold_left : "
              << fold_left( list, 0, minus )
              << "\n";
    std::cout << "fold_right : "
              << fold_right( list, 0, minus )
              << "\n";
}

4.3. Autre réduction inversée

Une autre variante consiste à parcourir la liste comme fold_right() tout en conservant l'ordre des arguments de fold_left() : le premier opérande est le résultat de l'itération suivante (ou la valeur initiale pour la dernière itération) et le second opérande est l'élément courant de la liste. Toujours avec le même exemple, cette variante effectue  (( 0 + 3 ) + 2 ) + 1 .

• Écrire une fonction récursive fold_right_other() réalisant cette réduction.
• Écrire une fonction test_43() qui montre sur un exemple que fold_left(), fold_right() et fold_right_other() ne donnent pas toujours le même résultat pour une même fonction utilisée pour faire la réduction.

Solution possible

int fold_right_other_aux( int_list_iter_t it, int_list_iter_t end, int init,
                          std::function< int( int, int ) > func )
{
    if( it == end ) return init;
    return func( fold_right_other_aux( std::next( it ), end, init, func ), *it );
}

int fold_right_other( int_list_t & list, int init,
               std::function< int( int, int ) > func )
{
    return fold_right_other_aux( list.cbegin(), list.cend(), init, func );
}

void test_43()
{
    std::cout << "*** Test 43 ***\n";

    auto list{ random_list() };
    print_list( list );
    auto double_plus = []( int x, int y ) { return x + x + y; };
    std::cout << "fold_left : "
              << fold_left( list, 0, double_plus )
              << "\n";
    std::cout << "fold_right : "
              << fold_right( list, 0, double_plus )
              << "\n";
    std::cout << "fold_right_other : "
              << fold_right_other( list, 0, double_plus )
              << "\n";
}