Clojure vs. D in creating immutable lists that are almost the same.

[Chris Wright via Digitalmars-d]

On Sat, 27 Feb 2016 22:31:28 +0000, Brother Bill wrote:

> Clojure supports immutable lists that allow adding and removing
> elements, and yet still have excellent performance.
> 
> For D language, what are the recommended techniques to use functional
> programming, without massive copying of data and garbage collection, so
> that it remains immutable.
> 
> That is, how to create one-off changes to an immutable data structure,
> while keeping the original immutable, as well as the one-off change, and
> maintain good performance.
> 
> Thank you

It's pretty straightforward for arrays:

  immutable(T[]) array = ...;
  auto inserted = chain(array[0..5], [new T], array[5..$]);
  auto dropped = chain(array[0..5], array[6..$]);
  auto appended = chain(array, [new T, new T]);

After K mutations, you have a tree of chain!(...).Result structs; this 
tree is of height K and contains O(2**K) Result structs (if you're 
removing or inserting items in the middle of the array).

That's not too bad if you're rarely mutating the array. Maybe choose a 
period; after that many mutations, you copy the data into a new 
collection.

But there's a bigger problem. In the above example, there are four 
variables, and each has a different type. That's fine if you're declaring 
new variables. If you are dealing with aggregate fields, it's trouble.