Add Enumerable.*By operators (DistinctBy, ExceptBy, IntersectBy, UnionBy, MinBy, MaxBy)

[GSPP]

I propose to add LINQ methods of the pattern *By. For example:

    IEnumerable<TSource> DistinctBy<TSource, TKey>(
         IEnumerable<TSource> source,
         Func<TSource, TKey> keySelector,
         IEqualityComparer<TKey> comparer = null)

This method would behave like Distinct except that equality is determined based on the key provided by keySelector. The key could be any value including anonymous types and value tuples.

A motivating case could be this:

	IEnumerable<Order> allOrders = GetTransactions();
	IEnumerable<int> completedOrderIDs = GetCompletedOrderIDs();
	IEnumerable<Order> remainingOrders =
          allOrders.ExceptBy(completedOrderIDs, order => order.ID, orderID => orderID);

Logic like that is reasonably common in business logic code. It is not easy to implement without ExceptBy. In particular, the following is undesirable because it leads to quadratic cost and repeated enumeration:

	IEnumerable<Order> remainingOrders = allOrders.Where(o => !completedOrderIDs.Contains(o.ID));

In the past I have had a need for *By methods many times so I have written them myself. A web search reveals great interest. I believe there is a strong case for adding methods like this.

There has been interest on this issue tracker as well:

• Feature Request: Overload for Distinct to receive a func. dotnet/runtime#27665
• Consider adding more LINQ operators from Ix.NET dotnet/runtime#19522
• Add commonly required Enumerable methods (DistinctBy, ExceptBy, AsChunked, ...) dotnet/runtime#14753

Proposed API

@eiriktsarpalis has provided the following shape for API review. Please refer to my original proposal below for reference.

namespace System.Linq
{
    public static class Enumerable
    {
        public static IEnumerable<TSource> DistinctBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
        public static IEnumerable<TSource> DistinctBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey>? comparer);
        
        public static IEnumerable<TSource> ExceptBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector);
        public static IEnumerable<TSource> ExceptBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector, IEqualityComparer<TKey>? comparer);
        
        public static IEnumerable<TSource> IntersectBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector);
        public static IEnumerable<TSource> IntersectBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector, IEqualityComparer<TKey>? comparer);
        
        public static IEnumerable<TSource> UnionBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector);
        public static IEnumerable<TSource> UnionBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector, IEqualityComparer<TKey>? comparer);
        
        public static TSource MinBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector);
        public static TSource MinBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult>? comparer);
        
        public static TSource MaxBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector);
        public static TSource MaxBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult>? comparer);
        
        // Missing min & max overloads accepting custom comparers added for completeness
        public static TResult Min<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult>? comparer);
        public static TResult Max<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult>? comparer);
    }
}

and equivalent Queryable APIs:

namespace System.Linq
{
    public static class Queryable
    {
        public static IQueryable<TSource> DistinctBy<TSource, TKey>(this IQueryable<TSource> source, Expression<Func<TSource, TKey>> keySelector);
        public static IQueryable<TSource> DistinctBy<TSource, TKey>(this IQueryable<TSource> source, Expression<Func<TSource, TKey>> keySelector, IEqualityComparer<TKey>? comparer);

        public static IQueryable<TSource> ExceptBy<TSource, TKey>(this IQueryable<TSource> source1, IEnumerable<TSource> source2, Expression<Func<TSource, TKey>> keySelector);
        public static IQueryable<TSource> ExceptBy<TSource, TKey>(this IQueryable<TSource> source1, IEnumerable<TSource> source2, Expression<Func<TSource, TKey>> keySelector, IEqualityComparer<TKey>? comparer);

        public static IQueryable<TSource> IntersectBy<TSource, TKey>(this IQueryable<TSource> source1, IEnumerable<TSource> source2, Expression<Func<TSource, TKey>> keySelector);
        public static IQueryable<TSource> IntersectBy<TSource, TKey>(this IQueryable<TSource> source1, IEnumerable<TSource> source2, Expression<Func<TSource, TKey>> keySelector, IEqualityComparer<TKey>? comparer);

        public static IQueryable<TSource> UnionBy<TSource, TKey>(this IQueryable<TSource> source1, IEnumerable<TSource> source2, Expression<Func<TSource, TKey>> keySelector);
        public static IQueryable<TSource> UnionBy<TSource, TKey>(this IQueryable<TSource> source1, IEnumerable<TSource> source2, Expression<Func<TSource, TKey>> keySelector, IEqualityComparer<TKey>? comparer);

        public static TSource MinBy<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector);
        public static TSource MinBy<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector, IComparer<TResult>? comparer);

        public static TSource MaxBy<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector);
        public static TSource MaxBy<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector, IComparer<TResult>? comparer);

        // Missing min & max overloads accepting custom comparers added for completeness
        public static TResult Min<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector, IComparer<TResult>? comparer);
        public static TResult Max<TSource, TResult>(this IQueryable<TSource> source, Expression<Func<TSource, TResult>> selector, IComparer<TResult>? comparer);
    }
}

EDIT @eiriktsarpalis: the key change in this amendment is that the ExceptBy and IntersectBy overloads do not allow heterogeneous element types for the second parameter. This makes it less of a join-like construct and more compatible with both the existing Except and Intersect methods as well as the proposed signature for UnionBy. Please follow the conversation after this comment for more details on the issue.

Open Questions

• The ExceptBy and IntersectBy methods can be generalized by admitting heterogeneous element types in the second parameter. This enables applications like the one cited in the first example, at the cost of requiring a separate keySelector argument for the second collection. Note that this generalization is not admissible in the UnionBy case.
• Should the *By methods accept custom comparers for the key types in addition to key selector lambdas? While there is certainly precedent for similar methods in LINQ, there is also an element of over-engineering here: the natural equality/ordering semantics of ad-hoc key projections are almost always sufficient. YAGNI.

Original API Proposal

Here is the API proposal. All of these methods come with an overload with and without comparer. I kept the existing naming conventions and argument ordering.

namespace System.Linq
{
    public static class Enumerable
    {
        public static IEnumerable<TSource> DistinctBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector);
        public static IEnumerable<TSource> DistinctBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer);

        public static IEnumerable<TSource> ExceptBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TKey> second, Func<TSource, TKey> keySelectorFirst);
        public static IEnumerable<TSource1> ExceptBy<TSource1, TSource2, TKey>(this IEnumerable<TSource1> first, IEnumerable<TSource2> second, Func<TSource1, TKey> keySelectorFirst, Func<TSource2, TKey> keySelectorSecond);
        public static IEnumerable<TSource1> ExceptBy<TSource1, TSource2, TKey>(this IEnumerable<TSource1> first, IEnumerable<TSource2> second, Func<TSource1, TKey> keySelectorFirst, Func<TSource2, TKey> keySelectorSecond, IEqualityComparer<TKey> comparer);

        public static IEnumerable<TSource> IntersectBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TKey> second, Func<TSource, TKey> keySelectorFirst);
        public static IEnumerable<TSource1> IntersectBy<TSource1, TSource2, TKey>(this IEnumerable<TSource1> first, IEnumerable<TSource2> second, Func<TSource1, TKey> keySelectorFirst, Func<TSource2, TKey> keySelectorSecond);
        public static IEnumerable<TSource1> IntersectBy<TSource1, TSource2, TKey>(this IEnumerable<TSource1> first, IEnumerable<TSource2> second, Func<TSource1, TKey> keySelectorFirst, Func<TSource2, TKey> keySelectorSecond, IEqualityComparer<TKey> comparer);

        public static IEnumerable<TSource> UnionBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector);
        public static IEnumerable<TSource> UnionBy<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer);

        public static TResult Max<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer);
        public static TResult Max<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer, TResult defaultValue);
        public static TSource MaxBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector);

        public static TSource MaxBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer);
        public static TSource MaxBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer, TSource defaultValue);

        public static TResult Min<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer);
        public static TResult Min<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer, TResult defaultValue);

        public static TSource MinBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector);
        public static TSource MinBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer);
        public static TSource MinBy<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector, IComparer<TResult> comparer, TSource defaultValue);
    }
}

Further notes:

1. DistinctBy: The order of the output elements should be documented to be the same order as the input. Any reasonable implementation that comes to mind does it this way. For compatibility reasons this could not ever be changed anyway after the first version ships. Distinct should be similarly documented if not already done. Distinct already behaves this way.
2. For ExceptBy and IntersectBy the same is true for the first input. Only items from the first input are ever returned and their order can be kept. Except does the same thing today.
3. For UnionBy I'm not sure about the order.
4. For MinBy/MaxBy it should be documented that the first element in the sequence with the minimum/maximum key is returned.
5. MinBy/MaxBy can take a defaultValue which is used in case the sequence is empty. Overloads without default value throw in that case.
6. I added overloads to Min/Max to bring them on par with the functionality added by MinBy/MaxBy (comparer and defaultValue).
7. Note, that the input element types for ExceptBy and IntersectBy can be different. This is because we only ever return items of the first sequence. We need two key selectors in that case. There's a simpler overload that has only one element type as well.

[MgSam]

Not sure why #14753 was closed way back when.

It is crazy that LINQ doesn't have these methods built in. I think it's been rare in the 10 years since LINQ's introduction that I've ever had a project where I don't end up writing one or more of these extension methods again and again myself.

I think the argument (mentioned in the other thread) of, "oh well you can do these things by creating a custom comparer" doesn't hold water. Writing a custom comparer is very heavyweight. And, in practice, I can probably count on one hand the number of times I've seen developers actually go and write their own comparers. Instead they usually a) use home-grown extension methods that do these things or b) fall back to writing a foreach loop.

One of the main points of LINQ is brevity- writing what you want to do, not all the plumbing code required to do it. Forcing users to write a separate class each time they want to slice their enumerable a different way is the absolute antithesis of this.

To implement these methods, I'd imagine it could just use something like Jon Skeet's ProjectionEqualityComparer and call the existing non-*By methods. (Probably deserves a separate issue, but that class should be exposed publicly in the framework proper as well)

[omariom]

@maryamariyan
The original issue is five years old. Seven versions of .NET Core have been released since then.
These methods are extremely convenient (unlike the overloads with IEqualityComparer) and are easy to implement.

[lipchev]

In an effort to unify my own *By extension methods (with the hope that those would someday would become part of the runtime) I came looking for a reference implementation that I could grab.
As far as I can tell the extrema-finding functions from both MoreLINQ and Ix.NET cause the evaluation of the selector function for single-element collections.
The decision to skip it (when possible) does come with the side effects of "hiding" a possible exception occurring in it, but at the same time- there is no "valid selector guarantee" with the empty collection either- so to me it would make sense to avoid the possibly lengthy selector evaluation (when possible)- but since the normal Enumerable.Min(source, selector) does it as well- might be the dominating factor in the final decision...
Anyway, can anybody point me to an existing implementation of the proposed API - looking through these 100+ pages of search results is quite painful (in more than one ways)- and I see no way of filtering out the "*ByTest.cs" files...

[maryamariyan]

/cc: @eiriktsarpalis @adamsitnik

[MgSam]

@terrajobst What needs to happen to get these API suggestions reviewed and get any official feedback from the team? I saw you mention in the standup yesterday that you guys have a clear plate now... :)

[terrajobst]

@terrajobst What needs to happen to get these API suggestions reviewed and get any official feedback from the team? I saw you mention in the standup yesterday that you guys have a clear plate now... :)

The API process is documented. Each area has an owner and it's their responsibility to work with the issue opener to get the issue either into the state api-ready-for-review or closed.

In this case, that's @eiriktsarpalis and @adamsitnik.