Structure de données persistante

Ce type de structures de données est particulièrement courant en programmation logique et fonctionnelle. Dans un programme purement fonctionnel, où toute donnée est immuable, les structures de données sont automatiquement totalement persistantes. Les structures persistantes peuvent aussi être obtenues en utilisant des modifications en place des données et peuvent alors être parfois plus efficaces, en temps ou en espace, que leurs contreparties purement fonctionnelles.

Bien que la persistance puisse être obtenue par une simple copie, c'est en général une solution inefficace en temps et en espace, car la plupart des opérations n'effectuent que peu de changements dans une structure de données. Une meilleure solution consiste à exploiter les similarités entre les anciennes versions et la nouvelle, telles que des sous-arbres communs dans un certain nombre de structures d'arbre. Parce qu'il devient rapidement difficile de déterminer quelles sont les parties de la structure effectivement partagées entre plusieurs versions, et parce qu'il est souvent souhaitable de supprimer des versions devenues inutiles, la présence d'un ramasse-miettes s'impose naturellement.

La structure de données persistante la plus simple est sans doute celle de liste simplement chaînée, où chaque élément contient une référence vers l'élément suivant dans la liste. Une telle structure est persistante si les opérations se limitent à extraire un suffixe d'une liste, c'est-à-dire les k derniers éléments pour un certain k, et à y ajouter de nouveaux éléments en tête. Le suffixe peut alors être partagé entre l'ancienne liste et la nouvelle, au lieu d'être dupliqué. Tant que les éléments sont immuables, ce partage reste invisible.

De nombreuses structures de données, telles que les arbres bicolores ou les files, peuvent facilement être adaptées pour être persistantes. Une version persistante de la structure de tableau est la structure de VList introduite en 2002 par Phil Bagwell.