En effet, je n'avais pas vu ton commentaire sur cette structure, c'est intéressant. En regardant en diagonale, j'ai l'impression que ce qui est fait est :
Un tableau est un triplet (modification avant, tableau, modifications après), où modification avant est une liste, et modifications après est une liste (de modifications).
Pour récupérer la version i du tableau, il faut effectuer les modifications sur le vrai tableau, et le faire bouger dans la liste en mettant à la place la modification nécessaire pour revenir (vers la gauche ou la droite). En gros, on se demande si la version est à gauche où à droite (en fonction de i), et si elle est à droite, on pop le premier élément de droite, on l'applique au tableau du milieu, et on push l'inverse de la transformation appliquée à gauche (jusqu'à ce que l'on soit sur le tableau désiré).
On se rend compte après coup que cette liste est inutile, et on gère tout avec des pointeurs et des références (qui seront bien gérées par le GC d'ocaml).
Vu sous cet angle c'est assez proche du graphe oui.
Plus précisément, pour le graphe, l'idée vient très certainement de la notion de Zipper, et avec un peu de travail, je pense qu'on peut relier le tableau persistant que tu as présenté à un zipper sur un type bien choisi.
[^] # Re: Map-Reduce
Posté par Aluminium95 . En réponse au journal Données vs Code. Évalué à 2.
En effet, je n'avais pas vu ton commentaire sur cette structure, c'est intéressant. En regardant en diagonale, j'ai l'impression que ce qui est fait est :
(modification avant, tableau, modifications après), où modification avant est une liste, et modifications après est une liste (de modifications).idu tableau, il faut effectuer les modifications sur le vrai tableau, et le faire bouger dans la liste en mettant à la place la modification nécessaire pour revenir (vers la gauche ou la droite). En gros, on se demande si la version est à gauche où à droite (en fonction dei), et si elle est à droite, onpople premier élément de droite, on l'applique au tableau du milieu, et onpushl'inverse de la transformation appliquée à gauche (jusqu'à ce que l'on soit sur le tableau désiré).Vu sous cet angle c'est assez proche du graphe oui.
Plus précisément, pour le graphe, l'idée vient très certainement de la notion de Zipper, et avec un peu de travail, je pense qu'on peut relier le tableau persistant que tu as présenté à un zipper sur un type bien choisi.