Kinds of containers

[Ulrich Küttler via Digitalmars-d]

On Wednesday, 21 October 2015 at 18:55:10 UTC, Andrei 
Alexandrescu wrote:
> On 10/21/2015 01:42 PM, Ulrich Kuettler wrote:
>> On Wednesday, 21 October 2015 at 11:05:12 UTC, Andrei 
>> Alexandrescu wrote:
>>> I'm finally getting the cycles to get to thinking about 
>>> Design by
>>> Introspection containers. First off, there are several general
>>> categories of containers. I think D should support all 
>>> properly. One
>>> question is which we go for in the standard library.
>>>
>>> 1. Functional containers.
>>
>> Very much in favor of functional (or persistent) containers. 
>> Immutable.
>> Value semantics.
>>
>> This might take some getting used to, but if properly designed 
>> these
>> containers would be killer for D. A dream come true.
>
> I agree they're cool.
>
>>> These are immutable; once created, neither their topology nor 
>>> their
>>> elements may be observably changed. Manipulating a container 
>>> entails
>>> creating an entire new container, often based on an existing 
>>> container
>>> (e.g. append takes a container and an element and creates a 
>>> whole new
>>> container).
>>>
>>> Internally, functional containers take advantage of common
>>> substructure and immutability to share actual data. The 
>>> classic
>>> resource for defining and implementing functional containers 
>>> is
>>> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
>>>
>>>
>>
>> An insanely beautiful example is clojure's PersistantVector. 
>> AFAIK it
>> made its way into Scala, too.
>
> Far as I understand from 
> http://hypirion.com/musings/understanding-persistent-vector-pt-1, it's that tree thing with carefully chosen slot sizes for cache friendliness?

Yes. It is about cache friendliness, memory efficiency and speed. 
Since each node consists of 32 pointers, there are just three 
inner levels to store 1M values.

The bit operations to navigate to the leaf node are a thing of 
beauty:

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentVector.java#L147-L163

It is a remarkable design on the JVM. Of course, it serves a very 
particular purpose. D's design space is very different. Obviously.