Re: Structures non mutables performantes

Effectivement, tu as bien compris comment fonctionnaient ces tableaux persistants. En interne il y a des effets de bords sur un véritables tableaux à la mode impératif. Cela vient en partie de la conception de la persistance des deux auteurs de l'ouvrage sus-mentionné :

Cela ne signifie pas pour autant qu'une structure de données persistantes soit nécessairement codée sans aucun effet de bord. La bonne définition de persistant est :

persistant = observationnellement immuable

et non purement applicatif (au sens de l'absence d'effet de bord). On a seulement l'implication dans un sens :

purement applicatif => persistant

La réciproque est fausse, à savoir qu'il existe des structures de données persistantes faisant usage d'effets de bord. Cet ouvrage contient plusieurs exemples de telles structures.

Dans cet exemple, on utilise les effets de bords pour avoir des opérations de lecture et d'écriture en temps constant tant qu'on utilise pas la persistance (sinon, il faut prendre en compte le temps de se rebaser sur le bon tableau via reroot en appliquant les patchs).

Pour ce qui est du fonctionnement des shared_ptr, en lisant ton explication, il me semble bien que c'est ce que j'en avais déjà compris. La discussion avec freem sur le sujet commence à ce commentaire et il pensait qu'en programmation fonctionnelle on privilégiait la copie alors que l'on favorise le partage de la mémoire (là où je voyais un rapport avec les shared_ptr, qui apportent aussi une gestion automatique de la mémoire à la manière des GC). Je prenais cet exemple de représentation en mémoire de deux listes qui partagent leur queue :

let l = [1; 2; 3];;
(* la représentation mémoire de celle-ci est une chaîne :
| 1 | -|-->| 2 | -|-->| 3 | -|-->| |
*)
let l1 = 4 :: l and l2 = 5 :: l;;
(* ce qui en mémoire donne :
| 4 | \|
 \
 -->| 1 | -|-->| 2 | -|-->| 3 | -|-->| |
 /
| 5 | /|
*)

De ce que je comprends de ta gestion mémoire pour tes graphes, c'est que tu évites les effets de bords et tu gères tes pointeurs comme le feraient les compilateurs Haskell et OCaml pour les types inductifs. Ai-je tort ? La liste l qui est partagée entre l1 et l2 n'est-elle pas proche d'un shared_ptr ?

Dans le cas de mes tableaux persistants :

type 'a t = 'a data ref
and 'a data = |Arr of 'a array 
 |Diff of int * 'a * 'a t

ce n'est pas avec le type paramétrique 'a t des tableaux que je crois voir une analogie avec les shared_ptr, mais avec le type 'a data. Pour ce qui du type 'a t, c'est une simple référence comme on en trouve en C++. Suis-je à côté de la plaque ?

Pour la note historique, d'après les auteurs du livre, cette structure de tableaux persistants serait due à Henry Baker qui l'utilisait pour représenter efficacement les environnements dans des clôtures LISP. (Henry G. Baker. Shallow binding makes functionnal array fast).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.