Kinds of containers

[Timon Gehr via Digitalmars-d]

On 10/24/2015 09:22 PM, Andrei Alexandrescu wrote:
> On 10/24/15 3:19 PM, Timon Gehr wrote:
>> Even if this was possible, it would not be a very good idea. Persistent
>> data structures have use cases that would be hindered by required
>> transitive immutability.
>
> This part I don't quite get.

The slots are not mutable, but they are not /transitively/ immutable 
either. Note that this does not require any special effort, nor does it 
/prevent/ stored elements from being (transitively) immutable. Scala 
does it this way. (Haskell as well, basically.)

> Are there any languages that offer
> containers with immutable topology but mutable slots, and call them
> persistent data structures? -- Andrei

Not that I know of, unless you count the hidden updates Haskell 
implementations may perform in order to provide lazy semantics (which 
'immutable' in D prevents, this alone is a sufficient reason not to 
force it on users).
However, that would be useful as well (as a potential performance 
optimization if the identity of the stored elements does not matter).


This paper of Sarnak and Tarjan discusses a version of what they call 
persistent rb-trees that only allows updates on the last version (which 
is often sufficient). (The point of the restriction is to lower space 
usage.) It changes color information on existing nodes and it keeps 
mutable lists in the nodes (i.e. making the nodes immutable would not work.)

http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf

One might now say that those implementation details don't matter, and 
that the slots should still be transitively immutable. Well, one may 
want to use such data structures _within_ other persistent data structures.

(Just consider e.g. the case where, given a 3D point cloud of size n, 
and a number of axis-aligned boxes, you want a way to count the number 
of points in each box, given that the boxes arrive in an online fashion, 
while the points are known from the start. (Here, we want O(n log² n) 
preprocessing time, O(n log n) space and O(log² n) query time). One way 
to achieve that involves storing instances of an augmented version of 
their persistent rb-tree (they should support the range queries I have 
mentioned in my list of useful data structures) within a persistent 
augmented tree with predetermined O(log n)-depth topology (this 
container I had missed to mention).)

You can't do that if slots are transitively immutable.