Xavier Leroy
Collège de France
Science du logiciel
Année 2022-2023
Structures de données persistantes
Systèmes de numération et types non réguliers
Un système de numération permet de représenter efficacement de grands nombres en donnant des poids différents aux chiffres successifs (par exemple, 1, 10, 100, 1 000, etc.). Cette idée inspire aussi la conception de structures persistantes remarquablement efficaces, notamment pour les listes à accès direct et les files de priorité. Nous décrirons ensuite l'utilisation de types algébriques non réguliers pour implémenter de telles structures de manière plus simple et mieux contrôlée par le typage. Nous terminerons par l'étude des « finger trees » de Hinze et Paterson, une structure polyvalente qui applique plusieurs de ces techniques.
Sciences du logiciel - Xavier Leroy