Xavier Leroy
Collège de France
Science du logiciel
Année 2022-2023
Structures de données persistantes
Concilier amortissement et persistance : de l'importance de la paresse
Dans ce cours, nous nous intéresserons aux structures de données persistantes dont l'implémentation utilise « sous le capot » des structures impératives et de la mutation en place, tout en préservant une interface purement fonctionnelle. Nous partirons des tableaux fonctionnels de Baker, qui combinent un tableau impératif et des liste de différences, puis introduirons progressivement la technique des « fat nodes » de Driscoll, Sarnak, Sleator et Tarjan, qui donne un procédé systématique pour rendre persistante une structure d'arbre impérative.
Sciences du logiciel - Xavier Leroy