Why isn't Array a generic type?

History

What problems would arise if arrays became a generic type?

Back in C# 1.0 they copied the concept of arrays mainly from Java. Generics did not exist back then, but the creators thought they were smart and copied the broken covariant array semantics that Java arrays have. This means that you can pull off things like this without a compile-time error (but a runtime-error instead):

Mammoth[] mammoths = new Mammoth[10];
Animal[] animals = mammoths;            // Covariant conversion
animals[1] = new Giraffe();             // Run-time exception

In C# 2.0 generics were introduced, but no covariant/contravariant generic types. If arrays were made generic, then you couldn't cast Mammoth[] to Animal[], something you could do before (even though it was broken). So making arrays generic would've broken a lot of code.

Only in C# 4.0 were covariant/contravariant generic types for interfaces introduced. This made it possible to fix the broken array covariance once and for all. But again, this would've broken a lot of existing code.

Array<Mammoth> mammoths = new Array<Mammoth>(10);
Array<Animal> animals = mammoths;           // Not allowed.
IEnumerable<Animals> animals = mammoths;    // Covariant conversion

Arrays implement generic interfaces

Why don't arrays implement the generic IList<T>, ICollection<T> and IEnumerable<T> interfaces?

Thanks to a runtime trick every array T[] does implement IEnumerable<T>, ICollection<T> and IList<T> automatically.¹ From the Array class documentation:

Single-dimensional arrays implement the IList<T>, ICollection<T>, IEnumerable<T>, IReadOnlyList<T> and IReadOnlyCollection<T> generic interfaces. The implementations are provided to arrays at run time, and as a result, the generic interfaces do not appear in the declaration syntax for the Array class.

Can you use all members of the interfaces implemented by arrays?

No. The documentation continues with this remark:

The key thing to be aware of when you cast an array to one of these interfaces is that members which add, insert, or remove elements throw NotSupportedException.

That's because (for example) ICollection<T> has an Add method, but you cannot add anything to an array. It will throw an exception. This is another example of an early design error in the .NET Framework that will get you exceptions thrown at you at run-time:

ICollection<Mammoth> collection = new Mammoth[10];  // Cast to interface type
collection.Add(new Mammoth());                      // Run-time exception

And since ICollection<T> is not covariant (for obvious reasons), you can't do this:

ICollection<Mammoth> mammoths = new Array<Mammoth>(10);
ICollection<Animal> animals = mammoths;     // Not allowed

Of course there is now the covariant IReadOnlyCollection<T> interface that is also implemented by arrays under the hood¹, but it contains only Count so it has limited uses.

The base class Array

If arrays were generic, would we still need the non-generic Array class?

In the early days we did. All arrays implement the non-generic IList, ICollection and IEnumerable interfaces through their base class Array. This was the only reasonable way to give all arrays specific methods and interfaces, and is the primary use of the Array base class. You see the same choice for enums: they are value types but inherit members from Enum; and delegates that inherit from MulticastDelegate.

Could the non-generic base class Array be removed now that generics are supported?

Yes, the methods and interfaces shared by all arrays could be defined on the generic Array<T> class if it ever came into existence. And then you could write, for example, Copy<T>(T[] source, T[] destination) instead of Copy(Array source, Array destination) with the added benefit of some type safety.

However, from an Object-Oriented Programming point of view it is nice to have a common non-generic base class Array that can be used to refer to any array regardless of the type of its elements. Just like how IEnumerable<T> inherits from IEnumerable (which is still used in some LINQ methods).

Could the Array base class derive from Array<object>?

No, that would create a circular dependency: Array<T> : Array : Array<object> : Array : .... Also, that would imply you could store any object in an array (after all, all arrays would ultimately inherit from type Array<object>).

The future

Could the new generic array type Array<T> be added without impacting existing code too much?

No. While the syntax could be made to fit, the existing array covariance could not be used.

An array is a special type in .NET. It even has its own instructions in the Common Intermediate Language. If the .NET and C# designers ever decide to go down this road, they could make the T[] syntax syntactic sugar for Array<T> (just like how T? is syntactic sugar for Nullable<T>), and still use the special instructions and support that allocates arrays contiguously in memory.

However, you would lose the ability to cast arrays of Mammoth[] to one of their base types Animal[], similar to how you can't cast List<Mammoth> to List<Animal>. But array covariance is broken anyway, and there are better alternatives.

Alternatives to array covariance?

All arrays implement IList<T>. If the IList<T> interface were made into a proper covariant interface then you could cast any array Array<Mammoth> (or any list for that matter) to an IList<Animal>. However, this requires the IList<T> interface to be rewritten to remove all methods that might change the underlying array:

interface IList<out T> : ICollection<T>
{
    T this[int index] { get; }
    int IndexOf(object value);
}

interface ICollection<out T> : IEnumerable<T>
{
    int Count { get; }
    bool Contains(object value);
}

(Note that the types of parameters on input positions cannot be T as this would break covariance. However, object is good enough for Contains and IndexOf, who would just return false when passed an object of an incorrect type. And collections implementing these interfaces can provide their own generic IndexOf(T value) and Contains(T value).)

Then you could do this:

Array<Mammoth> mammoths = new Array<Mammoth>(10);
IList<Animals> animals = mammoths;    // Covariant conversion

There is even a small performance improvement because the runtime would not have to check whether an assigned value is type compatible with the real type of the array's elements when setting the value of an element of an array.

My stab at it

I took a stab at how such an Array<T> type would work if it were implemented in C# and .NET, combined with the real covariant IList<T> and ICollection<T> interfaces described above, and it works quite nicely. I also added the invariant IMutableList<T> and IMutableCollection<T> interfaces to provide the mutation methods that my new IList<T> and ICollection<T> interfaces lack.

I built a simple collection library around it, and you can download the source code and compiled binaries from BitBucket, or install the NuGet package:

M42.Collections – Specialized collections with more functionality, features and ease-of-use than the built-in .NET collection classes.

¹) An array T[] in .Net 4.5 implements through its base class Array: ICloneable, IList, ICollection, IEnumerable, IStructuralComparable, IStructuralEquatable; and silently through the runtime: IList<T>, ICollection<T>, IEnumerable<T>, IReadOnlyList<T>, and IReadOnlyCollection<T>.

[Update, new insights, it felt something was missing until now]

Regarding the earlier answer:

• Arrays are covariant like other types can be. You can implement things like 'object[] foo = new string[5];' with covariance, so that is not the reason.
• Compatibility is probably the reason for not reconsidering the design, but I argue this is also not the correct answer.

However, the other reason I can think of is because an array is the 'basic type' for a linear set of elements in memory. I've been thinking about using Array<T>, which is where you might also wonder why T is an Object and why this 'Object' even exists? In this scenario T[] is just what I consider another syntax for Array<T> which is covariant with Array. Since the types actually differ, I consider the two cases similar.

Note that both a basic Object and a basic Array are not requirements for an OO language. C++ is the perfect example for this. The caveat of not having a basic type for these basic constructs is not being able to work with arrays or objects using reflection. For objects you're used to making Foo things which makes an 'object' feel natural. In reality, not having an array base class makes it equally impossible to do Foo -- which is not as frequently used, but equally important for the paradigm.

Therefore, having C# without an Array base type, but with the riches of runtime types (particularly reflection) is IMO impossible.

So more into the details...

Where are arrays used and why are they arrays

Having a basic type for something as fundamental as an array is used for a lot of things and with good reason:

• Simple arrays

Yea well, we already knew that people use T[], just like they use List<T>. Both implement a common set of interfaces, to be exact: IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection and IEnumerable.

You can easily create an Array if you know this. We also all know this to be true, and it's not exciting, so we're moving on...

• Create collections.

If you dig into List you will end up with an Array eventually - to be exact: a T[] array.

So why's that? While you could have used a pointer structure (LinkedList), it's just not the same. Lists are continuous blocks of memory and get their speed by being a continuous block of memory. There's a lot of reasons about this, but simply put: processing continuous memory is the fastest way of processing memory - there are even instructions for that in your CPU that make it faster.

A careful reader might point at the fact that you don't need an array for this, but a continuous block of elements of type 'T' that IL understands and can process. In other words, you could get rid of the Array type here, as long as you make sure there's another type that can be used by IL to do the same thing.

Note that there's value and class types. In order to retain the best possible performance, you need to store them in your block as-such... but for marshalling it's simply a requirement.

• Marshalling.

Marshalling uses basic types that all languages agree upon to communicate. These basic types are things like byte, int, float, pointer... and array. Most notably is the way arrays are used in C/C++, which is like this:

for (Foo *foo = beginArray; foo != endArray; ++foo) 
{
    // use *foo -> which is the element in the array of Foo
}

Basically this sets a pointer at the start of the array and increments the pointer (with sizeof(Foo) bytes) until it reaches the end of the array. The element is retrieved at *foo - which gets the element the pointer 'foo' is pointing at.

Note again that there are value types and reference types. You really don't want a MyArray that simply stores everything boxed as an object. Implementing MyArray just got a hell of a lot more tricky.

Some careful readers can point at the fact here that you don't really need an array here, which is true. You need a continuous block of elements with the type Foo - and if it's a value type, it must be stored in the block as the (byte representation of the) value type.

• Multi-dimensional arrays

So more... What about multi-dimensionality? Apparently the rules aren't so black and white, because suddenly we don't have all the base classes anymore:

int[,] foo2 = new int[2, 3];
foreach (var type in foo2.GetType().GetInterfaces())
{
    Console.WriteLine("{0}", type.ToString());
}

Strong type just went out of the window, and you end up with collection types IList, ICollection and IEnumerable. Hey, how are we supposed to get the size then? When using the Array base class, we could have used this:

Array array = foo2;
Console.WriteLine("Length = {0},{1}", array.GetLength(0), array.GetLength(1));

... but if we look at the alternatives like IList, there's no equivalent. How are we going to solve this? Should introduce a IList<int, int> here? Surely this is wrong, because the basic type is just int. What about IMultiDimentionalList<int>? We can do that and fill it up with the methods that are currently in Array.

• Arrays have a fixed size

Have you noticed that there are special calls for reallocating arrays? This has everything to do with memory management: arrays are so low-level, that they don't understand what growth or shrinking are. In C you would use 'malloc' and 'realloc' for this, and you really should implement your own 'malloc' and 'realloc' to understand why exactly having fixed sizes is important for all things you directly allocate.

If you look at it, there's only a couple of things that get allocated in a 'fixed' sizes: arrays, all basic value types, pointers and classes. Apparently we handle arrays differently, just like we handle basic types differently.

A side note about type safety

So why need these all these 'access point' interfaces in the first place?

The best practice in all cases is to provide users with a type safe point of access. This can illustrated by comparing code like this:

array.GetType().GetMethod("GetLength").Invoke(array, 0); // don't...

to code like this:

((Array)someArray).GetLength(0); // do!

Type safety enable you to be sloppy when programming. If used correctly, the compiler will find the error if you made one, instead of finding it out run-time. I cannot stress enough how important this is - after all, your code might not be called in a test case at all, while the compiler will always evaluate it!

Putting it all together

So... let's put it all together. We want:

• A strongly typed block of data
• That has its data stored continuously
• IL support to make sure we can use the cool CPU instructions that make it bleeding fast
• A common interface that exposes all the functionality
• Type safety
• Multi-dimensionality
• We want value types to be stored as value types
• And the same marshalling structure as any other language out there
• And a fixed size because that makes memory allocation easier

That's quite a bit of low level requirements for any collection... it requires memory to be organized in a certain way as well as conversion to IL/CPU... I'd say there's a good reason it's considered a basic type.

Compatibility. Array is a historic type that goes back to the time that there were no generics.

Today it would make sense to have Array, then Array<T>, then the specific class ;)