Proposal (& implementation): LINQ APIs to enable C# 8.0 index and range for IEnumerable<T>

[Dixin]

C# 8.0 introduces index and range features for array and countable types. It is natural and convenient to generally support index and range for all IEnumerable types and LINQ queries. I searched the API review notes, didn't find such APIs, so propose them here.

var element = source1.ElementAt(index: ^5);
var elements = source2.Take(range: 10..^10).Select().Where();

Problem

Index/range are language level features. Currently, they

• work with array (compiled to RuntimeHelpers.GetSubArray, etc.)
• work with countable type
• do not work with "uncountable" IEnumerable<T> sequence, or LINQ query.

Rationale and usage

The goals of these LINQ APIs are:

• Use index to locate an element in sequence.
• Use a range to slice a sequence. The usage should be consistent with array, but with deferred execution.

This enables index and range language features to work with any type that implements IEnumerable<T>, and LINQ queries.

LINQ already has ElementAt(int) and ElementAtOrDefault(int) operators. It would be natural to have a System.Index overload as ElementAt(Index) and ElementAtOrDefault(Index), as well as Slice(Range), so that LINQ can seamlessly work with C# 8.0:

Index index = ...;
var element1 = source1.ElementAt(index);
var element2 = source2.ElementAtOrDefault(^5);
Range range = ...;
var slice1 = source3.Take(range);
var slice2 = source4.Take(2..^2);
var slice3 = source5.Take(^10..);

With these APIs, the C# countable[Index] and countable[Range] syntax are enabled for sequences & LINQ queries as enumerable.ElementAt(Index) and enumerable.Slice(Range).

Proposed APIs

For LINQ to Objects:

namespace System.Linq
{
    public static partial class Enumerable
    {
        public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, Index index);

        public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, Index index);

        public static IEnumerable<TSource> Take<TSource>(this IEnumerable<TSource> source, Range range);
    }
}

For remote LINQ:

namespace System.Linq
{
    public static partial class Queryable
    {
        public static TSource ElementAt<TSource>(this IQueryable<TSource> source, Index index);

        public static TSource ElementAtOrDefault<TSource>(this IQueryable<TSource> source, Index index);

        public static IQueryable<TSource> Take<TSource>(this IQueryable<TSource> source, Range range);
    }
}

API review feedback: @eiriktsarpalis:

We'll be implementing the Queryable equivalents but not the PLINQ ones.

Implementation details (and pull request)

The API review process says PR should not be submitted before the API proposal is approved. So currently I implemented these APIs separately Dixin/Linq.IndexRange:

• Enumerable:
  • ElementAt(Index) and ElementAtOrDefault(Index)
  • Slice(Range)
• Queryable:
  • ElementAt(Index), ElementAtOrDefault(Index), Slice(Range).

Please see the unit tests about how they work.

These proposed APIs can be used by adding NuGet package Linq.IndexRange:

dotnet add package Linq.IndexRange

If this proposal is doable, I can submit a PR quickly.

Open questions

Slice(Range) vs ElementsIn(Range) as name

Should Slice be called ElementsIn(Range)? Currently I implemented both.

• ElementsIn(Range) keeps the naming consistency with original ElementAt(Index). Might it be natural for existing LINQ users?
• Slice is consistent with the countable types, which requires a Slice method to support range. I prefer Slice for this reason.

API review feedback: Rename to Take(Range).
@eiriktsarpalis:

I'm increasingly warming up to exposing the Range method as a Take overload, it really simplifies applications that would typically require chaining Skip and Take calls and the confusion that ensues with order of chaining and indices:

• source.Take(..3) instead of source.Take(3)
• source.Take(3..) instead of source.Skip(3)
• source.Take(2..7) instead of source.Take(7).Skip(2)
• source.Take(^3..) instead of source.TakeLast(3)
• source.Take(..^3) instead of source.SkipLast(3)
• source.Take(^7..^3) instead of source.TakeLast(7).SkipLast(3). This is also more efficient since elements only need to be queued once instead of twice.

Using the name Take also removes any ambiguity in terms of whether out-of-bounds ranges should have Slice semantics or Take semantics. Clearly, it should be the latter. The semantics of the implementation as provided by @Dixin are just right in that regard.

Out of bound handling

If Index is out of the boundaries, for ElementAt(Index), there are 2 options:

• Array behavior: throw IndexOutOfRangeException
• LINQ behavior: throw ArgumentOutOfRangeException. My current implementation goes this way, to keep ElementAt(Index) consistent with orginal ElementAt(int).

If Range goes off the boundaries of source sequence, for Slice(Range), there are 2 options:

• Array behavior: Follow the behavior of array[Range], throw ArgumentOutOfRangeException. I implemented ElementsIn(Range) following this way. See unit tests of ElementsIn.
• LINQ behavior: Follow the behavior of current partitioning LINQ operators like Skip/Take/SkipLast/TakeLast, do not throw any exception. I implemented Slice following this way. See unit test of Slice.

API review feedback: @eiriktsarpalis:

We use LINQ behaviour for out-of-bounds ranges.

Using the name Take also removes any ambiguity in terms of whether out-of-bounds ranges should have Slice semantics or Take semantics. Clearly, it should be the latter.

ElementAt(Index) and Queryable

As @bartdesmet mentioned in the comments, LINQ providers may have issues when they see ElementAt having an Index argument, etc. Should we have a new name for the operator instead of overload? For example, At(Index) or Index(Index)?

Feedback

My original proposal includes other methods like Enumerable.Range(Range) and AsEnumerable(this Range). After discussion with @eiriktsarpalis, we are keeping only ElementAt(Index) and Slice(Range). The original proposal can be found in the history or this link.

I had an email discussion with @MadsTorgersen, merging his feedback here:

Thanks for looping me in, and for the great proposal!

A couple of thoughts:

• I like the proposal! I have no concerns about adding this functionality to IEnumerable. I think that the specific method names should be considered in the larger context of standardizing them for pattern-based compilation, but that’s a detail.
• I agree with most of Bart’s comments on the proposal, including the open questions he points out.

API review feedback

@eiriktsarpalis:

• We're renaming Slice to Take.
• We use LINQ behaviour for out-of-bounds ranges.
• We'll be implementing the Queryable equivalents but not the PLINQ ones.

[bartdesmet]

This looks interesting to me and has been on my list of things to look into for Ix and async LINQ for IAsyncEnumerable<T> over at dotnet/reactive#423. Adding @terrajobst for visibility, given he owns System.Index and System.Range and is also aware of the work in Ix.

From a technical point of view, here are my 0.02 cents:

ElementAt and ElementAtOrDefault

These do make sense and have little ambiguity. Indexing from the end is also not a concern, given TakeLast was also added to LINQ surface before. It'd be nice to define some algebraic identities, e.g. converting ElementAt[OrDefault](i) to Skip(n).First[OrDefault]() if indexing from the start or SkipLast(n).Last[OrDefault]() if indexing from the end, at least for purposes of reviewing a design (and to write tests to assert the identity, though likely not for an implementation when it comes to efficiency).

ElementsIn

This one is a bit more fuzzy. At first glance, it feels like a Slice method and obeys, as a first approximation, to the identity xs.Slice(r).SequenceEqual(xs.ToArray().Slice(r)), except for infinite sequences where ToArray wouldn't terminate. In this case, there'd be exceptions thrown for range violations. Likely ArgumentOutOfRangeException to match existing LINQ operators, rather than OverflowException or something like that.

Alternatively, the identity could be defined in terms of composing Skip[Last] and Take[Last]. However, that'd bring with it other exception behavior (namely, none), because Skip and Take are happy to yield empty sequences.

So the question would be whether to lean towards array semantics or LINQ semantics, and an argument could be made for both sides (though, also based on the Range discussion below, I'd be leaning towards the former).

Range and AsEnumerable

A first question is whether Range implementing IEnumerable<int> would make sense. Most likely not, because "from end" values. Would these be relative to int.MaxValue (as in the open question raised here), which yields integers that are not relative to some list-like thing being indexed into (which is the primary use of Range)? Given this observation, I'm not the biggest fan of an AsEnumerable extension method on Range because it could/would give the false illusion of "if Range were to implement IEnumerable, it'd do it like this".

As for Enumerable.Range, that could make sense given it would be clearer than start, count pairs where one often wonders if the second argument to Range is an index or a count (.. eliminates this confusion). I actually always use named parameters when calling Range to clarify the meaning of the two integer arguments.

Supporting "from end" is a different matter though. On the one hand, given the int return type, one could "suspect" a range 0..int.MaxValue, but a more formally inclined person could argue about the signed nature of int (int.MinValue..int.MaxValue?). I'd personally not be offended by Range throwing Argument[OutOfRange]Exception to indicate there's no "from end" support, and just have it work for cases that would already be expressible using current the Enumerable.Range method, i.e. relative to 0. Open-ended ranges are still a question then, either picking int.MaxValue or throwing.

One could argue that Range(r).Select(i => xs.ElementAt(i)).SequenceEqual(xs.ElementsIn(r)) should be an identity (modulo side-effects of repeated enumeration due to ElementAt), thus values relative to int.MaxValue would not make sense to be treated as indexes passed to ElementAt (i.e. the view where an enumeration of a range yields valid indexes, which it can't do for "from end" indexes if the length of the source is unknown, as is the case for arbitrary IEnumerable<T> objects). That'd also cement ElementsIn (or maybe Slice if that's a better name) behavior of throwing exceptions on range violations (rather than yielding an empty sequence).

Queryable methods

Symmetry makes sense to me; there's been a precedent of extending the surface with TakeLast and SkipLast. However, two possible concerns could be:

• Query providers may break in a variety of ways because they see new overloads to ElementAt[OrDefault]. E.g. they could use reflection to get MethodInfo for these, under the assumption there's only a single overload (e.g. short-sighted use of Single or [0]). Or, they could match simply on name and try to interpret the second argument as Int32 and fail there. Note this is different from TakeLast and SkipLast which were brand new names.
• Query providers could freak out seeing Index or Range objects appear in an expression tree. I'm also not sure on the plan of record for using .. in lambda expressions converted to expression trees; either these would become MethodCallExpression nodes to factory methods (as is the case for $"..." interpolated strings using string.Format), or get rejected by the C# compiler (as is the case for e.g. ?.).

One could argue different ways here:

• .NET Core supports side-by-side, so this type of compat is less of a concern today. We could also make sure that LINQ to SQL and Entity Framework are not affected.
• We can't run the risk, and
  • asymmetry is tolerable (which makes me cringe);
  • we can put it in another library (thus on another EnumerableExtensions method, reducing the risk of query providers blowing up; though if they just check method names, they'd still be in trouble).

For the very last (personally not preferred, to be clear) option, note that the query provider supporting AsQueryable on an IEnumerable<T> is happy to find an IEnumerable<T>-based method on the same declaring type for purposes of rebinding IQueryable<T>-based methods to their "local" equivalent (see https://github.com/dotnet/corefx/blob/master/src/System.Linq.Queryable/src/System/Linq/EnumerableRewriter.cs#L49), so the symmetry can be kept in an extension library (such as Ix).

One data point for this decision could be the proposed addition of a Zip method with a ValueTuple return type, see https://github.com/dotnet/corefx/issues/16011. This is analogous in two ways: reuse of the same method name, and occurrence of a new type in expression trees (though not in an operator argument position, but in the return type, so typically treated differently by query providers).

[Clockwork-Muse]

In light of symmetry, don't forget PLINQ (where operators must be implemented by the library, and not with add-ons).

[Dixin]

@bartdesmet Thank you for your insights. I hope these LINQ operators can be provided in corefx. Since index/range are language level features, it is nice to have them work with not only array, but also any type that implements IEnumerable<T>.

[Dixin]

@Clockwork-Muse I looked at PLINQ before I post this proposal. ParallelEnumerable is not symmetric with Enumerable/Queryable. Enumerable/Queryable have Append/Prepend/SkipLast/TakeLast operators but ParallelEnumerable does not have them.

[Clockwork-Muse]

@Dixin -
That's fine, if you've already reviewed it and decided not to include it.

[joshfree]

@tarekgh

[Dixin]

@joshfree @tarekgh Thank you for labeling this issue. Since it is now in the Future Milestone (issues not triaged to a planned release. Work in this milestone may happen, or may not). Does it mean there is not much chance of actions for the next release? Please suggest what should I do next.

[tarekgh]

Does it mean there is not much chance of actions for the next release? Please suggest what should I do next.

We'll look at the details to ensure the proposed APIs is reasonable and then we'll have the issue reviewed by the design committee. expect will get traction on this when we ship 3.0. if you didn't see any activities by then, please ping us. Usually we'll get into that in right time. Thanks for the proposal.

[Dixin]

Thank you @tarekgh.

[eiriktsarpalis]

For Range(Range) and AsEnumerable(Range), the question is: what does range's start index and end index mean, when the index is from the end? For example, 10..20 can be easily converted to a sequence of 10, 11,12, ... 19, but how about ^20...^10?

The easiest way is to disallow, and throw exception.

My current implementation attempts to make it flexible. Regarding Index's Value can be from 0 to int.MaxValue, I assume a virtual "full range" 0..2147483648, and any Range instance is a slice of that "full range". So:

• Ranges .. and 0.. and ..^0 and 0..^0 are converted to "full sequence" 0, 1, .. 2147483647
• Range 100..^47 is converted to sequence 100, 101, .. 2147483600
• Range ^48..^40 is converted to sequence 2147483600, 2147483601 .. 2147483607
• Range 10..10 is converted to empty sequence

My concern with this approach is that it seems to assign arbitrary meaning to "from end" indices simply to reconcile them with IEnumerable. While throwing is probaby the better approach, it can still be violating user expectations, particularly if the type implementing IEnumerable is a list:

var l = new List<int>() { 1, 2, 3 };

l[^1]; // 3
l.ElementAt(^1); // throws ArgumentOutOfRangeException

It could be argued that a type test could be used and adapt meaning if the underlying type is IList, however this would imply completely changing semantics depending on the subtype. This approach has LSP violation written all over it.

As such, I would recommend against accepting this proposal. We should simply acknowledge that indices and ranges are intended for list-like types, and IEnumerable is much more general-purpose than that.

[Dixin]

@eiriktsarpalis, thank you for your review and feedback. Actually in my proposed implementation, the meaning of "from end" is consistent with existing APIs.

For the proposed static method Enumerable.Range(Range) API:

• Enumerable.Range(2..7) should make sense.
• Enumerbale.Range(^10..^0) may be violate user expectation, as you pointed out.

I agree this particular method should only allow "from start", and disallow "from end".

For the other method Enumerable.ElementAt(Index) that you mentioned, in my proposed implementation, it allows "from start" and "from end" index, and it works exactly the same way as the countable types.

var countable = new List<int>() { 1, 2, 3 };
var enumerable = countable.Hide();

countable[^1] // 3
enumerable.ElementAt(^1) // 3

countable[^10] // ArgumentOutOfRangeException
enumerable.ElementAt(^10) // ArgumentOutOfRangeException

You can also take a look at the unit tests of the proposed implementation.

• I apply Index/Range to built-in countable types,
• and apply Index/Range to enumerable using proposed APIs,
• and make sure they return consistent results/throw consistent exceptions.

You mentioned

IEnumerable is much more general-purpose than that

That's why I proposed these APIs. They would enable Index and Range for so many types in .NET and for LINQ queries. If they keep consistency with existing APIs, they can provide good convenience.

Thank you @eiriktsarpalis so much again for your time. Please let me know what you think.

[eiriktsarpalis]

Thanks for the clarification @Dixin, I mistook your original comment as specifying the "from end" behaviour for all proposed methods and not just Enumerable.Range.

The ElementAt implementation that you linked to seems reasonable. Only downside being that "from end" index support implies O(n) space, however it's probably not that important for the basic applications the method is meant to be used in (though the potential for misuse will probably not go away!)

Going back to Enumerable.Range, are we comfortable with the fact that Enumerable.Range(5 .. 10) evaluates to something completely different than Enumerable.Range(5, 10)? While it may be obvious to people who read the docs or are familiar with .NET nuance and history, for casual users it might not be so. Perhaps using a different method name is preferable here? (for instance the proposed AsEnumerable).

I tend to favour Slice over ElementsIn and would probably prefer non-throwing behaviour for out-of-bounds ranges.

Also, @Dixin, it looks most of the Linq.IndexRange links in your OP are dead. For the purposes of assisting future review, would it be possible to update to permalinks? Thanks.

[eiriktsarpalis]

Supporting "from end" is a different matter though. On the one hand, given the int return type, one could "suspect" a range 0..int.MaxValue, but a more formally inclined person could argue about the signed nature of int (int.MinValue..int.MaxValue?).

Note that ranges only support non-negative numbers, since they are ranges of indices rather than a general-purpose range construct.

[Dixin]

@eiriktsarpalis, thank you for your reply.

The ElementAt implementation that you linked to seems reasonable. Only downside being that "from end" index support implies O(n) space, however it's probably not that important for the basic applications the method is meant to be used in

That is by design.

• If index is from start, ElementAt(Index) is the same as the original ElementAt(int).
• If index is from end, it does take O(n) space, because we do not know the count of the enumerable.
  • enumerable.ElementAt(^5) is equivalent to enumerable.TakeLast(5).ElementAt(0). Regarding consistency & performance, I am following the approach in TakeLast operator implementation.
  • To make it O(1) space, we have to scan the enumerable twice, that not how enumerable supposed to work.

Going back to Enumerable.Range, are we comfortable with the fact that Enumerable.Range(5 .. 10) evaluates to something completely different than Enumerable.Range(5, 10)? While it may be obvious to people who read the docs or are familiar with .NET nuance and history, for casual users it might not be so. Perhaps using a different method name is preferable here? (for instance the proposed AsEnumerable).

I totally realize Enumerable.Range(5 .. 10) is different from the old Enumerable.Range(5, 10). On the other hand I am also thinking, because C# officially introduces the Range concept, would Enumerable.Range(Range) be more natural for modern C# users?

[Clockwork-Muse]

• If index is from end, it does take O(n) space, because we do not know the count of the enumerable.

  • enumerable.ElementAt(^5) is equivalent to enumerable.TakeLast(5).ElementAt(0). Regarding consistency & performance, I am following the approach in TakeLast operator implementation.

Technically this equivalent proposal only requires O(5) space, at most. There's no reason a from-end ElementAt wouldn't be able to take the same shortcuts.

[eiriktsarpalis]

On the other hand I am also thinking, because C# officially introduces the Range concept, would Enumerable.Range(Range) be more natural for modern C# users?

I'm not too sure about that. It seems to me that the particular design of System.Range constrains it to slicing applications, which is unlike ranges in say Python or F# that permit negative ranges, stepping and even float types. As such expressions like Enumerable.Range(-10, 5) would not be expressible using a range overload. I'm wondering though if the concept could somehow be generalized at the language level without introducing any breaking changes.

[Dixin]

Also, @Dixin, it looks most of the Linq.IndexRange links in your OP are dead. For the purposes of assisting future review, would it be possible to update to permalinks?

@eiriktsarpalis I updated the proposal contents including all links. Thank you.

[Dixin]

Technically this equivalent proposal only requires O(5) space, at most. There's no reason a from-end ElementAt wouldn't be able to take the same shortcuts.

@Clockwork-Muse Yes, the proposed implementation only requires O(5) space, at most. Here is the link to the source.

[eiriktsarpalis]

Technically this equivalent proposal only requires O(5) space, at most. There's no reason a from-end ElementAt wouldn't be able to take the same shortcuts.

@Clockwork-Muse Yes, the proposed implementation only requires O(5) space, at most. Here is the link to the source.

It's Θ(k) for ElementAt(^k) calls, so O(n) space by virtue of the fact that source.ElementAt(^source.Count()) is valid.

[Dixin]

I'm not too sure about that.

I am not sure either, and I don't have a preference here, just trying to put everything on the plate for discussion. @eiriktsarpalis please let me know if you want me to remove it from the proposal or make other changes.

[eiriktsarpalis]

At this point I'm fairly convinced that we should hold off from adding the Enumerable.Range and AsEnumerable methods. I think adding the Slice and ElementAt* methods is probably fine despite the performance concerns (the existing ElementAt method isn't too great in that regard either) since they are consuming index types the way they were intended.