Talk:Persistent array

"Backers trick" should probably be "Baker's trick", since it is most likely referring to "Henry G. Baker. Shallow binding makes functional arrays fast. SIGPLAN Not., 26(8):145–147, 1991.". Per Mildner (talk) 19:57, 22 December 2020 (UTC)

Tree of Modifications

I removed the second implementation from the main article (attached below) since the time complexity of lookups appears to be $\Theta (n)$ in the worst case, which is much worse than the other implementations. Perhaps this implementation can be re-added if accompanied by an explanation of why this implementation is preferred over the others.

---

Using an array, and a tree of modifications

A fully persistent array may be implemented using an array and the so-called Baker's trick. This implementation is used in the OCaml module parray.ml by Jean-Christophe Filliâtre.

In order to define this implementation, a few other definitions must be given. An initial array is an array which is not generated by an update on another array. A child of an array ar is an array of the form ar.update(i,v), and ar is the parent of ar.update(i,v). A descendant of an array ar is either ar or the descendant of a child of ar. The initial array of an array ar is either ar if ar is initial, or it is the initial array of the parent of ar. That is, the initial array of ar is the unique array init such that $\mathrm {ar} =init.update(i_{0},v_{0}).\dots .update(i_{m},v_{m})$, with ar initial and $i_{0},\dots ,i_{m}$ an arbitrary sequence of indexes and $v_{0},\dots ,v_{m}$ an arbitrary sequence of value. A family of array is thus a set of arrays containing an initial array and all of its descendants. Finally, the tree of a family of arrays is the tree whose nodes are the arrays, and with an edge e from ar to each of its children ar.update(i,v).

A persistent array using the Baker's trick consists into a pair with an actual array called array and the tree of arrays. This tree admits an arbitrary root - not necessarily the initial array. The root may be moved to an arbitrary node of the tree. Changing the root from root to an arbitrary node ar takes time proportional in the depth of ar. That is, in the distance between root and ar. Similarly, looking up a value takes time proportional to the distance between the array and the root of its family. Thus, if the same array ar may be lookup multiple time, it is more efficient to move the root to ar before doing the lookup. Finally updating an array only takes constant time.

Technically, given two adjacent arrays ar1 and ar2, with ar1 closer to the root than ar2, the edge from ar1 to ar2 is labelled by (i,ar2[i]), where i the only position whose value differ between ar1 and ar2.

Accessing an element i of an array ar is done as follows. If ar is the root, then ar[i] equals root[i]. Otherwise, let e the edge leaving ar toward the root. If the label of e is (i,v) then ar[i] equals v. Otherwise, let ar2 be the other node of the edge e. Then ar[i] equals ar2[i]. The computation of ar2[i] being done recursively using the same definition.

The creation of ar.update(i,v) consists in adding a new node ar2 to the tree, and an edge e from ar to ar2 labelled by (i,v).

Finally, moving the root to a node ar is done as follows. If ar is already the root, there is nothing to do. Otherwise, let e the edge leaving ar toward the current root, (i,v) its label and ar2 the other end of e. Moving the root to ar is done by first moving the root to ar2, changing the label of e to (i, ar2[i]), and changing array[i] to v. B52481 (talk) 05:12, 19 June 2023 (UTC)