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