2  Fonctions pures ou impures : des effets de bord

AFFAIRE(

)

2.1 Fonctions pures et impures

AFFAIRE(

  • définir la pureté - maths : théorie des probas
  • exo 1 caractérisation théorique par duplication

)

Exercice 2.1 (Une caractérisation de la pureté) Comment caractériser la pureté

2.2 Logique contre efficacité

AFFAIRE(

  • exo 2 exemple des nat pour comprendre le problème (logique vs efficacité)
    • somme alternative avec modification en place
    • comparaison : logique vs efficacité )

2.3 Approche pragmatique : immutabilité aux interfaces, mutabilité confinée

AFFAIRE(

  • exo 3 - approche pragmatique - exemple du produit
    • algorithme sur des listes
    • problèmes en API standard Java : le choix tardif de l’immutabilité - notamment pour les listes
    • comparaison tableaux et listes chaînées pour les listes mutables de Java

)

Exercice 2.2 (Entiers naturels : Implémentation optimisée par une liste de chiffres) Les deux implémentations précédentes des entiers naturels, par induction (récurrence) et par restriction respectivement, présentent des défauts : la première est inefficace, représentant un entier naturel \(n\) par un chaînage de \(n + 1\) objets, la seconde impose une limite en taille aux entiers naturels, qui ne peuvent dépasser \(2^{31}\) puisque leur représentation en base deux comporte \(32\) chiffres au maximum, et qu’ils sont relatifs (signés comme on dit en informatique), ce qui fait un perdre un chiffre codant le signe. Pour résoudre ces deux problèmes, nous allons représenter un entier naturel en une certaine base (typiquement dix) par une liste de chiffres, précisément un tableau de chiffres, et implémenter les calculs qu’on apprend en école primaire et au collège avec les retenues.

  • Calculer une approximation de \(2^{32}\) de tête. Quel est l’intervalle décrit par des entiers naturels de \(n\) chiffres en base \(b\) ?
  • Définir une nouvelle classe GrandNat implémentant Nat.
    • Définir une constante statique (associée à la classe et non aux objets de la classe) base de type Nat. L’initialiser à 10.
    • Définir un attribut de type List<Integer> représentant la liste de chiffres. On requiert que cette liste soit immutable pour garantir de bonnes propriétés logiques et de type tableau pour permettre un accès en temps constant à chaque chiffre.
    • Définir deux constructeurs, l’un ayant pour paramètre un tableau d’entiers de type Integer..., dit varargs, qui permet d’appeler le constructeur en notant les éléments du tableau comme une suite d’arguments, l’autre acceptant une liste d’entiers de type Integer. À chaque fois, vérifier l’entrée et créer une liste immutable de type tableau. Indication : demander à une IA comment créer une ArrayList qui soit immutable à partir d’une liste donnée ou d’une suite finie de valeurs (de style varargs).
  • Ajouter à l’interface Nat les accesseurs qui vous paraissent utiles pour cette nouvelle classe d’implémentation.
  • Définir tous les accesseurs de la classe. La méthode predecesseur requiert de développer un algorithme de soustraction.
  • Définir la méthode somme en réalisant les sommes des chiffres à partir des unités, et en retenant 1 si la somme dépasse la valeur de la base (moins une unité). On pourra prendre une liste chaînée de type LinkedList<Integer> comme structure intermédiaire pour stocker les résultats, pour éviter tout problème de redimensionnement, puis créer à partir d’elle la liste immutable de type tableau.
  • Définir la méthode produit en utilisant la multiplication russe, dans la base fixée, alors qu’elle est généralement utilisée en base deux. Il s’agit d’une formalisation algébrique de la multiplication qu’on pose. Indication : demander à une IA de décrire l’algorithme de la multiplication russe, en précisant si nécessaire que vous voulez généraliser la méthode à une base autre que deux.
class GrandNat implements Nat {
    private final static Nat base = new IntRestreint(10); // base associée à la classe et non aux objets (car static)
    
    private List<Integer> chiffres; // liste immutable de type tableau pour l'efficacité de l'accès
    
    public GrandNat(Integer... chiffres) {
        var c = List.of(chiffres); // Liste immutable de type tableau
        if (c.stream().allMatch(x -> (x >= 0) && (x < base.valeurInt()))) {
            this.chiffres = c;
        }else{
            throw new IllegalArgumentException("Grand Nat : requiert des chiffres entre 0 et base - 1");
        }
    }

    public GrandNat(List<Integer> chiffres) {
        if (chiffres.isEmpty()) {
            this.chiffres = List.of(0); // liste immutable de taille 1 - type tableau
        } else if (chiffres.stream().allMatch(x -> (x >= 0) && (x < base.valeurInt()))) {
            this.chiffres = List.copyOf(chiffres); // copie immutable - type tableau
        } else {
            throw new IllegalArgumentException("Grand Nat : requiert des chiffres entre 0 et base - 1");
        }
    }

    @Override
    public boolean estZero() {
        Predicate<Integer> estNul = x -> x.intValue() == 0;
        return this.chiffres.stream().allMatch(estNul); // Style fonctionnel 
    }

    @Override
    public Nat predecesseur() {
      ...
    }

    @Override
    public int valeurInt() {
        return this.chiffres.stream().reduce(0, (x, y) -> base.valeurInt() * x + y); // Style fonctionnel 
    }

    @Override
    public List<Integer> chiffres() {
        return this.chiffres;
    }

    @Override
    public Nat zero() {
        return new GrandNat(0);
    }

    @Override
    public Nat successeur() {
        return this.somme(new GrandNat(1));

    ...
}

Pour le produit, il est possible d’utiliser la multiplication russe, en base b. Cette approche est une adaptation de la multiplication russe, où on divise par b à chaque étape au lieu de deux, et explique le procédé qu’on apprend enfant en posant les multiplications. Voici l’algorithme, pour deux entiers naturels x et y, représentés par des listes de chiffres en base b, les unités étant en fin de liste.

  1. Initialiser un total à 0 et un exposant p à 0 pour le multiplicateur qui sera la puissance b^p.

  2. Tant que x > 0 :

    1. Calculer le reste r = x % b, ce qui revient à prendre le dernier chiffre de x.
    2. Ajouter au total r * y * b^p. Pour calculer r * y, on fait le produit de y par r, ce qui est simple puisque r < base, résultat qu’on peut mémoriser pour s’en resservir, puis pour multiplier par la puissance de b, on ajoute en fin p zéros.
    3. x = x / b (division entière) : on retire le dernier élément qui correspond aux unités.
    4. p = p + 1 : le multiplicateur est donc multiplié par b.

  3. Le total est le résultat final.

🧮 Exemple avec 47 * 42 en base 10

Étape x r = x%b y (constant) Multiplicateur b^p Ajout (r * y * b^p) Total cumulé
1 47 7 42 10^0 = 1 7 * 42 * 1 = 294 294
2 4 4 42 10^1 = 10 4 * 42 * 10 = 1680 1974
3 0 - - - - 1974

Vérification : 47 × 42 = 1974 ✅

L’algorithme repose sur l’identité

  x * y = ((x / b) * b + (x % b)) * y 
        = (x / b) * b * y + (x % b) * y

et on itère avec le produit (x / b) * y * b, b étant le premier multiplicateur.

Pratiquement, lorsque des calculs sont faits sur des listes en ajoutant en début et en fin des éléments, on peut utiliser une liste chaînée, de type LinkedList, qui est à vrai dire doublement chaînée. Cela évite les redimensionnements rencontrés avec des tableaux de type ArrayList, qui obligent à créer un nouveau tableau et à recopier l’ancien.

Voici quelques explications.

📚 Choisir entre Liste Chaînée et Tableau (Array) : Guide pour Débutants

Pour choisir entre une liste chaînée et un tableau (ou tableau dynamique comme ArrayList), on analyse les opérations principales qu’on va effectuer sur la structure de données. Voici les critères clés :

  1. Recenser les opérations principales – Listez les actions fréquentes que vous ferez sur votre structure :

    • Accès fréquent à des éléments par position ?
    • Insertions/suppressions fréquentes au début/milieu ?
    • Beaucoup d’ajouts/suppressions en fin de liste ?
    • Besoin de parcourir séquentiellement toute la liste ?

  2. Critères de choix par opération

Opération Meilleure structure Explication
Accès par index
(get(i))		 🏆 Tableau Accès direct en O(1). Liste chaînée : O(n) (doit parcourir depuis le début)
Insertion/suppression au début 🏆 Liste Chaînée O(1). Tableau : O(n) (doit décaler tous les éléments)
Insertion/suppression à la fin ⚖️ Les deux Tableau : O(1) amorti. Liste chaînée : O(1) si doublement chaînée
Insertion/suppression au milieu 🏆 Liste Chaînée O(1) si on a déjà la position. Tableau : O(n) (décalage)
Parcours séquentiel ⚖️ Les deux O(n) dans les deux cas
Mémoire prévisible 🏆 Tableau Allocation contiguë en mémoire. Liste : surcharge des pointeurs
  1. Exemples concrets
  • Cas 1 : Lecteur de musique (playlist)
    • Opérations : Ajout/suppression fréquente en début/fin, parcours séquentiel
    • Choix : Liste chaînée (insertions/suppressions rapides, accès séquentiel)
  • Cas 2 : Système de réservation (places numérotées)
    • Opérations : Accès aléatoire par numéro, peu de modifications
    • Choix : Tableau (accès instantané à n’importe quelle position)
      Cas 3 : Historique de navigation
    • Opérations : Ajouts fréquents en fin, suppressions occasionnelles au milieu
    • Choix : Tableau dynamique (ArrayList), car optimisé pour l’ajout en fin
  1. Pièges courants
  • Tableau dynamique :
    • Insertion au milieu coûteuse (décalage)
    • Redimensionnement possible (coût temporaire)
  • Liste chaînée :
    • Accès aléatoire lent
    • Mémoire supplémentaire pour les pointeurs
    • Moins “cache-friendly” (données dispersées)

💡 Conseils pratiques

  1. Commencez par lister les opérations dominantes dans votre algorithme
  2. Tableau si :
    • Besoin d’accès aléatoire
    • Taille relativement stable
    • Opérations principalement en fin de liste
  3. Liste chaînée si :
    • Insertions/suppressions fréquentes au début/milieu
    • Taille très variable
    • Parcours séquentiel uniquement

⚖️ En cas de doute : En pratique, les tableaux dynamiques (comme ArrayList) sont souvent préférés car plus efficaces en mémoire et pour l’accès aléatoire, sauf si les insertions en milieu de liste sont critiques.

flowchart TD
    A[Quelles opérations ?] --> B{Accès aléatoire fréquent ?}
    B -->|Oui| C[Tableau]
    B -->|Non| D{Insertions ou suppressions au début ou milieu ?}
    D -->|Oui| E[Liste Chaînée]
    D -->|Non| F{Principalement ajouts en fin ?}
    F -->|Oui| C
    F -->|Non| G[Les deux conviennent]

Figure 2.1: Listes chaînées vs tableaux : Résumé des critères

Lorsqu’on implémente un tel algorithme, il est utile de définir des fonctions adjointes (static) de manière à simplifier l’implémentation avec une décomposition adaptée à l’algorithme. Voici ce qu’on pourrait obtenir comme décomposition maximale pour le produit. Cette implémentation se lit facilement car elle constitue une traduction de l’algorithme, au même niveau d’abstraction.

    @Override
    public Nat produit(Nat n) {
        var total = chiffresModifiablesInitialisesAZero();
        var tableMultiplication = nouvelleTableMultiplication();
        var exposant = 0; // exposant du multiplicateur : base^exposant
        var x = copieModifiableChiffresNonModifiables(this.chiffres);
        while(possedeChiffres(x)){
            var r = unite(x);
            var ry = multiplicationParChiffreEnMemorisant(r, n.chiffres(), tableMultiplication);
            multiplierParPuissanceBase(exposant, ry);
            sommer(total, ry);
            diviserParBase(x);
            exposant++;
        }
        return new GrandNat(total);
    }

Il reste à implémenter toutes les fonctions adjointes, qui réalisent les difficultés plus concrètes et techniques, mais les séparent.

    /*
   * Fonction adjointe créant une liste chaînée pour des chiffres modifiables, initialisée à zéro (liste contenant uniquement 0).
   */
  private static LinkedList<Integer> chiffresModifiablesInitialisesAZero() {
    ...
  }
  /*
   * Fonction adjointe renvoyant un tableau (ArrayList) contenant `base` valeurs, utilisé pour mémoriser les résultats des calculs répétés.
   * Initialisation de chaque résultat par la valeur `null`, pour signifier que le résultat n'a jamais été calculé. 
   */
  private static ArrayList<LinkedList<Integer>> nouvelleTableMultiplication(){
    ...        
  }
  /*
   * Fonction adjointe renvoyant une copie des chiffres, modifiable facilement car la copie est une liste chaînée.    
   */
  private static LinkedList<Integer> copieModifiableChiffresNonModifiables(List<Integer> chiffres) {
    ...
  }
  /*
   * Fonction adjointe donnant le chiffre des unités d'une liste chaînée de chiffres.
   * Convention : du début à la fine de la liste, les puissances de la base diminuent ; le chiffre des unités est le dernier élément.
   */
  private static Integer unite(LinkedList<Integer> chiffres){
    ...
  }
  /*
   * Fonction adjointe testant si la représentation numérique sous forme d'une liste a des chiffres. 
   * Convention : quand la représentation n'a aucun chiffre, elle correspond à la valeur nulle. Cependant, nous appliquons plutôt la représentation suivante pour zéro : un unique chiffre, 0. 
   */
  private static boolean possedeChiffres(LinkedList<Integer> chiffres){
    ...
  }
  /*
   * Fonction adjointe calculant le produit par un chiffre (nombre entre 0 et base - 1).
   * Précondition :  0 <= n < base, x de type tableau (sinon inefficace), memo de taille base.
   * Le tableau mémorise les résultats. S'il n'a pas été calculé avant, alors la valeur est null et initialisée à la fin.
   * Une copie est renvoyée comme résultat pour éviter tout effet de bord.
   */
  private static LinkedList<Integer> multiplicationParChiffreEnMemorisant(int n, List<Integer> x, ArrayList<LinkedList<Integer>> memo){
    ...
  }
  /* 
   * Fonction adjointe calculant le produit par une puissance de la base modifiant en place.
   * Précondition :  0 <= exposant.
   */
  private static void multiplierParPuissanceBase(int exposant, LinkedList<Integer> x){
    ...
  }
  /* 
   * Fonction adjointe calculant la somme et modifiant en place la première liste.
   * Implémentation utilisant des itérateurs positionnés en fin : les listes chaînées sont en fait doublement chaînées.
   */
  private static void sommer(LinkedList<Integer> x, LinkedList<Integer> y){
    ...
  }
  /* 
   * Fonction adjointe calculant la division par la base.
   * Implémentation : une simple suppression du chiffre en fin de liste (correspondant aux unités).
   */
  private static void diviserParBase(LinkedList<Integer> x){
    ...
  }