> 
> I don't think we want to have a Map.add(k,v) instance method (or default 
> method) for immutable maps or for constructing them.
> 
> For a fast, compact, immutable map implementation, the only way to implement 
> Map.add() would be to copy the entire contents plus the additional pair into 
> a new map. 
> 
> this would result in O(N^2) performance and space allocation, though most of 
> the allocated space is garbage.

Only with a very naive implementation of immutable maps! With a HashTrie, or 
RedBlack tree, of Finger tree, adding a new entry can be O(log(N)) in both time 
and space.
> 
> Of course, one could avoid the copying overhead by making the immutable maps 
> persistent (i.e., sharing their unmodified portions) but that is an entirely 
> different discussion.

Well, I think immutable maps are a different discussion anyway, but surely any 
worthwhile implementation of immutable maps should make it easy and fast to 
create a new immutable map by adding an entry?
> 
> I kind of think you're after the ability to chain the method calls.

Yes.

> This is certainly convenient and has no arbitrary restrictions on the number 
> of elements. To do something like this we'd put the chainable methods on a 
> builder instead:
> 
>    Map.builder()
>       .add(k0, v0)
>       .add(k1, v1)
>         ...
>       .add(kN, vN)
>       .build();

Seems an unnecessary complication to me... 

For a mutable map it's just: add(k,v) {put(k,v); return this}.

For an immutable map using something like a HashTrie, creating a small map 
using say 5 add() operations is not going to take significantly longer than the 
builder approach; you can always provide the builder as well for those who want 
ultimate performance.
> 
Michael Kay
Saxonica

Reply via email to