Tag: IEnumerable

C#6: Collection Initializers

Patterns and Collection Initializers

Some of the cool parts of C# are pattern-based, rather than type-based as one might expect. For example, `foreach` does not need the enumerated type to implement `IEnumerable` in order to work, it just requires that it has a `GetEnumerator()` method. Another place where pattern-based compilation occurs that also happens to illustrate how useful this pattern-based approach can be is in collection initializers like this:

var list = new List<int> { 1, 2, 3, 4, 5, 6 };

When this gets compiled, for each value in the initializer the C# compiler1 looks for an `Add()` method on the collection type with an appropriate number of arguments of the appropriate types, which it then calls for that value. The benefit to using a pattern-based approach is that the compiler does not need to know about every possible compatible type up front or what `Add()` methods it might support. It only enforces that the type derives from `IEnumerable` and that it has an `Add()` method that matches the initializer values. This allows us to create a collection types that can support a variety of different ways to add values without needing the compiler to know our type will ever exist. For example, we could create a collection of names with `Add()` methods that take one or two strings and then initialize elements with either just the surname or first name and surname2.

var names = new NamesCollection
{
   "Jones",
   { "David", "Smith" },
   { "Daniel", "Smith" },
   "Smith"
};

Collection initializers in C#6

In C#6, a new collection initializer syntax has been added and the way the compiler interprets the existing syntax has been modified. Before we look at the newly added syntax, let us look at how the compilation of the existing syntax has been changed. To do so, consider a collection of `DateTimeOffset` values where we want to simplify adding dates and times from parsable string values. To support this we could implement an entire new type with the appropriate calls or we could derive from an existing collection type `List<DateTimeOffset>` and then implement a new `Add()` method to support `string`.

public class DateTimeOffsetList : List<DateTimeOffset>
{
    public void Add(string value)
    {
        base.Add(DateTimeOffset.Parse(value));
    }
}

Of course, not all collections are open for extension and creating new types for this is cumbersome since we want a list of `DateTimeOffset` we just happen to want to initialize it from another type. To get around sealed types and the need to implement wrapper types or derivations, VB.NET has supported using extension methods to expand the `Add()` options on a type. I like this idea since, in the previous example, our list is really still of `DateTimeOffset` and we want others to see it that way, we just happen to support adding `string` values; why should we be forced to use a different type for that? Alas ((Cue Top Gear voice style)), this feature was not included in C#…until now. As of C#6, this disparity between VB.NET and C# is no more; the compiler will use a matching `Add()` extension method in lieu of an appropriate `Add()` method on the type itself.

public static class Extensions
{
    public static void Add(this List<DateTimeOffset> list, string value)
    {
        list.Add(DateTimeOffset.Parse(value));
    }
}

Interestingly, this change to how C# resolves overloaded methods is very specific in that it only supports `Add()` extension methods and not extension methods in other pattern-based scenarios like `GetEnumerator`. I am not certain why this so, since I can imagine some cases where enumerating an existing non-enumerated type might be quite nice3, though I expect is is because it would not be clear what was going to get enumerated and therefore, the code would be ambiguous and hard to follow4. The `Add()` method usage in an initializer does not have this ambiguity as the compiler makes it clear if it found a suitable `Add` method that matches both the collection type and the type of the element being added.

Index Initializers

The other change to collection initializers in C#6 is the introduction of index intializer syntax. This new syntax is similar to the existing collection initializer syntax we have discussed, except that instead of using `Add()` methods, it uses indexers. With index-based collection initialization we can specify values for specific indices in a collection. This works for any indexer that a collection implements. Traditionally, we might initialize a `Dictionary<string,string>` using the `Add()` method pattern like this:

var pairs = new Dictionary<string, string>
{
    {"address","12 This Way, Anywhere"},
    {"name", "Bob Foo"},
    {"title", "Master of the universe"}
};

But with the index initializer syntax, we can make it clear that one string indexes the other to make this much more readable as:

var pairs = new Dictionary<string, string>
{
    ["address"] = "12 This Way, Anywhere",
    ["name"] = "Bob Foo",
    ["title"] = "Master of the universe"
};

I cannot speak for anyone else, but I think this really makes the code easier to read. Note, however, that this new index syntax cannot be mixed with traditional initializer syntax; for example, the following is invalid:

var pairs = new Dictionary<string, string>
{
    {"address","12 This Way, Anywhere"},
    ["name"] = "Bob Foo",
    ["title"] = "Master of the universe"
};

I think it is okay that they cannot be mixed. One way is using `Add()` method overload resolution to set values and the other is using indexers; these use different semantics and often have different implementations and connotations. By mixing them, the code becomes muddled and loses meaning; are we specifying records in a collection or are we mapping specific indexes to their records?

In Conclusion

Both of these changes to collection initialization are reasonably subtle. Of all the features C#6 brings us, these are perhaps going to be used the least. In fact, when I started writing this post I was unsure of their value. However, as I wrote and thought of usage examples, I came to the realisation that although they cater to perhaps infrequent scenarios, these changes to collection initializers each provide nice additions to the C# language. Index initializers remove a little ambiguity from the initialization of indexed collections, such as dictionaries, whereas the expansion of `Add()` method overload resolution to include extension methods reduces the number of frivolous types we have to create. In short, they allow us to write simpler, clearer code, and that is a beautiful thing.

  1. pre-C#6 [↩]
  2. A contrived example to be sure, but illustrative none-the-less [↩]
  3. Such as enumerating the lines from a file stream [↩]
  4. Much clearer to write a `LineEnumerator` wrapper for `FileStream` and use it explicitly [↩]

LINQ: Understanding Your Query Chain

This is part of a short series on the basics of LINQ:

This is the third part in my small series on LINQ and it covers what I feel is the most important thing to understand when using LINQ, query chains. We are going to build on the deferred execution concepts discussed in the last entry and look at why it is important to know your query operations.

Each method in a LINQ query is either immediately executed or deferred. When deferred, a method is either lazily evaluated one element at a time or eagerly evaluated as the entire collection. Usually, you can determine which is which from the documentation or, if that fails, a little experimentation. Why does it matter? This question from StackOverflow provides us with an example:

For those that did not read it or do not understand the problem, let me summarize. The original poster had a problem where values they had obtained from a LINQ query result, when passed into the `Except()` method on that same query, did not actually exclude anything. It was as if they had taken the sequence `1,2,3,4`, called `Exclude(2)`, and that had returned `1,2,3,4` instead of the expected `1,3,4`. On the surface, the code looked like it should work, so what was going on? To explain, we need a little more detail.

The example code has a class that described a user. An XML file contained user details and this is loaded into a sequence of `User` instances using LINQ-to-XML.

IEnumerable<IUser> users = doc.Element("Users").Elements("User").Select
        (u => new User
            { ID = (int)u.Attribute("id")
              Name = (string)u.Attribute("name")
            }
        ).OfType<IUser>();       //still a query, objects have not been materialized

As noted in the commentary, the poster understood that at this point, the query is not yet evaluated. With their query ready to be iterated, they use it to determine which users should be excluded using a different query.

public static IEnumerable<IUser> GetMatchingUsers(IEnumerable<IUser> users)
{
     IEnumerable<IUser> localList = new List<User>
     {
        new User{ ID=4, Name="James"},
        new User{ ID=5, Name="Tom"}
     }.OfType<IUser>();
     var matches = from u in users
                   join lu in localList
                       on u.ID equals lu.ID
                   select u;
     return matches;
}

And then using those results, the originally loaded list of users is filtered.

var excludes = users.Except(matches);    // excludes should contain 6 users but here it contains 8 users

Now, it is clear this code is not perfect and we could rewrite it to function without so many LINQ queries (I will give an example of that later in this post), but we do not care about the elegance of the solution; we are using this code as an example of why it is important to understand what a LINQ query is doing.

As noted in the commentary, when the line declaring the initial `users` query is executed, the query it defines has not. The query does not actually become a real list of users until it gets consumed1. Where does that happen? Go on, guess.

If you guessed `GetMatchingUsers`, you are wrong. All that method does is build an additional level of querying off the initial query and return that new query. If you guessed the `Except()` method, that's wrong too, because `Except()` is also deferred. In fact, the example only implies that something eventually looks at the results of `Except()` and as such, the query is never evaluated. So, for us to continue, let's assume that after the `excludes` variable (containing yet another unexecuted query), we have some code like this to consume the results of the query:

foreach (var user in excludes)
{
   Console.WriteLine(user.ID);
}

By iterating over `excludes`,  the query is executed and gives us some results. Now that we are looking at the query results, what happens?

First, the `Except()` method takes the very first element from the `users` query, which in turn, takes the very first `User` element from the XML document and turns it into a `User` instance. This instance is then cast to `IUser` using `OfType`2.

Next, the `Except()` method takes each of the elements in the `matches` query result and compares it to the item just retrieved from the `users` collection. This means the entire `matches` query is turned into a concrete list. This causes the `users` query to be reevaluated to extract the matched users. The instances of `User` created from the `matches` query are compared with each instance from the `users` query and the ones that do not match are returned for us to output to the console.

It seems like it should work, but it does not, and the key to why is in how queries and, more importantly, deferred execution work.

Each evaluation of a deferred query is unique. It is very important to remember this when using LINQ. If there is one thing to take away from reading my blog today, it is this. In fact, it's so important, I'll repeat it:

Each evaluation of a deferred query is unique.

It is important because it means that each evaluation of a deferred query (in most cases) results in an entirely new sequence with entirely new items. Consider the following iterator method:

IEnumerable<object> GetObject()
{
    yield return new Object();
}

It returns an enumerable that upon being consumed will produce a single `Object` instance. If we had a variable of the result of `GetObject()`, such as `var obj  = GetObject()` and then iterated `obj` several times, each time would give us a different `Object` instance. They would not match because on each iteration, the deferred execution is reevaluated.

If we go back to the question from StackOverflow armed with this knowledge, we can identify that `users` is evaluated twice by the `Except()` call. One time to get the list of exceptions out of the `matches` query and another to process the list that is being filtered. It is the equivalent of this:

IEnumerable<object> GetObjects()
{
    return new[]
    {
        new Object(),
        new Object(),
        new Object(),
        new Object(),
        new Object()
    };
}

void main()
{
   var objects = GetObjects().Except(GetObjects());
   foreach (var o in objects)
   {
        Console.WriteLine(o);
   }
}

From this code, we would never expect `objects` to contain nothing since the two calls to the immediately executed `GetObjects` would return collections of completely different instances. When execution is deferred, we get the same effect; each evaluation of a query is as if it were a separate method call.

To fix this problem, we need to make sure our query is executed once to make the results "concrete", then use those concrete results to do the rest of the work. This is not only important to ensure that the objects being manipulated are the same in all uses of the queried data, but also to ensure that we don't do work more than once3. To make the query concrete, we call an immediately executed method such as `ToList()`, evaluating the query and capturing its results in a collection.

This is our solution, as the original poster of our StackOverflow question indicated. If we change the original `users` query to be evaluated and stored, everything works as it should. With the help of some investigation and knowledge of how LINQ works, we now also know why.

Now that we understand a little more about LINQ we can consider how we might rewrite the original poster's example code. For example, we really should not to iterate the `users` list twice at all; we should see the failure of `Except()` as a code smell that we are iterating the collection too often. Though making it concrete with `ToList()` fixes the bug, it does not fix this inefficiency.

To do that, we can rewrite it to something like this:

public static bool IsMatchingUser(User user)
{
     var localList = new List<User> {
        new User{ ID=4, Name="James"},
        new User{ ID=5, Name="Tom"} }
      .Cast<IUser>()
      .AsReadOnly();

    return localList.Any(u=>u.ID == user.ID && u.Name == user.Name);
}

var users = doc
    .Element("Users")
    .Elements("User")
    .Select(u => new User {
        ID = (int)u.Attribute("id")
        Name = (string)u.Attribute("name") })
    .Where(u => IsMatchingUser(u));

This update only iterates over each user once, resulting in a collection that excludes the users we don't want4.

In conclusion…

My intention here was to show why it is fundamental to know which methods are immediately executed, which ones are deferred, and whether those deferred methods are lazily or eagerly evaluated. At the end of this post are some examples of each kind of LINQ method, but a good rule of thumb is that if the method returns a type other than `IEnumerable` or `IQueryable` (e.g. `int` or `List`), it is immediately executed; all other cases are probably using deferred execution. If a method does use deferred execution, it is also helpful to know which ones iterate the entire collection every time and which ones stop iterating when they have their answer, but for this you will need to consult documentation and possibly experiment with some code.

Just knowing these different types of methods can be a part of your query will often be enough to help you write better LINQ and debug queries faster.  By knowing your LINQ methods, you can improve performance and reduce memory overhead, especially when working with large data sets and slow network resources. Without this knowledge, you are likely to evaluate queries and iterate sequences too often, and instantiate objects too many times.

Hopefully you were able to follow this post and it has helped you get a better grasp on LINQ. In the final post of this series, I will ease up on the deep code analysis, and look at query syntax versus dot notation (aka fluent notation). In the meantime, if you have any comments, I'd love to read them.

Examples of LINQ Method Varieties

Immediate Execution

`Count()`, `Last()`, `ToList()`, `ToDictionary()`, `Max()`, `Aggregate()`
Immediate iterate the entire collection every time

`Any()`, `All()`, `First()`, `Single()`
Iterate the collection until a condition is or is not met

Deferred Execution, Eager Evaluation

`Distinct()`, `OrderBy()`, `GroupBy()`
Iterate the entire collection but only when the query is evaluated

Deferred Execution, Lazy Evaluation

`Select()`,`Where()`
Iterate the entire collection

`Take()`,`Skip()`
Iterate until the specified count is reached

  1. "consumed" is often used as an alternative to "iterated" [↩]
  2. `Cast()` should have been used here since all the objects loaded are of the same type [↩]
  3. This is something that becomes very important when working with large queries that can be time or resource consuming to run [↩]
  4. with more effort, I am certain there are more things that could be done to improve this code, but we're not here for that, so I'll leave is as an exercise for you; I'm generous like that [↩]