Is order relevance implied with IEnumerable<T> or should it be explicit?

Question

To me, IEnumerable<T> in C# (well, .NET) denotes an arbitrary set of data which can be iterated. It can be backed by anything, like the results of a SELECT query, the contents of an array, characters typed by the user in the console, or the digits of Pi. The data cannot be referenced by index, it is not necessarily finite or infinite, nor can it be modified. It could even be a different set of data when called identically later, like an IEnumerable<double> of random numbers. It's just bits of data yielded to a consumer like a foreach loop.

Now consider one concept in something else that deals with data sets: SQL. In SQL, the order of rows unless explicitly specified is not guaranteed and is not relevant. For example, if you do a SELECT * FROM stack_overflow_posts LIMIT 1, there's no implication made by the database that the row you get back is actually the first row that was inserted, nor the oldest row. You need to explicitly order the results with ORDER BY posted_date_time, for example.

Does this same concept apply to enumerations in .NET with IEnumerable<T>? Is the use of IEnumerable<T> an implication that results will always be yielded in a particular order? In the examples I gave earlier, I would say yes, order would be implied, because if they were enumerated in a different order, the results would be meaningless; if you get the characters typed by the user in the console in a different order than the actual keystrokes, what's the point of reading them? Obviously LINQ has OrderBy() to order results however you want, but that's explicit ordering, not implicit.

A class implementing an interface is effectively promising to follow a particular pattern, not just implement methods as defined by the interface. Does IEnumerable<T> imply its data will be yielded in a relevant order, or is it up to consumers of the enumeration to explicitly order if they wish to do so? If I have a method that yields items in an undefined order--or rather, an order that is not relevant to consumers and is subject to change at any point--should I use something other than IEnumerable<T>?

Answer 1

Is the use of IEnumerable<T> an implication that results will always be yielded in a particular order?

No. IEnumerable just guarantees that the object can be iterated over. The fact that List<T>, for example, always outputs items in ascending order according to index is an implementation detail for List<T> specifically.

A class implementing an interface is effectively promising to follow a particular pattern, not just implement methods as defined by the interface. Does IEnumerable<T> imply its data will be yielded in a relevant order, or is it up to consumers of the enumeration to explicitly order if they wish to do so?

No, implementing IEnumerable doesn't imply any order. When consuming an object that's IEnumerable, you must explicitly provide an order if you want to guarantee your data is going to come out in the same order every time.

If you think of the CLR collection types that implement IEnumerable, this is straightforward. Imagine you created a method that returned IEnumerable<string>. That method could return a List<string>, whose implementation of IEnumerable does have a certain order to it, but it could just as easily return a HashSet<string>, for which an order wouldn't make sense.

If I have a method that yields items in an undefined order--or rather, an order that is not relevant to consumers and is subject to change at any point--should I use something other than IEnumerable<T>?

I'd say that IEnumerable<T> suits your needs nicely. To be extra clear, you could document your method and state that the order of items in the result is undefined and could change from call to call.

Answer 2

IEnumerable<T> does not gurantee order but the implementer, or the method returning IEnumerable<T> could guarantee order. For example, File.ReadLines is guaranteed to give you file lines in order. Enumerable.Where is guaranteed to preserve order. However, as you mentioned, you can easily write a method that yields a new GUID every time, and it would have no order.

Answer 3

An unfortunate limitation of IEnumerable<T> is while there are numerous characteristics which most implementations have, and some consumers rely upon, there is no means by which objects can indicate whether they have such characteristics.

Among these characteristics is the fact that if a method receiving an IEnumerable<T> calls GetEnumerator and iterates through the collection's contents, it will reach the end after a finite number of MoveNext calls; if it calls GetEnumerator again without having done anything else with the passed-in IEnumerable<T>, it should receive the same sequence of items in the same order and end at the same point.

Note that the above actually encompasses a number of discrete criteria; there are many implementations which meet all, but it's possible for implementations to meet almost any combination. Among the distinct criteria from the above statement:

1. That an enumeration will yield a finite number of items.

2. That multiple enumerations will always yield the same number of items.

3. That all items which appear in one iteration will appear in another, in the same sequence.

If an enumeration doesn't yield a finite number of items, the question of whether multiple iterations yield the same number is moot. Aside from that, however, it's possible for an implementation of IEnumerable<T> to abide by any of the six remaining combinations of the above criteria:

• Many collections, when used only by one thread, will of course abide by all three.

• A "true" random generator might not abide by any.

• A pseudo-random generator might abide by #3 only.

• A concurrent add-only list might abide by #1 and #3.

• Some other concurrent collections might only abide by #1.

• An array which is used by concurrent code might only abide by #1 and #2.

Although some methods which receive an IEnumerable<T> may malfunction if the passed object fails to abide by some or all of the aforementioned characteristics, the characteristics are not part of the IEnumerable<T> contract, nor is there any way for an IEnumerable<T> to specify what criteria it can meet. The expectation seems to be that code which is going to pass an IEnumerable<T> to a method is responsible for knowing what "kind" of IEnumerable<T> it has, and that methods which pass an IEnumerable<T> received from outside code to a method should somehow convey to their consumers the requirements of the methods to which the IEnumerable<T> instances are passed.

If an IEnumerable<T> is enumerated once, it will return items in some sequence. With most IEnumerable<T> implementations, repeated enumerations will yield the items in the same sequence, and some code relies upon that behavior, but there is nothing in the IEnumerable<T> contract which specifies that..