Why Isn't Array a Generic Type

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>.

What's the reason I can't create generic array types in Java?

It's because Java's arrays (unlike generics) contain, at runtime, information about its component type. So you must know the component type when you create the array. Since you don't know what T is at runtime, you can't create the array.

How to create a generic array in Java?

I have to ask a question in return: is your GenSet "checked" or "unchecked"?
What does that mean?

Checked: strong typing. GenSet knows explicitly what type of objects it contains (i.e. its constructor was explicitly called with a Class<E> argument, and methods will throw an exception when they are passed arguments that are not of type E. See Collections.checkedCollection.

-> in that case, you should write:

public class GenSet<E> {

    private E[] a;

    public GenSet(Class<E> c, int s) {
        // Use Array native method to create array
        // of a type only known at run time
        @SuppressWarnings("unchecked")
        final E[] a = (E[]) Array.newInstance(c, s);
        this.a = a;
    }

    E get(int i) {
        return a[i];
    }
}

Unchecked: weak typing. No type checking is actually done on any of the objects passed as argument.

-> in that case, you should write

public class GenSet<E> {

    private Object[] a;

    public GenSet(int s) {
        a = new Object[s];
    }

    E get(int i) {
        @SuppressWarnings("unchecked")
        final E e = (E) a[i];
        return e;
    }
}

Note that the component type of the array should be the erasure of the type parameter:

public class GenSet<E extends Foo> { // E has an upper bound of Foo

    private Foo[] a; // E erases to Foo, so use Foo[]

    public GenSet(int s) {
        a = new Foo[s];
    }

    ...
}

All of this results from a known, and deliberate, weakness of generics in Java: it was implemented using erasure, so "generic" classes don't know what type argument they were created with at run time, and therefore can not provide type-safety unless some explicit mechanism (type-checking) is implemented.

ArrayType VS Type[] in Typescript

There isn't any semantic difference

There is no difference at all. Type[] is the shorthand syntax for an array of Type. Array<Type> is the generic syntax. They are completely equivalent.

The handbook provides an example here. It is equivalent to write:

function loggingIdentity<T>(arg: T[]): T[] {
    console.log(arg.length);
    return arg;
}

Or:

function loggingIdentity<T>(arg: Array<T>): Array<T> {
    console.log(arg.length);
    return arg;
}

And here is a quote from some release notes:

Specifically, number[] is a shorthand version of Array<number>, just as Date[] is a shorthand for Array<Date>.

About the `readonly` type modifier

TypeScript 3.4, introduces the readonly type modifier. With a precision:

the readonly type modifier can only be used for syntax on array types and tuple types

let err2: readonly Array<boolean>; // error!    
let okay: readonly boolean[]; // works fine

The following declaration is equivalent to readonly boolean[]:

let okay2: ReadonlyArray<boolean>;

Why can't System.Array be a type constraint?

The appropriate syntax to do what you want is this:

void Print<T>(T[] array)
{
    for (int i = 0; i < array.Length; i++)
    {
        Console.Write(array[i]);
    }
}

Why are arrays covariant but generics are invariant?

Via wikipedia:

Early versions of Java and C# did not include generics (a.k.a. parametric polymorphism).

In such a setting, making arrays invariant rules out useful polymorphic programs.
For example, consider writing a function to shuffle an array, or a function that tests two arrays for equality using the Object.equals method on the elements. The implementation does not depend on the exact type of element stored in the array, so it should be possible to write a single function that works on all types of arrays. It is easy to implement functions of type
boolean equalArrays (Object[] a1, Object[] a2);
void shuffleArray(Object[] a);
However, if array types were treated as invariant, it would only be possible to call these functions on an array of exactly the type Object[]. One could not, for example, shuffle an array of strings.

Therefore, both Java and C# treat array types covariantly. For instance, in C# string[] is a subtype of object[], and in Java String[] is a subtype of Object[].

This answers the question "Why are arrays covariant?", or more accurately, "Why were arrays made covariant at the time?"

When generics were introduced, they were purposefully not made covariant for reasons pointed out in this answer by Jon Skeet:

No, a List<Dog> is not a List<Animal>. Consider what you can do with a List<Animal> - you can add any animal to it... including a cat. Now, can you logically add a cat to a litter of puppies? Absolutely not.
// Illegal code - because otherwise life would be Bad
List<Dog> dogs = new List<Dog>();
List<Animal> animals = dogs; // Awooga awooga
animals.add(new Cat());
Dog dog = dogs.get(0); // This should be safe, right?
Suddenly you have a very confused cat.

The original motivation for making arrays covariant described in the wikipedia article didn't apply to generics because wildcards made the expression of covariance (and contravariance) possible, for example:

boolean equalLists(List<?> l1, List<?> l2);
void shuffleList(List<?> l);

Why isn't Array.newInstance(Class?, int) generic?

You can use Array.newInstance(Class<?> componentType, int length) to create

Arrays of Objects: Integer[] a = (Integer[])Array.newInstance(Integer.class, 5);
Arrays of primitives: int[] b = (int[])Array.newInstance(int.class, 5);
Arrays of Arrays: int[][] c = (int[][])Array.newInstance(b.getClass(), 5);

The second example illustrates why this method cannot just return a generic array of objects, as arrays of primitves aren't array of objects (arrays of arrays, on the other hand, are).

Using this helper method...

private static <T> T[] newArray(Class<?> type, int len){
    return (T[])Array.newInstance(type, len);
}

...with int[] b = newArray(int.class, 5); will result in a compilation error:

Incompatible types, required int[], but found T[]

...and with int[] b = (int[])newArray(int.class, 5); will result in a compilation error:

cannot cast Object[] to int[]

Why Isn't Array a Generic Type