Kinds of containers

[Jonathan M Davis via Digitalmars-d]

On Wednesday, 21 October 2015 at 15:34:14 UTC, Russel Winder 
wrote:
> On Wed, 2015-10-21 at 14:06 +0000, Jonathan M Davis via 
> Digitalmars-d wrote:
>> 
> […]
>> > 1. Functional containers.
>> 
>> I fully expect that these have their place, but I honestly 
>> have no idea what they would be. When I've used functional 
>> languages, I've only ever found these attributes to be a royal 
>> pain to deal with, not a benefit. From what I've seen, 
>> containers are the sort of thing that almost always always 
>> need to be mutable to be of any real benefit. Upon occasion, 
>> constructing a container up front and then never tweaking it 
>> after that is useful, but that's pretty rare from what I've 
>> seen.
>> 
>> The only cases that I can think of where this could be really 
>> beneficial would be something like strings, and we're using 
>> arrays for those currently (though they are arguably 
>> functional containers given that they have immutable elements).
>
> I am confused as to why you would find these 
> functional/persistent data structures to be a problem in 
> functional languages. The whole point of them is they can be 
> easily shared without any locks. In effect each amendment of 
> the structure creates a fork (effectively a copy but without 
> the copy bit) of it. This goes hand in hand with the 
> functional, and especially tail recursive computational model.

My experience with immutable containers is that their performance 
is trash precisely because you can't mutate them. They end up 
being copied just to add elements or to change elements. And even 
if their internals are smart and share data as much as possible 
(though that starts moving into COW pretty quickly), the 
efficiency is still worse than having a properly mutable 
container would be. I'm sure that there are use cases where they 
would be useful, but I've sure never had one. I've found that 
functional languages can be great from an algorithmic 
perspective, but for data structures? Not so much.

And I'm by no means against having data structures like this in 
Phobos, but I think that having normal, reference containers is 
far more useful for the common case. Certainly, it's what most 
programs currently use and what most programmers expect. I'd much 
prefer that we get a solid set of reference containers working 
than spend a lot of time worrying about more exotic containers up 
front. IMHO, they can wait.

We'll see what the future may hold, and I could certainly end up 
being surprised, but I fully expect that I'll never use any 
functional containers if they're put into Phobos. They're just 
too unwieldy and inefficient.

- Jonathan M Davis