Update to Immutable Collections

Update to Immutable Collections

Rate This
  • Comments 23

Thanks a lot for your great feedback!

Two months ago, we shipped a NuGet package with support for immutable collections. We’ve also talked about it on Channel 9. Since then we received feedback through various channels and we’re happy to announce we shipped an update on NuGet that addresses your feedback.

Feedback Channels

First of all: how are we tracking your feedback? We track social media, such as Twitter, Reddit and our official Facebook page. We also track StackOverflow, Connect, the comments on this blog, and last but not least emails send through the NuGet’s Contact Owners mechanism. Yes, we really want your feedback!

The most direct way to contact us is via NuGet or comments on this blog.

Your Feedback

Package Installation Issues

Some customers reported issues with installing the NuGet package. In all cases, the root cause was an outdated version of the NuGet package manager. Immutable collections use portable class libraries and they are only supported by NuGet 2.1 or higher.

In order to update the immutable collections package, please install the latest version of NuGet. You can check whether you have the latest version by going to Tools | Extensions and Updates. When the Extensions and Updates dialog opens, select Updates | Visual Studio Gallery and look for an entry titled NuGet Package Manager.

Unfortunately, there is currently no way for a package to specify a minimum required version of NuGet. To address this in the future, we have worked with the NuGet team and NuGet 2.3 will add this ability. For now, you will need to know to install an updated version of NuGet.

Construction

We explicitly decided not to provide constructors for immutable collections. The reason for this is that immutable collections typically start with an empty instance. Since all empty instances would be the same, this would result in a lot of wasted objects. Instead, we decided to use a singleton as the empty instance.

Unfortunately this decision resulted in quite verbose code:

    var list = ImmutableList<int>.Empty.Add(1, 2, 3);

Furthermore, this approach doesn’t support type inference as the generic arguments must be specified. Besides having to type more this also means that anonymous types aren’t supported (remember: only Jon Skeet knows their names).

We’ve fixed this by using a solution similar to what we use for Tuple. We’ve created non-generic types that serve as a factory for creating immutable collections. Also, we’ve removed the Empty property and replaced it by a factory method (it still returns a singleton but this makes the design more consistent).

This allows you to write code like this:

    var anEmptyList = ImmutableList.Create<int>();
    var oneTwoThree = ImmutableList.Create<int>(1, 2, 3);

which can be shortened as it allows for type inference:

    var oneTwoThree = ImmutableList.Create(1, 2, 3);

which in turn enables anonymous types:

    var andrew = new { FirstName = “Andrew”, LastName = “Arnott” };
    var matt = new { FirstName = “Matt”, LastName = “Cohn” };
    var immo = new { FirstName = “Immo”, LastName = “Landwerth” };
    var list = ImmutableList.Create(andrew, matt, immo);

Interoperating with existing collections

As you are probably aware, the existing mutable collection interfaces in the BCL support the notion of read-only-ness. In our original design we made the decision that immutable collections shouldn’t implement the standard mutable interfaces. The idea was that you had to explicitly call a method on them to convert them to the standard collection interfaces, such as ImmutableList<T>.ToReadOnlyCollection().

However, we received the feedback that people had a hard time figuring out how to pass an immutable list to en existing method that took, for example, IList<T>.

Also, we came to the conclusion that this design was inconsistent with our existing collection types. For example, List<T> implements IReadOnlyList<T> which means you can view a mutable list as if it were a collection that doesn’t support modifications. In the same way it makes sense to view an immutable list as list that doesn’t support modifications and thus implements IList<T> but returns true for IsReadOnly.

In the end, we decided to remove the method to explicitly convert the collections to read-only collections and simply implemented the existing collection interfaces in a read-only fashion.

The following table summarizes the relationship between the immutable collections and the existing interfaces:

 

Equality semantics

Today, all collections in the BCL have reference equality semantics and don’t overload the equals operator (== in C#, = in Visual Basic).

In the preview release we chose to override the Object.Equals method to provide value equality, but did not overload the equals operator in line with the other collections. After reviewing this design more carefully we concluded that we don’t want to override the Equals method.

Value equality on collections can be fairly expensive to compute and comparing for equality on nested collections, such as ImmutableDictionary<string, ImmutableList<string>> is more difficult to define. Finally, providing this functionality leads to more issues when different comparers are involved, as customers have pointed out.

In many cases, we believe that reference equality is sufficient. In other cases, the app should provide its own equality policy. As a result, we have removed the overrides of the Equals methods.

Naming

Several people pointed out that the design of our immutable collections is known as persistent data structures. Thus, it was suggested to rename our data types accordingly, for example, PersistentList<T>. We’ve given it a lot of thought and decided to keep the name “immutable”.

We want to keep the concept count low. The BCL already provides mutable collections, read-only collections, and now immutable collections. Traditionally, we don’t introduce new concepts unless deemed necessary.

From a high-level perspective, the important characteristic you get from immutable collections is that they guarantee that their contents will never ever change. The fact that these collections also enable you to efficiently create new versions of an existing instance without naively copying all their contents is of secondary importance. We feel the “Immutable” name focuses on the most important aspect.

In addition, we’ll consider adding an ImmutableArray<T>. This would be a struct that simply wraps an underlying array without ever exposing it. Naming wise, it makes sense to name it ImmutableArray<T>. It wouldn’t have persistent character though, as we wouldn’t offer any methods to create new versions with different values. If you wanted this behavior, you should use ImmutableList<T> instead. The goal of ImmutableArray<T> is simply to provide a low overhead wrapper around an array to enforce it can never change.

To me this indicates that “immutable” is a more useful term for the BCL as it is precise and yet general purpose enough to not require adding more terminology down the road when the design evolves.

The Small Things Count

We’ve also improved several smaller things, for example, we’ve added a ImmutableList<T>.RemoveRange(IEnumerable<T>) method. The existing remove range that took an index and a count was not super useful in mainstream scenarios.

Hold on – aren’t those breaking changes?

Yes! The NuGet package is marked as a “pre-release”. Pre-release packages are non-stable previews of a product. That is, we don’t guarantee the final shape of the API and/or functionality and want to be able to change them based on customer feedback. In the end, the sole purpose of pre-release packages is gathering feedback.

That is a very different experience from a beta of the .NET Framework. Typically, a beta is the first public release of the framework but it is already very close to RTM. In fact, for .NET 4.5 we shipped the beta with a go-live license that supports use in production. On one hand, this is great for early adopters, but on the other hand it means we couldn’t react to major design change requests because the design was already set.

Pre-releases on NuGet allow us to give you the bits really early and react to your feedback in a meaningful way. For example, if changing the API shape is the right thing, we’ll do it.

However, once we mark packages as stable (AKA “RTM”) we hold the same bar for breaking changes as in-box .NET Framework components.

Summary

Please try out the new drop of immutable collections. If you’re already using them, you can simply upgrade your existing packages via the NuGet package manager. Otherwise, just search for Microsoft.Bcl.Immutable and make sure you include pre-releases.

Looking forward to receiving more feedback!

  • Re: Equality Semantics: Isn't the answer here to support (the F#-encouraged) IStructuralEquatable and IStructuralComparable?

  • Do the collections implement IStructuralEquatable? It sounds like it would be a reasonable compromise for those who want to do value equality, and it just generally make sense for collections to implement this interface, because their semantics are that of containers holding values.

    I wish it was retrofitted onto existing collections classes, as well, but that may be a more far fetched proposition.

  • @Maxwell J. Battcher: We considered this but we weren't happy with the design. For example, comparing two lists of value types would result in boxing all elements.

    @int19h: Agree, that's why we entertained the idea. In general, we haven't seen a strong demand for value-based equality semantics on collections. Also, structural equality is a concept that is hard to generalize. For example, we've talked to the C#/VB languages team since they have a similar problem in Project Roslyn when comparing syntax trees. They needed a bunch of different options to express the kind of equality they need. Examples are: ignoring whitespaces or ignoring casing of identifiers. You can express all of this in a comparer but sometimes it's just easier to write a custom traverser that computes the answer for a specific problem domain.

    We can always add this capability once we have a design we're happy with. But we don't want to ship a design we aren't comfortable with because it's hard to morph once we mark the package as stable. That's why we concluded not to add it now.

  • Directly implementing IList<T> seems like a mistake. In my experience, code that uses IList<T> seldom checks IsReadOnly (because historically, it's hardly ever mattered). The best way to know that a piece of code is safe to use with immutable lists is to change it to use IReadOnlyList<T>. Having the immutable collections implement IList<T> makes that much harder; it would require diligence to make sure I always typed my list as IReadOnlyList<T> as soon as I created it, and never used the "var" keyword for a fresly-created list. In other words, I'd have to practice constant vigilance to get even the slightest bit of value out of the feature, which doesn't seem like a great trade-off.

    It seems to me that "I want to review any code that tries to use this as an IList<T> without saying it really means it" would be a much more common use case, especially when initially transitioning existing code to use immutable collections, than "I want to pass this immutable list to code that expects a read-write list and I promise I've checked to make sure it won't ever blow up". Honestly, I can't imagine when the latter would even come up, unless you're dealing with a third-party library that isn't IReadOnlyList-savvy yet (or that needs to maintain compatibility with older Framework versions), and those would often use IEnumerable anyway.

    That said, the old method, "ToReadOnlyCollection", seems like a really poor name. Nothing about that name suggests that it actually returns an IList<T>; it sounds like it just returns another IReadOnlyCollection<T>, which is pointless since that's what I already have and I already know it isn't what I need. "ToIList" or "AsIList" (probably the latter, since you're creating an adapter like with AsEnumerable, not a new copy like with ToList) seems like it would be much more discoverable; and if it was discoverable, you wouldn't have to implement the poorly-matched IList<T> on the immutable collections in the first place.

  • @Joe White: Thanks for the well written feedback.

    We certainly didn't make this change lightly. In fac the original design did exactly what you proposed. The reason we named the method ToReadOnlyCollection() was because it actually gave you an instance of the class ReadOnlyCollection<T> which implements IReadOnlyList<T> as well as IList<T> (in a read only fashion of course).

    For better or worse, the existing design of the BCL decided to encode read-only-ness via a capability based design. It's consistent how, for example, streams are exposed as well.

    As of today, the IReadOnly-interfaces aren't widely used, given that they were introduced in .NET 4.5. So the majority of the code will be written using the existing mutable interfaces.

    We want to ensure that (1) we can operate well with those and (2) the way you interoperate is discoverable. In addition to the method approached we shipped before we also considered an explicit casting operator but outside of primitives explicit casting operators aren't really discoverable.

    That being said, we still want to hear what others think about this design aspect.

  • I agree strongly with Joe White

  • Thanks! Extension methods such as To<Smth> and GetValueOrDefault is very good (waiting for this in a regular collections and dictionaries). Please, provide also in BCL (and add to an immutable) interface IReadOnlySet<>.

  • Thanks for the Grate Work.

    I updated to 1.0.8-beta at once.

    And I found an error "CS0121" on this simple code:

       var dict = ImmutableDictionary.Create<string, string>();

       var val  = dict.GetValueOrDefault("foo");

    Because `dict` can be casted implicit to both IDictionary and IReadOnlyDictionary.

    I think that this behavior is not user-friendly.

    One of solutions is to add this method:

       public static TValue GetValueOrDefault<TKey, TValue>(this IImmutableDictionary<TKey, TValue> dictionary, TKey key);

  • I would say than letting the mutable IList implement an immutable IReadOnlyList is a completely different matter, than letting a immutable list implement the mutable IList. It is contradictory, albeit inline with the failed BCL standard interfaces which should have been split into read (immutable) and write (mutable) interfaces from the start. As any good programming knows splitting command and queries is a good thing.

    So I would prefer immutable collection to not pose as mutable and only implement IReadOnlyList, IReadOnlyCollection, IEnumerable etc. If people complain they can't use an immutable list as an IList then they have a failed contract in my opinion and the receiver should say I would like an IReadOnlyList instead.

    Also have you actually reviewed how much code actually depends on the IsReadOnly property out there. Very little I would assume.

  • I understand this package is pre-release and subject to change, but it would be great if you could offer a license that allows us ship it.

  • ImmutableArray would be very useful in cases where you have lots of them (and need to keep them around for a long time (like in a cache)) and want to save memory. It doesn't get more efficient than a struct-wrapped array.

  • Please release a version for .NET 4.0. We are stuck to it because we still need to support windows xp. We really need those collections.

    So is there a plan to support .NET 4.0?

  • I have just one piece of easy feedback so far: in the blog posts for this, I can never find a link to the NuGet package page ( nuget.org/.../Microsoft.Bcl.Immutable ), and always spend a few minutes trying to re-find it. If you'd toss a link to it at the top of the blog post, that'd be fantastic :) I don't use NuGet much (yet!) so I never remember where everything is.

  • @Viacheslav Ivanov: Thanks for the suggestion. Unfortunately, we will not be able to address this in this release.

    @ToruNagashima: You're spot on! Thanks for reporting this. I've filed a bug and we will address it in the next drop of immutable collections. As a workaround, you can type the local as IImmutableDictionary:

    IImmutableDictionary<string,string> dict = ImmutableDictionary.Create<string, string>();

    var val = dict.GetValueOrDefault("foo");

    @Harry: We hear you. For what it's worth, the existing mutable interfaces are what they are. I've checked the API usage data we have from our compat lab and it turns out that of all the apps using IList only half of them call methods that mutate the list. That's probably not representative for the entire .NET ecosystem but it's the best data point we have so far. To me this, this indicates that that implementing the mutable interfaces in a read-only fashion enables an interesting set of scenarios. However, we do realize that we sacrifice expressiveness by doing so.

    @Jamie da Silva: Thanks for the feedback. We don't have plans on changing the license but I'll double check to see whether we can lift that restriction. However, please note that we will continue to do breaking changes if we believe that's necessary. After all, this is a pre-release.

    @xor88: Glad you like the idea!

    @Heiko: I'm sorry to hear you are stuck on .NET 4.0 due to XP. There are no plans on releasing a version that is compatible with .NET 4.0. We've explicitly chosen to target the new, System.Runtime based factoring and are thus not compatible with .NET 4.0 anymore. Also, we use the new read-only interfaces we introduced in .NET 4.5. We don't want to maintain two versions.

    @Rick Brewster: It's actually the 3rd link in the second paragraph :-)

  • Does it make sense to suggest to make them [Serializable]? I'd like to 'snapshot' a whole bunch of this with a BinaryFormatter, but they're not marked with the SerializableAttribute, and I'm also not sure if it's a good idea to serialize the internal structure.

Page 1 of 2 (23 items) 12