Covariant Immutable Collections

[gregsn]

related: https://github.com/dotnet/corefx/issues/5164

having dedicated covariant interfaces for the different immutable collection types (and implementing them on the immutable collection classes) would allow to add extension methods that allow to add elements to an immutable covariant collection.

The extension methods could check if the incoming IImmutableCovariantList<out T> is already a ImmutableList<T> - which should be true most of the time - and in this case use all the specific methods, like insert, add, remove of that class. Otherwise, we'd need to create a new ImmutableList<T> and then operate on that new instance.

---

Why all the trouble?

• Because explaining that an immutable collection of bananas cannot be perceived as an immutable collection of fruits is a hard task and in fact, could from a user perspective be seen as a design flaw - not as bad as the standard mutable array being covariant, but still not that beautiful.
• With the proposed design the extension methods for modification would only show up on that type, not on IReadonlyList<T>. related: Make IImmutableList covariant like IReadOnlyList, IEnumerable etc. #16011. You'd have an immutable type, that when adding or removing an element would give you a new snapshot of exactly the same type, where this type is covariant.

---

it looks like the idea works and doesn't seem to break anything

Basically it is just

• an empty interface IImmutableCovariantList<T> implemented by Immutablelist<T>
• extension methods for that interface (for now in a new namespace System.Collections.Immutable.Covariance)

Down there in the tests you also can see that how c# treats an ImmutableList<T> as an IImmutableCovariantList<T> to make adding an apple to a list of bananas work out. As a user you currently need to add the namespace System.Collections.Immutable.Covariance that I introduced to avoid blowing up the list of extension methods that you see in the intellisense list when working with a regular ImmutableList<T>.

            var firstBanana = new Banana();
            var bananas = ImmutableList<Banana>.Empty;

            bananas = bananas.Add(firstBanana);

            // add an apple to the banana(s) and you get fruits
            var fruits = bananas.Add<IFruit>(new Apple()); 
            Assert.Equal(fruits.Count, 2);

            // add a banana and you still have bananas
            bananas = bananas.Add(new Banana());
            Assert.Equal(bananas.Count, 2);

            // bananas can be seen as fruits
            fruits = bananas;

            var anotherApple = new Apple();

            // again messing with bananas that get confronted with apples all of a sudden
            IEnumerable<IFruit> applefollowedByBanana = bananas.SetItem<IFruit>(0, anotherApple);
            IEnumerable<IFruit> applefollowedByBanana2 = bananas.Replace(firstBanana, anotherApple, EqualityComparer<IFruit>.Default);

            Assert.Equal(applefollowedByBanana, applefollowedByBanana2);

here is the issue about covariance for classes:
dotnet/roslyn#171
it will not happen.

even though immutable collections would highly benefit: Eric Lippert implementing a class Stack<out T>: https://stackoverflow.com/questions/2733346/why-isnt-there-generic-variance-for-classes-in-c-sharp-4-0/2734070#2734070 ...

anyways, because of this unavailable CLR feature, the only way of introducing covariant types is via interfaces. so yes, the proposed solution is a hack. it hacks around the limitations of the underlying system by introducing an interface for each immutable collection class. An ImmutableDictionary<TKey, TValue> e.g. would implement IImmutableCovariantDictionary<TKey, out TValue>. The interface is there to ship the covariance feature, which is not shippable without that "hack". So class and covariant interface would always come in pairs.

A user just needs to include System.Collections.Immutable.Covariance in her/his using statements and she/he is now able to work with IImmutableCovariantDictionary<TKey, out TValue> whenever the need arises. Therefore she/he can avoid more complicated code, which would do the same.

---

In the implementation of the extension methods regarding IImmutableCovariantArray<out T> would internally use the CastUp idea. The API surface would not care about when optimizations like the CastUp idea are possible or not. It would work the same way for all the immutable collections, which would be beautiful.

---

If in 10 years classes in .Net suddenly can have covariant type parameters, the interfaces would get obsolete and many extension methods would magically run faster as list as ImmutableList<T> would typically be true (even if the incoming list is actually of type ImmutableList<TDerived>).

        public static IImmutableCovariantList<T> Insert<T>(this IImmutableCovariantList<T> list, int index, T element)
            => (list as ImmutableList<T> ?? list.ToImmutableList()).Insert(index, element);

---

if you look at the implementation it gets obvious that we could also return the classes on all extension methods.
e.g.

    bananas.SetItem<IFruit>(0, anotherApple);

would act on ImmutableList<Banana> (seen as IImmutableCovariantList<IFruit>) and return ImmutableList<IFruit>. The user would not even need to deal with the interface.

[gregsn]

@terrajobst and @AArnott
back in the days when you were designing the immutable collections: were you thinking about covariance? I am pretty sure you were. Would you mind sharing some of the ideas of why you didn't go for it?

The point that I am trying to make here is: Immutable collections should be covariant, even if the type system of .Net makes it hard to achieve it. At least it should be possible to unlock the feature as it is a property of immutable collections from a theoretical perspective.

From a user perspective, I would like to see a unified and easy way to use this feature. Currently, an ImmutableArray allows to Castup, but for other immutable collections, I need to perform other tricks (like for a dictionary).

In this proposal, I try to come up with a unified API design that makes it very easy to make use of the covariantly flavored collections. I am aware that expressions like list.ToImmutableList()) is kind of problematic as it is expensive and super naive. On the other hand: the user would currently need to do the same or in case of a dictionary even more complicated tricks. So with the sketch, we could shield that away from the user. Also, if the CLR ever could do covariant type parameters on classes (and they would be used in your classes) the user would get a performance improvement for free while not changing any code.

[AArnott]

I don't need this often, but I do like the idea. It was a while ago, but as I recall the reason we didn't do it this way is we were considering it being the only way. There was a very well written blog post by Eric Lippert describing how immutable collections could be created and rely on extension methods to achieve automatic covariance. That idea was dismissed pretty quickly because of its reliance on extension methods for the primary use cases. For instance, if I created a System.Collections.Immutable.ImmutableList<Banana>, there wouldn't be an Add method on it because I hadn't (yet) added the using System.Collections.Immutable; statement at the top of the file yet. This was seen as too much of a hurdle for a collection type that should define basic operations on its own.

The hybrid approach you're proposing where you can opt into covariance but the basic functions don't require it isn't one I recall considering before. @terrajobst may remember more.

[gregsn]

Thanks @AArnott !
Another alternative more explicit idea regarding unifying the API design: couldn't we just add CastUp to the other immutable collections as well?

        [Pure]
        public static ImmutableList<T> CastUp<TDerived>(ImmutableList<TDerived> items)
            where TDerived : class, T
        {
            return ((IEnumerable<T>)items).ToImmutableList();
        }

Again quite more expensive than the CastUp of IImmutableCovariantArray<out T>, and you could argue that the name CastUp is misleading. You would not expect that method to be expensive. But unifying the API would allow a certain storytelling: immutable collections are not covariant but all come with a method CastUp.

bananas.CastUp<IFruit>().SetItem(0, anotherApple);

That way we wouldn't need to introduce a new interface, namespace and wouldn't need to add all the extension methods.

[alrz]

I cannot find the same suggestion for task, e.g. ITask<out T> tasklike type, is there a tracking issue for that already?

[stijnherreman]

That idea was dismissed pretty quickly because of its reliance on extension methods for the primary use cases. For instance, if I created a System.Collections.Immutable.ImmutableList<Banana>, there wouldn't be an Add method on it because I hadn't (yet) added the using System.Collections.Immutable; statement at the top of the file yet. This was seen as too much of a hurdle for a collection type that should define basic operations on its own.

I've my doubts about it being too much of a hurdle, considering the target audience is people who consciously choose to use immutable collections. I'd wager a large majority of .NET developers will rarely, if ever, come in contact with the concept of immutable collections.

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of the experimental issue cleanup initiative we are currently trialing in a limited number of areas. Please share any feedback you might have in the linked issue.

This issue will now be closed since it had been marked no recent activity but received no further activity in the past 14 days. It is still possible to reopen or comment on the issue, but please note that the issue will be locked if it remains inactive for another 30 days.