That's a lot of interesting questions! Let me take them one by one.
3 hours ago
Why not allow user to select implementation using a factory function? The allocator most often knows how the collection will be used. For example that indexer or add must be O(1). The current AVL solution doesn't sound too good for paging and slicing. How would I create a slice of an ImmutableList? Did you look at Dlang ranges?
I haven't looked at Dlang ranges -- Andrew might have more context there. In general, we are not convinced that offering a knob for every option is the right thing. In the end, our goal is delivering a list of collection types that work for a wide variety while still being easy to use and agree upon. The Roslyn use case we brought up is quite special -- Roslyn has super tight perf constraints that most developers will not have. Once you are in this boat, chances are you want to have more control than what we can realistically offer in the BCL.
For those case we still offer the immutable interfaces as the exchange currency.
And .ToList() is commonly used on IEnumerables to materialize them from linq or other enums to make sure they are O(1) indexed. Not only to get a safe copy to foreach over. Will you add a ToImmutableList()? And will that be a noop if the IEnumerable is already an ImmList?
Our library offers an extension method for IEnumerable<T> that provides ToImmutableList().
If you call ToImmutableList() on an immutable list, you will get back the same instance, assuming it uses the default comparer. If it doesn't we change the comparer. In any case, that's an O(1) operation.
Is that what you are looking for?
An immutable list where add/indexer is O(1) with an array backing store would be nice. The allocation time would be amortized. The extra space created in array realloc could be used for non concurrent adds or adds in creator thread.
We still entertain the idea of ImmutableArray<T>. The type would be a struct wrapper around an array. Constructing would copy the array once to avoid anybody can violate the immutability guarantee. Indexer would be O(1). However, we wouldn't support persistent operations. In other words, adding or changing items would not be supported.