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!

  • @Dave Van den Eynde: It was suggested before on User Voice which we decided to decline. Have a look at this thread:

    visualstudio.uservoice.com/.../3701316

  • Please, make the immutable collections [Serializable].

  • Just a partially related question, do you plan to port StorageFile and StorageFolder API to WP7.5, .NET 4.0 and Silverlight as well, now when HttpClient is ported as a NuGet library?

  • @Martin Suchan: No. StorageFile/StorageFolder aren't managed APIs but native WinRT APIs. Supporting those APIs requires having OS support for WinRT as well as CLR/.NET FX support for WinRT interop (which was added in .NET 4.5). So even if we wanted to, we wouldn't be able to produce a library that enables that support on Windows Phone 8 or .NET 4.0.

  • Does System.Collections.Immutable.IImmutableList<T>.Add from Microsoft's Preview of Immutable Collections have a position requirement?

    I am implementing an immutable collection, which provides O(1) stack operations and O(log n) list operations. In other words, a collection that can do both stack and list operations. As a result, adding elements to the front is faster than adding elements to the back. Can a valid implementation of System.Collections.Immutable.IImmutableList<T>.Add()  add an element to the front of the collection instead of the back?

  • Do you use Hash array mapped tries (en.wikipedia.org/.../Hash_array_mapped_trie) for your implementation of an immutable hash table (ImmutableDictionary).

  • @soggy.potato: Yes, IImmutableList<T>.Add() has an ordering requirement. I would say the following invariant should hold:

    var list = GetImmutableList();

    var oneMore = list.Add(someValue);

    Assert.IsEqual(list.Count, oneMore.IndexOf(someValue));

  • @soggy.potato: No, the ImmutableDictionary is implemented as an AVL tree whose keys are the hash codes of the stored keys. We may change this implementation detail in the future, however.

    You may find our Channel 9 deep dive on implementation details interesting:

    blogs.msdn.com/.../inner-workings-of-immutable-collections-on-channel-9.aspx

Page 2 of 2 (23 items) 12