This site uses cookies. Continue to use the site as normal if you are happy with this, or read more about cookies and how to manage them.

×

This site uses cookies. Continue to use the site as normal if you are happy with this, or read more about cookies and how to manage them.

×

The contravariance of legumes

The following narration aims to demystify the often overly complex concepts of covariance and contravariance in computer science. We'll discuss it afterwards to go over and explain what is happening. The code is written in Kotlin.

The Setup

/**
 * Legume
 * A leguminous plant (member of the pea family), especially one grown as a crop.
 */
open class Legume

/**
 * Chickpea
 * A round yellowish edible seed, widely used as a pulse.
 * A legume of the family Fabaceae, subfamily Faboideae.
 */
class Chickpea : Legume()

/**
 * Seller
 * Someone who sells things.
 */
class Seller<out T>

/**
 * Buyer
 * Someone who buys things.
 */
class Buyer<in T>

/**
 * Market
 * A place for sellers to sell and buyers to buy.
 */
data class Market(var legumeSeller: Seller<Legume>?, var chickpeaBuyer: Buyer<Chickpea>?)

The Scenario

Suppose we have a Market that is looking for someone to sell Legumes. The role is currently vacant...

// Note that the legumeSeller is currently null
val market: Market = Market(legumeSeller = null, chickpeaBuyer = null)

Now, Market doesn't care what Legumes the seller sells. It just needs to be able to say that it has someone who sells Legumes. As You is a person that knows people - and people know that You is a person that knows people - the Market goes to You:

Market: "Hey, You! Do you know any Legume sellers?"

You: "Why, yes of course! Here, let me introduce you to Chris... She sells Chickpeas."

*Chris stops awkwardly hovering nearby and comes over*

// Note that Chris is a Seller of Chickpeas
val chris: Seller<Chickpea> = Seller()

Market: "Who in their right mind only sells Chickpeas?"

Chris: "I'm stood righ..."

You: "Chris does! You said that you were looking for someone who sells Legumes and Chris sells Chickpeas."

Chris: "And Chickpeas are Legu..."

You: "And Chickpeas are Legumes, so Chris sells Legumes."

Market: "Right. Well, do you know anyone that sells more than just Chickpeas?"

Chris: "Again. Stood righ..."

You: "Nope, just Chris!"

Market: "Okay, fine. Chris, you've got the job."

Chris: "Cool beans."

*You and Market share a look and are inwardly disgusted at Chris' unashamed use of a bean-based pun... but also slightly amused*

// Chris is assigned the role of the Legume Seller
market.legumeSeller = chris

Chris immediately sets up shop so that she can begin selling her Chickpeas.

Some time passes though and Market realises that no one wants to buy Chris' Chickpeas! There are plenty of people wanting to buy butter beans and kidney beans but not Chickpeas. Market decides to approach You again:

Market: "No one is buying Chris' Chickpeas!"

You: "Are you kidneying me?!"

*Market pukes in his mouth a little at such a terrible pun but quickly swallows it and moves on*

*You is also ashamed... but in a good way*

Market: "No, I'm not. I need you to find me someone who loves buying Chickpeas and send them my way."

You: "Not a problem. I know just your man. Sean, come on over here!"

// Note that Sean is a Buyer of Legumes
val sean: Buyer<Legume> = Buyer()

Market: "Has he bean hiding behind that... Wait a minute. I know you! You're..."

Sean: "Sean Bean. Yes, I'm well aware. My surname is Bean, I'm famous and I buy Legumes. And don't think I didn't hear your bean pun just then, either. You, how can I help?"

You: "Well Market has this shoddy Chickpea seller named Chris..."

Chris: "Who is RIGH..."

You: "...but unsurprisingly, no one wants to buy her Chickpeas and as you love buying Legumes..."

Market: "Hang on a minute! Sean buys Legumes?! I need someone to buy Chris' Chickpeas, not Legumes."

*You and Sean are appalled at how Market struggles to understand the contravariance of the situation*

Sean: "Yes, and Chickpeas are Legumes..."

You: "...so Sean will buy Chris' Chickpeas!"

Market: "Hmm. So Sean can buy Chris' Chickpeas, and Chris can sell Sean herpes? I mean her peas!"

You: "They'll be like two peas in a pod!"

Sean: "Hummusing!"

*Sean had to go and take it too far*

// Sean is assigned the role of the Chickpea Buyer
market.chickpeaBuyer = sean

Recap

Okay, so what just happened? Well, ultimately, we made the following two assignments:

var legumeSeller: Seller<Legume> = Seller<Chickpea>()
var chickpeaBuyer: Buyer<Chickpea> = Buyer<Legume>()

You and Market took someone who is a seller of chickpeas and gave them the role of seller of legumes. They then took someone that is a buyer of legumes and gave them the role of buyer of chickpeas.

So how does this work?

Well, we can see from the code that Legume is a base class of Chickpea - that is, Chickpea IS A Legume. That on its own is not enough to imply that Seller<Chickpea> IS A Seller<Legume> or that Buyer<Legume> IS A Buyer<Chickpea>. This is where the keywords in and out in Kotlin come into play.

We can see that the Seller class is defined as

class Seller<out T>

and the Buyer class is defined as

class Buyer<in T>

What these keywords say to the compiler is that

  • the generic type T will only appear in the Seller class in 'out' positions (e.g. methods can return T but not have T as a parameter)
  • the generic type T will only appear in the Buyer class in 'in' positions (e.g. methods can have T as a parameter but not return T)

Without specifying the in and out keywords, the assignments that You and Market made would result in compiler errors.

In fancy terms, the compiler would not be able to guarantee that

  • Seller<T> is covariant with respect to the generic type, T
  • Buyer<T> is contravariant with respect to the generic type, T

The terms covariant and contravariant have been adapted from mathematics so we'll take a moment to cover what they mean at a high level...

Co- and Contravariant

Say we have two variables, x and y and a relationship on those variables, < - less than, for example.

We are then able to make the statement x < y. This may be true or it may not.

Now let's take a function, f on the variables x and y such that f: x → f(x) and f: y → f(y).

We are now able to define covariant, contravariant and invariant:

  • f is covariant with respect to the variables x and y and the relationship <x < yf(x) < f(y)
  • f is contravariant with respect to the variables x and y and the relationship <x < yf(x) > f(y)
  • f is invariant with respect to the variables x and y and the relationship < if it is not covariant or contravariant, i.e. we can make no assumptions about the relationship between f(x) and f(y) even if we know the relationship between x and y

We can see a basic example of each of these if we take the integers and the three functions:

  • double: x → 2*x
  • negative: x → -x
  • square: x → x*x

We notice that double is covariant with respect to x (1 < 22 < 4), negative is contravariant with respect to x (1 < 2-1 > -2) and square is invariant with respect to x (1 < 21 < 4 but -2 < 14 > 1).

Let's now apply this to our example of Buyers and Sellers above.

When is a Chickpea a Legume?

We can view the two classes Seller and Buyer as "functions" of a type, T:

  • Seller: T → Seller<T>
  • Buyer: T → Buyer<T>

And our type, T has a relationship that we'll call extends.

Now using the exact same definitions of covariance and contravariance above, we get:

  • Seller is covariant with respect to T and S and the relationship extendsT extends SSeller<T> extends Seller<S>
  • Buyer is contravariant with respect to T and S and the relationship extendsT extends SBuyer<S> extends Buyer<T>

So by replacing the two definitions

class Seller<T>
class Buyer<T>

with

class Seller<out T>
class Buyer<in T>

we are telling the compiler that we guarantee the covariance of Seller and the contravariance of Buyer. The compiler then happily allows us to assign a Seller<Chickpea> to a Seller<Legume> and a Buyer<Legume> to a Buyer<Chickpea>.

Kotlin makes this a lot easier to remember than Java does by using the words 'in' and 'out' instead of 'extends' and 'super'. The equivalent in Java would be Seller<Chickpea> extends Seller<? extends Legume> and Buyer<Legume> extends Buyer<? super Chickpea>.

All that remains is to convince ourselves that a class that only specifies a generic type in 'out' positions is indeed covariant with respect to that type and that a class that only specifies a generic type in 'in' positions is indeed contravariant with respect to that type. Hopefully, the example of buyers and sellers of legumes in the market is enough to at least make it seem reasonable.


The code for this article can be found here. Feel free to clone it yourself and prove that it compiles.