>
> 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
