01 - Structures de données persistantes : Introduction aux structures persistantes et à la programmation purement fonctionnelle

Xavier LeroyCollège de FranceScience du logicielAnnée 2022-2023Structures de données persistantesIntroduction aux structures persistantes et à la programmation purement fonctionnelleCe premier cours décrira l'émergence des structures de données persistantes dans deux contextes historiques différents : l'émergence des langages de programmation purement fonctionnels et de leurs approches équationnelles de dérivation et de vérification des programmes, d'une part, et de l'autre l'apparition de besoins nouveaux, notamment en algorithmique géométrique, de partager efficacement les représentations en mémoire de plusieurs structures de données qui diffèrent en peu de points. Nous verrons au passage nos premiers exemples de structures persistantes, à base de listes, d'arbres binaires, ou de tableaux avec historiques de modifications.