LinkedList Java persistante et immuable

Dans cet article nous allons implémenter une variante persistante et immuable de la LinkedList en Java avec
partage structurel partiel pour des gains d'efficacité temporelle et spatiale.

Introduction

Qu'est-ce qu'une LinkedList

Une liste chaînée est une structure de données composée d'une collection de nœuds où chaque nœud contient une valeur et une référence au nœud suivant dans la séquence. Les opérations telles que l'ajout d'un élément en tête de la liste ou la suppression d'un élément de la tête sont des opérations O(1). Cependant, les opérations telles que l'ajout d'un élément à la fin de la liste ou la suppression d'un élément à la fin sont des opérations O(n) où n est le nombre d'éléments dans la liste.

Pourquoi avons-nous besoin d'une LinkedList immuable

En programmation fonctionnelle, l'immuabilité est un concept clé. L'immuabilité signifie qu'une fois qu'une structure de données est créée, elle
ne peut pas être modifié. Au lieu de cela, une nouvelle structure de données est créée avec les modifications et celle d'origine reste inchangée.

Cette propriété nous permet plusieurs avantages :

1. Sécurité des threads : la structure des données étant immuable, elle peut être partagée sur plusieurs threads sans avoir besoin de synchronisation.
2. Prévisibilité : Puisque la structure des données est immuable, nous pouvons raisonner sur l'état de la structure des données à tout moment.
3. Annuler : La structure de données étant immuable, nous pouvons toujours revenir à un état antérieur en utilisant la version précédente de la structure de données.
4. Débogage : L'immuabilité facilite le débogage puisque la structure des données ne peut pas être modifiée.

Cependant, les collections en Java et puisque cet article se concentre sur LinkedList, sont mutables par défaut. Les raisons peuvent être nombreuses
allant du fait de ne pas y avoir pensé après coup lors de la conception des collections jusqu'aux raisons de performance inhérentes à
structures de données immuables.

Différence entre les collections JDK non modifiables et cette LinkedList

Le JDK fournit des collections non modifiables qui enveloppent les collections originales. Ils prennent en charge l'immuabilité mais ils ne sont pas persistants et ne fournissent pas de véritable méthode sécurisée de type. Ils enveloppent les collections originales et ils
lève une exception lorsqu'une opération de modification est appelée. Ce n'est pas la même chose que l'immuabilité où la structure des données ne peut pas être modifiée du tout tout en garantissant qu'il sera difficile d'obtenir une UnsupportedOperationException au moment de l'exécution.

Persistant vs Immuable

Bien que les termes persistant et immuable soient souvent utilisés de manière interchangeable, ils ont des significations différentes. Si l'immuabilité ne permet pas la modification de la structure des données, la persistance permet le partage de la structure des données lorsqu'elle est modifiée. Cela signifie que lorsqu'une structure de données est modifiée, c'est-à-dire qu'une nouvelle version est créée, des parties de l'ancienne structure de données peuvent être partagées avec la nouvelle, permettant ainsi des gains d'efficacité en termes de temps et d'espace. Cette technique s'appelle partage structurel.

Il existe plusieurs façons d’obtenir la persistance dans les structures de données. Les structures de données vont du simple au complexe, comme l'utilisation d'arbres équilibrés comme les arbres AVL ou Rouge-Noir, à des structures plus complexes comme les arbres Finger et les arbres équilibrés basés sur Radix.

Dans cet article, nous allons implémenter une version plus simple d'une LinkedList persistante et immuable avec partage structurel partiel. La raison en est que LinkedList est une structure de données simple et qu'elle nous aidera à mieux comprendre les concepts d'immuabilité et de persistance et que, généralement, la mise en œuvre de structures de données plus complexes est intrinsèquement une tâche difficile.

Mise en œuvre

Ci-dessous, nous allons implémenter une LinkedList unique persistante et immuable en Java en utilisant une approche étape par étape.

Pour une implémentation complète et des monades et utilitaires supplémentaires pour vous aider dans votre visite de programmation fonctionnelle vers Java, vous pouvez consulter cette superbe petite bibliothèque FunctionalUtils.

Le nom que nous donnerons à notre LinkedList sera SeqList et ce sera une classe générique.

Dans un premier temps, nous devons réfléchir aux opérations que nous allons soutenir dans notre Liste.

1. Ajout à la tête de liste qui va être une opération O(1).
2. Suppression d'un élément de la liste qui sera au pire une opération O(n) si l'élément est situé vers la fin.
3. Ajout à une position arbitraire dans la liste.
4. Opération de filtrage pour filtrer / filtrer les éléments à partir d'un prédicat.
5. Opérations Map et FlatMap pour transformer notre liste en monade pour une composition de fonctions plus facile.

Nous pouvons considérer une LinkedList comme une structure composée de nœuds où chaque nœud comprend :

1. tête détenant une valeur.
2. tail contenant le reste de la liste qui à son tour est une LinkedList composée de la tête et de la queue jusqu'à la fin de la liste.
3. La fin de la liste est représentée par une LinkedList vide, ce qui signifie que la tête et la queue sont nulles.

La mise en œuvre complète peut être trouvée ici

Étant donné que le dernier élément de la liste est une LinkedList vide et que chaque élément est un nœud avec une tête et une queue, nous pouvons représenter notre LinkedList comme une structure de données récursive composée de deux classes :

public record Empty() implements SeqList {
}

public record Cons(T head, SeqList tail) implements SeqList {
}

où Cons est un terme de programmation fonctionnelle nommé Construct qui remonte au langage de programmation Lisp.

Compte tenu de ce qui précède, nous pouvons implémenter l'interface SeqList comme suit :

public sealed interface SeqList permits Empty, Cons {
  /**
   * Creates an empty list.
   *
   * @param  the type of the elements
   * @return an empty list
   */
  static  SeqList empty() {
    return new Empty<>();
  }

  /**
   * Creates a new list with the given elements. The complexity of this method is O(n) where n is
   * the number of elements.
   *
   * @param elements the elements to add
   * @param       the type of the elements
   * @return a new list with the elements added
   */
  @SafeVarargs
  static  SeqList of(T... elements) {
    SeqList list = empty();
    for (int i = elements.length - 1; i >= 0; i--) {
      list = list.add(elements[i]);
    }
    return list;
  }

  /**
   * Prepends the element to the list. The complexity of this method is O(1).
   *
   * @param element the element to add
   * @return a new list with the element prepended
   */
  default SeqList add(T element) {
    return new Cons<>(element, this);
  }
}

Décomposons ce que nous avons écrit ci-dessus :

1. Nous avons créé une interface scellée SeqList qui sera l'interface de notre LinkedList.
2. La méthode empty() crée une liste vide qui est une instance de la classe Empty.
3. La méthode add() ajoute un élément au début de la liste. La complexité de cette méthode est O(1) car nous créons simplement un nouveau nœud avec l'élément donné et la liste actuelle. Cette méthode utilise le Partage structurel car la nouvelle liste partage la queue de la liste actuelle.
4. La méthode of() crée une nouvelle liste avec les éléments donnés. La complexité de cette méthode est O(n) où n est le nombre d’éléments. Comme il est évident, nous partons du dernier élément et l’ajoutons à la liste. C'est parce que nous voulons préserver l'ordre des éléments.

Nous devons mettre en œuvre le reste de nos opérations. Commençons par l'opération de suppression :

/**
   * Removes the first occurrence of the element from the list. If the element is not found, the
   * list is returned as is. The complexity of this method is O(n) where n is the number of
   * elements. It uses structural sharing up to the element to remove. If the element is not found
   * the structural sharing is not utilized.
   *
   * @param element the element to remove
   * @return a new list with the element removed
   * @throws StackOverflowError for infinite lists
   */
  default SeqList remove(T element) {
    if (isEmpty()) {
      return this;
    }
    if (head().equals(element)) {
      return tail();
    }
    return new Cons<>(head(), tail().remove(element));
  }

Et implémentez en outre la méthode tail() et quelques autres méthodes utiles dans nos sous-classes :

public record Cons(T head, SeqList tail) implements SeqList {

  @Override
  public boolean isEmpty() {
    return false;
  }

  @Override
  public Optional headOption() {
    return Optional.ofNullable(head);
  }

  @Override
  public Optional last() {
    if (tail.isEmpty()) {
      return Optional.ofNullable(head);
    }
    return tail.last();
  }
}

public record Empty() implements SeqList {

  @Override
  public boolean isEmpty() {
    return true;
  }

  @Override
  public T head() {
    throw new UnsupportedOperationException("head() called on empty list");
  }

  @Override
  public Optional headOption() {
    return Optional.empty();
  }

  @Override
  public SeqList tail() {
    throw new UnsupportedOperationException("tail() called on empty list");
  }

  @Override
  public Optional last() {
    return Optional.empty();
  }
}

Comme nous pouvons le constater à partir de l'implémentation de la méthode Remove, nous utilisons des appels récursifs pour supprimer l'élément de
la liste. Il s'agit d'un modèle typique de la programmation fonctionnelle où nous utilisons la récursivité pour parcourir la liste et
supprimer l'élément. Des précautions doivent être prises pour éviter les débordements de pile en cas de listes infinies. Une amélioration future pourrait consister à utiliser l'optimisation de la récursion de queue qui n'est pas prise en charge en Java mais pourrait être réalisée à l'aide du trampoline.

Enfin, implémentons les opérations map et flatMap pour transformer notre liste en monade :

/**
   * Applies a map function to the elements of the list. The complexity of this method is O(n) where
   * n is the number of elements.
   * It does not use structural sharing as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the map function
   * @param  the type of the elements of the new list
   * @return a new list with the elements mapped
   * @throws StackOverflowError for infinite lists
   */
  default  SeqList map(Function fn) {
    if (isEmpty()) {
      return empty();
    }
    return new Cons<>(fn.apply(head()), tail().map(fn));
  }

  /**
   * Applies a flat map function to the elements of the list. The complexity of this method is O(n)
   * where n is the number of elements.
   * It does not use structural sharing as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the flat map function
   * @param  the type of the elements of the new list
   * @return a new list with the elements flat mapped
   * @throws StackOverflowError for infinite lists
   */
  default  SeqList flatMap(Function> fn) {
    if (isEmpty()) {
      return empty();
    }
    SeqList mappedHead = fn.apply(head());
    SeqList newTail = tail().flatMap(fn);
    return concat(mappedHead, newTail);
  }

  /**
   * Concatenates two lists. The complexity of this method is O(n) where n is the number of
   * elements.
   *
   * @param list1 the first list
   * @param list2 the second list
   * @param    the type of the elements
   * @return a new list with the elements of the two lists concatenated
   * @throws StackOverflowError for infinite lists
   */
  static  SeqList concat(SeqList list1, SeqList list2) {
    if (list1.isEmpty()) {
      return list2;
    }
    return new Cons<>(list1.head(), concat(list1.tail(), list2));
  }

SeqList list = SeqList.of(1, 2, 3, 4, 5, 6);
SeqList updatedList = list
   .filterOut(number -> number % 2 == 0)
   .map(number -> Math.pow(number, 2));

SeqList list = SeqList.of("a", "b", "c", "d", "e");
SeqList updatedList = list
   .map(letter -> "prefix" + letter + "suffix");

SeqList> list = SeqList.of(SeqList.of(1, 2), SeqList.of(3, 4), SeqList.of(5, 6));
SeqList updatedList = list
   .flatMap(seqList -> seqList);

SeqList list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
  case Empty() -> {
    // do something
  }
  case Cons cons -> {
    //do something else
  }
}