Does LINQ guarantee ordering with SelectMany?

Question

I have an array of ordered enumerations IorderedEnumerable<T>[] foo , and I want to flatten it so that the ordered enumerations foo are combined together in the order in which they are stored in the array.

For example {{1, 2, 3}, {4, 5}, {6}} => {1, 2, 3, 4, 5, 6}

Can I do this with IOrderedEnumerable<T> bar = foo.SelectMany(x => x); , or does LINQ not guarantee how the order is processed during alignment?

Answer 1

Lists (represented by IEnumerable<T> in.net) along with two operations form a monad, which must obey the laws of the monad . These two operations have different names in different languages, in the wikipedia article Haskell is used, which calls them return and >>= (called "bind"). C # calls >>= SelectMany and has no built-in function for return . However, names are inconsequential, and types are important. Specializes in IEnumerable<T> :

 Return :: T -> IEnumerable<T> SelectMany :: IEnumerable<T> -> Func<T, IEnumerable<U>> -> IEnumerable<U> 

return simply returns a sequence of 1 element containing the given element, for example.

 public static IEnumerable<T> Return<T>(T item) { return new[] { item }; } 

SelectMany already implemented as Enumerable.SelectMany :

 public static IEnumerable<U> SelectMany<T, U>(IEnumerable<T> seq, Func<T, IEnumerable<U>> f) { ... } 

SelectMany accepts an input sequence and a function that generates a different sequence for each element of the input sequence and aligns the resulting sequence of sequences into one.

Repeating the first two monad laws in C #, we have:

Left identity

 Func<T, IEnumerable<U>> f = ... Return(x).SelectMany(f) == f(x) 

Identity

 IEnumerable<T> seq = ... seq.SelectMany(Return) == seq 

In accordance with the law of identity, SelectMany should smooth out each sequence generated by Func<T, IEnumerable<U>> in accordance with the order of the input elements.

Suppose he flattened them in the reverse order, for example.

 new[] { 1, 2 }.SelectMany(i => new[] { i, -i }) == new[] { 2, -2, 1, -1 } 

then

 var s = new[] { 1, 2 } s.SelectMany(Return) == new[] { 2, 1 } != s 

which would not satisfy the requirements of the law of identity.

Answer 2

All LINQ to Objects methods (except, obviously, OrderBy() and ToDictionary() ) will preserve source ordering.