Subtyping between function types

Question

In coursera functional programming course, I came across a subtle concept.

If A2 <: A1 and B1 <: B2, then (A1 => B1) <: (A2 => B2)

Justification

• when we pass an argument to A2 and because of the subtyping relationship, we can pass the same argument to A1.
• Then apply the function A1 => B1
• Then that function gives B1 and because of subtyping that qualifies as B2

If we draw a Venn diagram for this,

• diagram 1

• diagram 2

  • Which is the correct diagram for this?
  • How can the result be explained using that Venn diagram ?

Reference : Youtube video

Thanks

Answer 1

Let's call (A1 => B1) for F1 and (A2 => B2) for F2

For a function F1 to be a subtype of another function F2, we need the type system to accept it in the place of F2.

You can pass any subtype of an argument A to a function that accepts A, but no supertype. This means that, for F1 to be a subtype of F2, it must accept at least everything that F2 accepts as argument, hence A1 must be a supertype of A2.

The output of F1, on the other hand, must be at least as detailed as the output of F2 so it can be used wherever the output of F2 can be used. This means that B1 must be a subtype of B2.

I'm not sure that diagrams are a good way of visualizing how this fits together, but I'd say that, of the two, diagram 1 is the most accurate one.

Let's look at an example: Say you have the function f1(s: Set): Set Then f2(s: Iterable): SortedSet is a subtype of f1, since it can be used in place of f1.

f1 requires its arguments to be of type Set or any subtype of Set. All these arguments are also valid in f2. The output of f1 is a Set, so the output of f2 must be usable as a Set. Since SortedSet is a subtype of Set, this is also true.