advancedTypes

If `Dog` is a subtype of `Animal`, is `List<Dog>` a subtype of `List<Animal>`?

Whether the candidate can derive variance from mutability instead of memorising a rule. The discriminator is whether they reach for the counterexample — writing a `Cat` into the list — rather than reciting "generics are invariant".

What a strong answer covers

  • For a mutable list, no, and the counterexample writes itself. If List<Dog> were a subtype of List<Animal>, you could pass your list of dogs where a list of animals is expected, and the callee could legally append a Cat. Now the caller reads a Cat out of a List<Dog>. The type system has lied, so the subtyping must be rejected: mutable containers are invariant in their element type.
  • The rule underneath is about position. If the type parameter appears only in output position — you can read a T out and never put one in — the container may be covariant, because a producer of Dog is a fine producer of Animal. If it appears only in input position, it may be contravariant: a consumer of Animal is a fine consumer of Dog. If it appears in both, it must be invariant. Function types are the canonical case: contravariant in the parameter, covariant in the return.
  • Languages then split on where the annotation lives. Declaration-site variance marks the parameter once at the type definition — out T and in T in Kotlin and C#, +T and -T in Scala. Use-site variance annotates at each usage, which is what Java's wildcards do, and is why List<? extends Animal> is readable but not writable.
  • Java arrays are the famous hole: Dog[] really is a subtype of Animal[], which is unsound, and the language patches it with a runtime store check that throws ArrayStoreException. That is the trade made explicit — covariance bought at the price of a check on every array write and an error that can only be discovered by running the program.
✓ Green flags
  • Reaches for the write-a-Cat counterexample immediately.
  • Derives the rule from read/write position rather than stating it.
  • Gets function types right, including contravariance in parameters.
  • Knows declaration-site from use-site variance and can name a language for each.
  • Names Java array covariance as the deliberate unsound exception and what it costs.
✗ Red flags
  • "Yes, because a Dog is an Animal." The subtyping of the element does not lift to the container; that is precisely the question.
  • "No, because generics are erased." Erasure is unrelated — invariance holds in reified generic systems too.
  • "Immutable lists are covariant, so just make everything immutable." Immutability makes covariance *sound*; the language still has to declare it, and most do not by default.
  • "Variance is a Java wildcard thing." It is a property of the type constructor in any language with subtyping and generics, wildcards or not.

Follow-up

What about Function<Animal, Dog> versus Function<Dog, Animal> — which is a subtype of which, and why does the parameter go the other way?

Implementation challenge

What to ask them to write or trace on a whiteboard.

Write the four-line program that breaks Java array covariance, and mark the exact line where the runtime check fires.

The lessons behind it

Variance: Why `List<Dog>` Is Not a `List<Animal>` →Subtyping: What `Dog <: Animal` Licenses →Parametric Polymorphism and the Theorems You Get Free →Type Soundness →What a Type System Actually Proves →
← All questions