4 ms·

Covariance and contravariance is often discussed in terms of subtyping, but it goes deeper than this. Generic types can be covariant or contravariant in languag

by jules 8y ago

Covariance and contravariance is often discussed in terms of subtyping, but it goes deeper than this. Generic types can be covariant or contravariant in languages without subtyping too. The List<T> type is covariant because it supports a map operation: given a function A -> B and a List<A> you can get a List. That phenomenon in mathematics is where the terms covariance and contravariance came from. The covariance you see in OO languages is the special case when the function A -> B is an upcast from the subtype A to the supertype B.

olliej 8y ago
No list<> is not covariant (it’s even mentioned that collections aren’t covariant in the article). Your example, map() is a function that takes list<a>, and a function of type a->b, and uses that to produce a value of type list. Note that at no point is a value of type List<A> ever treated as a value of type List You may be confused by how member syntax looks in OO languages. What you need to realize that List<T>::map(A->B) is an alias to a function along the lines of List_map<A,B>(List<A>, A->B)->List Again there’s no actual subtyping relationship implied between list<a> and list
- jules 8y ago
 List::map vs List_map is merely a syntactic difference. That's not the issue. Mutable collections are invariant, immutable collections are covariant. Mutable collections do not support map in the mathematical sense, immutable collections do. I didn't say that if you map List<A> to List that List is then a subtype of List<A>. That is only the case if A is a subtype of B. Rather, the ability to write map implies that List is covariant, and conversely, covariant types support map. A type Foo<T> is covariant if T appears only as an output to methods and not as an input to methods. For such types you can implement map(f) by returning a proxy that calls the original object, but whenever a method returns a value v of type T you return f(v) instead.

by jules 8y ago

olliej 8y ago

No list<> is not covariant (it’s even mentioned that collections aren’t covariant in the article). Your example, map() is a function that takes list<a>, and a function of type a->b, and uses that to produce a value of type list. Note that at no point is a value of type List<A> ever treated as a value of type List You may be confused by how member syntax looks in OO languages. What you need to realize that List<T>::map(A->B) is an alias to a function along the lines of List_map<A,B>(List<A>, A->B)->List Again there’s no actual subtyping relationship implied between list<a> and list

jules 8y ago
List::map vs List_map is merely a syntactic difference. That's not the issue. Mutable collections are invariant, immutable collections are covariant. Mutable collections do not support map in the mathematical sense, immutable collections do. I didn't say that if you map List<A> to List that List is then a subtype of List<A>. That is only the case if A is a subtype of B. Rather, the ability to write map implies that List is covariant, and conversely, covariant types support map. A type Foo<T> is covariant if T appears only as an output to methods and not as an input to methods. For such types you can implement map(f) by returning a proxy that calls the original object, but whenever a method returns a value v of type T you return f(v) instead.