[Proposal] + opeator as a shorthand for Enumerable.Concat

[Opiumtm]

Use of + operator to concatenate two compatible IEnumerable<T> sequences is natural and concatenation of sequences is quite common.

So, instead of

IEnumerable<int> sequence1, sequence2;
// assign values to sequences
// then concat
var concated = sequence1.Concat(sequence2);

allow to write

var concated = sequence1 + sequence2;

As custom operator can't be declared for interface (IEnumerable<T> in this case), there is no manual way to overload + for IEnumerables concatenation.

[DavidArno]

it would be useful if this were expanded slightly to use more than just Concat, so that both of the following would be possible too:

IEnumerable<int> sequence = ...
var concated1 = 1 + sequence; // adds 1 to the start of the enumeration
var concated2 = sequence + 1; // adds 1 to the end of the enumeration

[MillKaDe]

I would prefer this to be solved at the library level instead of the language level.

May be Default Interfaces (#52) could support defining operators, and the + operator could be implemented there:

interface IEnumerable<T> {
  static IEnumerable<T> operator + (IEnumerable<T> a, IEnumerable<T> b) => a?.Concat (b) ?? b;
}

[bondsbw]

Some more suggestions for list and set operators (including the proposal for completeness):

• s + t for s.Concat(t)
• s - t for s.Except(t)
• s & t for s.Intersect(t)
• s | t for s.Union(t)

and their counterparts for updating the original: +=, -=, &=, |=.

edit: Also from Python is s ^ t for symmetric difference (the set of elements in either set but not both).

[MgSam]

Concatenation of IEnumerable is quadratic. This is why the + operator never made sense- it doesn't make sense to encourage more concatenation when you will silently get huge perf costs.

[DavidArno]

@MgSam,

Surely it's only quadratic if eager concatenation is performed? If the returned type is some LazyConcatEnumerable, which simply stores the original enumerations, then this issue shouldn't occur?

Also (and my eyes I bleeding as I read what I'm typing here as it's paining me to say this 🙃), if Concat where made a default interface method, rather than an extension method, various collection types would be free to offer high performance versions of +.

[bondsbw]

Concat isn't really quadratic. It's linear, O(m+n). Iterating over it linearly, as done in the post, is of course quadratic (linear * linear = quadratic).

The result is no different, but I feel calling Concat itself quadratic is misleading. The pain point is the fact that it is linear in the first place. Concat simply eagerly evaluates both inputs (one after the other).

Now I could see a case where someone were to create a list implementation with a constant-time Concat operation (particularly for a linked-list or linked-list-of-lists structure).

[bondsbw]

Nevertheless, someone who has tried and failed to use + in their C# code has certainly searched for the equivalent operation. And they have certainly found Concat() and used it regardless of performance implications, of which they may not have been aware.

So I don't see how adding this feature makes things worse. It just makes things easier to read.

[Opiumtm]

Why it's quadratic if concatenation does simply enumerate over both sequences?

It's equivalent of

IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b) {
    foreach (var i in a) yield return i;
    foreach (var i in b) yield return i;
}

There are no performance problems.

[Opiumtm]

@MillKaDe

In fact it is proportional to the square of the number of concats composed together.

It's quadratic for number of composed concats, not number of elements.
It's very uncommon to do hundreds of concats of hundreds of sequences.

[scalablecory]

@Opiumtm You don't really need hundreds to notice a difference with Concat. It very quickly loses performance. This could easily be changed though.

Regardless of that it is inconsequential to your proposal. I agree with @MillKaDe, it would make more sense for this to be implemented via default interfaces than as a language change.

[Opiumtm]

@scalablecory
It's not so simple. Concatenation of enumerables is part of LINQ, so + operator (as shorthand for LINQ concat) should be translated to LINQ expressions in case of IQueryable<T>. Interface operator wouldn't be translated so it would be useless for queryable LINQ.

[svick]

@Opiumtm

The quadratic behavior is when you're concatenating n sequences (and let's call the total number of items in all sequences m). In such cases, I believe the time complexity is O(n² + m) on .Net Core and O(nm) on .Net Framework (assuming each sequence has the same number of items).

So, at least on .Net Framework, I would expect the performance to be bad even when concatenating just tens of sequences.

[Opiumtm]

@svick
It's implementation-dependent detail and not forget about IQueryable which indeed uses Enumerable.Concat as concatenation operation on LINQ side.

[bondsbw]

Regardless, if you need to concat, you need to concat. Saying that + encourages bad-perf code would only be valid if most people use something other than .Concat() today... and I haven't seen any proof of that.

[MgSam]

Related: #378

[MgSam]

I think the general advice is to just Add all the elements into an ever growing List rather than using Concat over and over again.

In either case, this proposal is really not so much a language request. It would first require extension operators, and then the BCL team would have to actually implement.

[bondsbw]

@MgSam Agreed (I assumed plain IEnumerable<T> sequences when I made that statement).

I am curious, why doesn't Concat special-case the parameters by type? I get much better performance for lists with just this alteration:

if (first is List<T> list1 && second is List<T> list2)
{
    var result = new List<TSource>(list1);
    result.AddRange(list2);
    return result;
}
// else the existing Enumerable.Concat()

[CyrusNajmabadi]

A typecheck incurs its own costs. Now you're taking that hit for all values that are not lists.

Also, you've now made concat non-lazy. And you are causing a memory allocation of size(list1) + size(list2).

[yaakov-h]

Enumerable.Concat performance was improved in .NET Core and IIRC those same changes will come across to .NET Framework 4.7.1.

I don't see "it's currently a slow implementation" as a decent argument against making it a language feature. (There are plenty of other reasons, already. 😄)

[Pzixel]

This feature may be misleading. For example

var result = new[]{1,2,3} + new[]{4,5,6};

I'd rather expect that result is of type int[], but with this feature will make it IEnumerable<int>. Moreover, most of time i really want it to be an array. But sometimes I don't.

I think we can use syntax like:

var result = [new[]{1,2,3}, new[]{4,5,6} ]

similar to F#

let result = [| for i in 1 .. 10 -> i * i |]

And leave + for concatenation of enumerables. But I don't think compiler knows about Enumerable.Concat and I'm not sure it has to.

[bondsbw]

@Pzixel Could operator+ for array types return that type? Same for List<T>, etc.

For that matter, specializing the operator in such a manner could optimize performance for each type.

(And I would love to see list/array comprehensions in C#.)

[Pzixel]

@bondsbw sometimes users want to concat arrays as a new array, sometime just as IEnumerable to not allocate new memory. You cannot fit both use cases with one single operator.

[bondsbw]

@Pzixel I can see that. In C#, + is generally an eager operation that allocates (consider string, which is conceptually like a char[]).

A separate lazy operator may be warranted. Say a {+} b or a (+) b.

[Pzixel]

@bondsbw can't say it's generally an eager operator since it works so for string types only :) Custom code may or not be an eager operation.

Concatenation of sequences is not really often operation (ask yourself how recently did you use UNION ALL in SQL), however, I'd like to have in language, but it's just a nice-to-have feature. Maybe in C# 100500 :)

[Pxtl]

I would say it depends on the type of the references. If I have variables that are typed as arrays or lists, I would expect it to alloc new lists or arrays. If I have variables that are typed as IEnumerables, I would expect it to use a wrapper that iterates across the two enumerables. Remember that it's easy to convert the second to the first with .ToList() or .ToArray()

[jnm2]

ask yourself how recently did you use UNION ALL in SQL

Last week, using LINQ Concat to materialize a read model in EF :-p

[Opiumtm]

ask yourself how recently did you use UNION ALL in SQL

I had used it very extensively for Microsoft Analysis Services dimension SQL view recently. And I had used it for facts SQL view too.

[TonyValenti]

I'm not sure why Enumerable.Concat has to be quadradic. I would suggest something like this:

public static IEnumerable<T> Concat<T>(params IEnumerable<T>[] Enumerables) {
  var ret = new MultiEnumerable<T>();
  foreach(var Enumerable in Enumerables){
    if(Enumerable is MultiEnumerable<T> Multi){
        ret.Enumerables.AddRange(Multi.Enumerables);
    } else {
        ret.Enumerables.Add(Enumerable);
    }
  }

  return ret;
}

public class MultiEnumerable<T> : IEnumerable<T> {

  internal List<IEnumerable<T>> Enumerables = new List<Enumerables>();

  public IEnumerable<T> GetEnumerator(){
    foreach(var Enumerable in Enumberables){
      foreach(var Item in Enumerable){
        yield return Item;
      }
    }
  }

}

[AustinBryan]

Won't you be able to do this yourself once Extension Everything roles out?

[evilguest]

I'd suggest to alter the language a bit in such a way that a + b would be handled as follows:

1. If both a and b are of the built-in numeric types, then it is a built-in addition
2. Otherwise, if we do have a static operator +(a, b) defined in either type that binds to the compile-time types of a and b respectively then this is that operator call
3. Otherwise, capture the longest sequence of + operators (a + b + c + d), and try searching for the a.Concat(b, c, d) performing the lookup according to the usual precedence rules, including the extension methods. If found - this is that method call.
4. Repeat step 3 with one-shorter sequence: a + b + c + d => a.Concat(b, c) + d until a matching Concat method is found
5. If failed, try (new[] {a, b, c, d}).Concat(),
6. Repeat step 5 with shorter sequences (if they would yield a different array type. I.e. string + string + string + int => (new object[] {..}).Concat()=> failure, now try (new string[] {a, b, c}).Concat() + d.

The IEnumerable + IEnumerable would be covered by the items 3 and 4 as soon as the System.Linq namespace is visible, as there is already a suitable Enumerable.Concat() extension method.
This contrivance would also cover the existing case for the strings concatenation, provided we add the suitable helper class with the extension methods redirecting to the string.Concat() in the standard library.

We would also be able to add the eager overloads even for the platform types like T[] and List, as the extension methods can be contributed by anyone.