Subtyping between function types

Question

In the 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 argument A2 and due to the subtyping relationship, we can pass the same argument to A1.
• Then we apply the function A1 => B1
• Then this function gives B1 and because of the subtyping, which has the form B2

If we draw a venn diagram for this,

• chart 1

• chart 2

  • What is the right diagram for this?
  • How to explain the result using this Venn diagram?

Link: Youtube video

thanks

Answer 1

Call (A1 => B1) for F1 and (A2 => B2) for F2

In order for function F1 to be a subtype of another function F2, we need a type system to accept it instead of F2.

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

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

I'm not sure that charts are a good way to visualize how this fits together, but I would say that of these, chart 1 is the most accurate.

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

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