std.experimental.collection.functional.slist

[via Digitalmars-d]

On Friday, 19 June 2015 at 13:31:36 UTC, Andrei Alexandrescu 
wrote:
> On 6/19/15 2:36 AM, Timon Gehr wrote:
>> On 06/19/2015 04:21 AM, Andrei Alexandrescu wrote:
>>> ...
>>> functional.SList should have empty but not popFront. The 
>>> latter is
>>> mutating.
>>> ...
>>> The first won, partly because it's easier to implement 
>>> efficiently. So
>>> now we have this one mutating operation that we need to mind. 
>>> Because of
>>> it, we'll need functional containers to be distinct from 
>>> their ranges.
>>> ...
>>
>> 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.

If opAssign is allowed, a major point of functional data 
structures is lost. Client code is so much better if rebinding is 
off the table. On the other hand, there is const and immutable... 
I would still prefer properly functional data structures.

In addition, is there a constructor for structural sharing, the 
complement to tail? Along those line:

this(T e, SList rhs)
{
     if (rhs.root) {
          allocator = rhs.allocator;
          root = allocator.make!Node(e, 1, rhs.root);
          ++rhs.root.count;
     }
}

This is very exciting! Properly typed efficient functional data 
structures! (In my dream, there are clojure's vector, set, map in 
D.) This is just too good.