std.experimental.collection.functional.slist

[Timon Gehr via Digitalmars-d]

On 06/19/2015 03:31 PM, Andrei Alexandrescu wrote:
>> This is one reason why I dislike the term "functional" in this context,
>> it implies unnecessary baggage. popFront does not affect any other
>> references to the same data, so why is there any problem with it?
>
> Well this is a good discussion to have: should we allow rebinding (i.e.
> assignment) of functional data structures or not?
>
> For a good part of the day I've had this:
>
> @disable void opAssign(SList);
>
> i.e. once an SList is constructed, it'll always contain the same data.
> If you need a modified list, you create another one. This is how
> traditionally matters are handled in functional programming.
>
> Later in the day I relaxed matters so assignment is allowed, provided
> that other variables referring to (parts of) the same list are left
> untouched. So I defined opAssign. With that, there's a possibility to
> write r = r.tail, which is the moral equivalent of popFront.
>
> So yes, if opAssign is allowed, popFront may be allowed as well. Some
> may say it's another step on a slippery slope though.

I think this would be a pointless assertion though.

What makes persistent data structures useful is that they provide _value 
semantics_ for complex data types with _O(1)_ copies and fast updates. 
(COW has only the first two of those.)

Even in-place mutation should be allowed (e.g insert an element into a 
set, remove an element from a set), as long as value semantics is 
preserved. Scala also does this:

scala> var t = s
t: scala.collection.immutable.Set[C] = Set(C at f35b47c, C at 741d171e, 
C at 688a3052, C at 43529d91, C at 4b564e68, C at 21d8ee20, C at 165f3028, C at 64e6bd1e, 
C at 486a8d1c, C at 28f9883c)

scala> t.size
res10: Int = 10

scala> t+=new C

scala> t
res7: scala.collection.immutable.Set[C] = Set(C at f35b47c, C at 28c1b86, 
C at 741d171e, C at 688a3052, C at 43529d91, C at 4b564e68, C at 21d8ee20, C at 165f3028, 
C at 64e6bd1e, C at 486a8d1c, C at 28f9883c)

scala> t.size
res10: Int = 11

scala> t+=new C

scala> t.size
res12: Int = 12

Similarly, it is no problem to allow reassigning the front of a 
persistent list, as long as in the background, a new node is allocated 
for the new head, that points to the same tail.

Reference counting is actually quite neat here, because if the reference 
count is 1, updates can be performed in-place transparently as an 
optimization.