Qu'est-ce qu'une fermeture éclair et comment est-elle liée à une structure arborescente?

15

Je lisais un chapitre de LYAH qui n'avait pas vraiment de sens pour moi. Je comprends que les fermetures à glissière peuvent traverser arbitrairement une structure arborescente, mais j'ai besoin de précisions à ce sujet. De plus, les fermetures à glissière peuvent-elles être généralisées à n'importe quelle structure de données?

ds.data-structures functional-programming tree n_ary_crazy
la source
3
C'est probablement plus approprié pour l' informatique , bien que le travail de généralisation des fermetures à glissière implique un certain nombre de machines techniques.
Dave Clarke
6
Une fermeture éclair est quelque chose que vous devez toujours garder fermé, surtout lorsque vous traversez un arbre.
Andrej Bauer

Réponses:

14

Une fermeture éclair, en général, est une structure de données avec un trou. Les fermetures à glissière sont utilisées pour traverser / manipuler les structures de données, et le trou correspond au foyer actuel de la traversée. Typiquement, il y a également un élément de la structure de données à l'étude, de sorte que l'on a une fermeture éclair (liste) et une liste ou une fermeture éclair (arbre) et un arbre. La fermeture éclair permet au programmeur de se déplacer efficacement autour de la structure de données, même en remplaçant l'élément au foyer. La paire de la fermeture à glissière et l'élément dans le foyer satisfont à la contrainte selon laquelle le placement de l'élément au foyer dans le trou donne la structure de données d'origine.

Les fermetures à glissière peuvent être généralisées à des types de données inductifs arbitraires. Le concept peut être défini de manière indexée par type (voir Types de données indexés par type ). Ils sont également liés à l'idée de la dérivée d'une structure de données , et ont été étudiés dans une perspective théorique de catégorie .

Dave Clarke
la source
2

Une fermeture à glissière est en général une paire de choses: c'est une structure avec un trou, un focus , représentant où vous êtes dans la structure, avec un chemin , enregistrant comment vous êtes arrivé à ce focus. (Ce chemin est la piste de chapelure de LYAH.)

Le chemin est la façon dont vous appliquez réellement les modifications à la structure: "descendez, allez à gauche, augmentez la valeur". En appliquant à plusieurs reprises "go up" ( go_updans l'article de Huet ) à ce stade, vous pouvez revenir sur vos pas et vous retrouver avec une nouvelle copie mutée de la structure d'origine.

Ils peuvent en effet être généralisés à d'autres structures:

Frank Shearar
la source