linqilookup

Creating ILookups

I've got an ILookup generated by some complicated expression. Let's say it's a lookup of people by last name. (In our simplistic world model, last names are unique by family)

ILookup<string, Person> families;

Now I've got two queries I'm interested in how to build.

First, how would I filter by last name?

var germanFamilies = families.Where(family => IsNameGerman(family.Key));

But here, germanFamilies is an IEnumerable<IGrouping<string, Person>>; if I call ToLookup() on it, I'd best bet would get an IGrouping<string, IGrouping<string, Person>>. If I try to be smart and call SelectMany first I'd end up with the computer doing a lot of unnecessary work. How would you convert this enumeration into a lookup easily?

Second, I'd like to get a lookups of adults only.

var adults = families.Select(family =>
         new Grouping(family.Key, family.Select(person =>
               person.IsAdult())));

Here I'm faced with two problems: the Grouping type doesn't exist (except as an internal inner class of Lookup), and even if it did we'd have the problem discussed above.

So, apart from implementing the ILookup and IGrouping interfaces completely, or make the computer do silly amounts of work (regrouping what has already been grouped), is there a way to alter existing ILookups to generate new ones that I missed?

Solution

  • (I'm going to assume you actually wanted to filter by last name, given your query.)

    You can't modify any implementation of ILookup<T> that I'm aware of. It's certainly possible to implement ToLookup with an immutable lookup, as you're clearly aware :)

    What you could do, however, is to change to use a Dictionary<string, List<Person>>:

    var germanFamilies = families.Where(family => IsNameGerman(family.Key))
                             .ToDictionary(family => family.Key,
                                           family.ToList());

    That approach also works for your second query:

    var adults = families.ToDictionary(family => family.Key,
                                   family.Where(person => persion.IsAdult)
                                         .ToList());

    While that's still doing a bit more work than we might think necessary, it's not too bad.

    EDIT: The discussion with Ani in the comments is worth reading. Basically, we're already going to be iterating over every person anyway - so if we assume O(1) dictionary lookup and insertion, we're actually no better in terms of time-complexity using the existing lookup than flattening:

    var adults = families.SelectMany(x => x)
                     .Where(person => person.IsAdult)
                     .ToLookup(x => x.LastName);

    In the first case, we could potentially use the existing grouping, like this:

    // We'll have an IDictionary<string, IGrouping<string, Person>>
var germanFamilies = families.Where(family => IsNameGerman(family.Key))
                             .ToDictionary(family => family.Key);

    That is then potentially much more efficient (if we have many people in each family) but means we're using groupings "out of context". I believe that's actually okay, but it leaves a slightly odd taste in my mouth, for some reason. As ToLookup materializes the query, it's hard to see how it could actually go wrong though...