Why does Linq not provide a lambda parameter instead of IEqualityComparer?

Question

So in things like GroupBy() in Linq, you can provide an implementation of IEqualityComparer<T> to help with object comparisons. It seems, though, that it would be easier to simply pass in a lambda expression.

Example:

// current implementation
myCollection.GroupBy(c => c.Foo, c => c.Bar, new FooBarComparer());

// it seems easier to...
myCollection.GroupBy(c => c.Foo, c => c.Bar, (x, y) => x.Baz == y.Baz);

Given a simple implementation of IEqualityComparer<T> like this:

public class FooBarComparer : IEqualityComparer<FooBar> {
    public bool Equals(FooBar x, FooBar y) {
        return x.Baz == y.Baz;
    }

    public int GetHashCode(FooBar obj) {
        return obj.GetHashCode();
    }
}

It seems that providing a lambda expression could be just as effective. As it stands now, if I try to pass in an IEqualityComparer<T> with a Linq query to a database, it fails because SQL Server (or whatever) doesn't know anything about my class. It seems that a lambda would be able to be translated into SQL that can be used in the target database.

Is there a specific reason this is not provided as an option in Linq?

Answer 1

You'd need two lambdas so that GetHashCode has an equivalent as well. Besides that this would work, yes. There are some LINQ methods that do not make use of hash codes but that use equality (Enumerable.Contains).

I guess it's just to have a standard API for equality that the whole BCL uses. You can easily convert between delegate and comparer by using a delegate-backed comparer implementation or by converting myComparer.Equals to a delegate.

For remoting expressions to the database is is not easy to remote a comparer expression. GROUP BY does not support that in SQL. It can surely be made to work but it is a niche use case (actually if the comparer expression for a GroupBy does not provide an equality relation I'm not sure how that would turn out when translated to SQL).

Answer 2

To make an efficient GroupBy/Distinct you need two things:

• An equality comparer
• An hash generator, to create an hash dictionary

OR you can follow the C++ route

• A comparator able to order the elements, so that you are able to create a tree

If you only have an equality comparer, then the difficulty of doing the GroupBy is something like O(n^2), because if you have 5 elements, you need 5 + 4 + 3 + 2 + 1 comparisons, so n * (n + 1) / 2 so 15. This is something a "good" library wouldn't ever permit you to do (and no sane SQL server would ever do!)

Now, clearly the LINQ library could analyze your equality lambda, see that it is

(x, y) => x.Baz == y.Baz

see that it is symmetrical, so that the left term and the right term are in the form

x => x.Baz

and use this to generate an hasher and select a comparer. But at this point, wouldn't it be easier to do directly

myCollection.GroupBy(c => c.Foo.Baz) 

Yes, that you can do :-)

And then,

myCollection.GroupBy(c => c.Foo.Baz, c => new { c.Foo, c.Bar })
            .Select(c => new { Key = c.First().Foo, Values = c.Select(x => x.Bar) })

That is quite similar to your intended GroupBy (the only difference is that the values are in a Values IEnumerable<>)

Now... for the use of the overloads with IEqualityComparer<T>... as I've written in the comments, I do think that they should be used with "stock" comparers, that the LINQ provider can recognize, like the various StringComparer.* (e.g. StringComparer.OrdinalIgnoreCase) and the EqualityComparer<T>.Default, that represents the "default" comparer.