Exploring contravariance using Swift

Last week we took a deep dive into the map function. First we saw that map on arrays is unique amongst all the functions that transform arrays and satisfy a simple property. That was kind of amazing, because it shows that map wasn’t invented because it was convenient, rather it was only sitting there waiting for us to discover it.

In today’s episode we want to explore the idea of “contravariance”. It’s a kind of composition that hides right in plain sight in the programming world, but for whatever reason we never really come face-to-face with it. So we want to dedicate some time to really study it and build intuitions for it, because it will allow us to uncover new ways of composing things that are otherwise difficult to see.

Variance in subtyping

If you’ve come across the ideas of covariance and contravariance in programming, it most likely had to do with subtyping and perhaps you even heard of the Liskov substitution principle . This is all about when it makes sense to replace a type with either a more specific one ( i.e. subclass) or a more general one ( i.e. superclass). In certain cases you can do one and not the other, or reversed.

Swift has subtyping through subclassing. We should all be very familiar with this because UIKit is a library built with a very deep subclass hierarchy. Just consider this sequence of subclasses that connects UIButton to its root base class NSObject :

// NSObject > UIResponder > UIView > UIControl > UIButton

We are using > to show a super type relation, and we will also use < to show subtype relationships.

When interacting with UIKit we are often writing functions and methods that take UIKit components as inputs or return UIKit components as outputs. And when we do this we will inevitably come face-to-face with needing to feed a subtype or supertype into those functions, or interpreting the output of the function as a subtype or supertype. Let’s look at an example:

func wrapView(padding: UIEdgeInsets) -> (UIView) -> UIView {
  return { subview in
    let wrapper = UIView()
    subview.translatesAutoresizingMaskIntoConstraints = false
    wrapper.addSubview(subview)
    NSLayoutConstraint.activate([
      subview.leadingAnchor.constraint(
        equalTo: wrapper.leadingAnchor, constant: padding.left
      ),
      subview.rightAnchor.constraint(
        equalTo: wrapper.rightAnchor, constant: -padding.right
      ),
      subview.topAnchor.constraint(
        equalTo: wrapper.topAnchor, constant: padding.top
      ),
      subview.bottomAnchor.constraint(
        equalTo: wrapper.bottomAnchor, constant: -padding.bottom
      ),
      ])
    return wrapper
  }
}

This is a helper function for wrapping an existing view inside a new view and applying some padding. It’s a handy function since UIView s do not have a concept of padding in their layouts. And true to our preference to put configuration up front and transformations last, this is a curried function that first takes the padding and then you get back a (UIView) -> UIView function that wraps views.

Here’s how we can use it:

let view = UIView(frame: CGRect(x: 0, y: 0, width: 100, height: 100))
view.backgroundColor = .darkGray

let padding = UIEdgeInsets(top: 10, left: 20, bottom: 30, right: 40)

let wrapper = wrapView(padding: padding)(view)
wrapper.frame.size = CGSize(width: 300, height: 300)
wrapper.backgroundColor = .lightGray
wrapper

This function provides the perfect setting for exploring contravariance. Here’s the signature of wrapView given some padding insets:

wrapView(padding: padding) as (UIView) -> UIView

No surprises there. Now, let’s try tweaking the input type. If this function is fine with us feeding it UIView s, then certainly it must be ok with us feeding, say, a UIButton :

wrapView(padding: padding) as (UIButton) -> UIView

And indeed it is! Really we can use any subclass of UIView :

wrapView(padding: padding) as (UIControl) -> UIView
wrapView(padding: padding) as (UISwitch) -> UIView
wrapView(padding: padding) as (UIStackView) -> UIView

So, what we’re seeing is that on the input we are allowed to substitute in a more specific type ( i.e. a subclass) freely and still get a valid function. What happens if we try feeding in a superclass of UIView ?

wrapView(padding: padding) as (UIResponder) -> UIView

? ‘(UIView) -> UIView’ is not convertible to ‘(UIResponder) -> UIView’

Let’s try that on the output. What if instead of returning a UIView we wanted to return a UIButton :

wrapView(padding: padding) as (UIView) -> UIButton

? ‘(UIView) -> UIView’ is not convertible to ‘(UIView) -> UIButton’

wrapView(padding: padding) as (UIView) -> UIResponder

Or even go all the way back to NSObject :

wrapView(padding: padding) as (UIView) -> NSObject

We can even forget more about this type, and return AnyObject !

wrapView(padding: padding) as (UIView) -> AnyObject

What we’ve discovered here is that functions have subtyping relations just like subclasses, and that it’s subtly different depending on if you are changing the input or the output of the function. For example, we have seen that (UIView) -> UIView is a subtype of (UIButton) -> UIView because anywhere you can use the former you can use the latter. The function just forgets that we have a button and treats it as a plain view. On the other hand, we’ve seen that (UIView) -> UIResponder is a subtype of (UIView) -> UIView because anywhere you can use the former you can just use the latter. We just forget we have a view and treat it as a simple responder.

Let’s generalize this so that we can better see the structure, using < to mean “is a subtype of”:

/*
  If A < B, then

  then (B -> C) < (A -> C)

  then (C -> A) < (C -> B)
*/

There’s something strange here, but it’s hard to see right now. To see it we need to move to a two-dimensional picture!

/*
  If A < B

  then B -> C
         <
       A -> C

  then C -> A
         <
       C -> B
 */

The C s are always grouped together! It becomes more noticeable if we align them!

/*
  If A < B

  then B -> C
         <
       A -> C

  then      C -> A
              <
            C -> B
 */

In the first relation, the position of A and B with respect to the “is a subtype of” relation got flipped. It went from “ A is a subtype of B ” to “something involving B is a subtype of something involving A ”. The roles were flipped.

Whereas in the second relationship the roles did not flip. It went from “ A is a subtype of B ” to “something involving A is a subtype of something involving B ”.

This is the essence of variance. When the order of a relationship is preserved we call it covariant, and when a relationship is reversed we call it contravariant. So, we have seen that subtyping a function by its output is a covariant relationship, and subtyping a function by its input is a contravariant relationship.

/*
  If A < B

  then B -> C
         <              contravariant
       A -> C

  then      C -> A
              <         covariant
            C -> B
 */

This is also a very succinct way of describing the Liskov substitution principle, which says that “if A is a subtype of B then a program involving objects of type B can be replaced with objects of type A without altering its outcome.” That seems reasonable enough! But perhaps we can now more clearly see that hiding in plain site in that statement is a reversal of relationships. You can even see it in how the statement is proposed: “if A is a subtype of B then objects of type B can be replaced by objects of type A ”! Pretty cool stuff!

Now, I think it’s a lil unfortunate that this is the only exposure we typically get to the ideas of covariance and contravariance. There are a lot more instances of it in programming, but it can be hard to see if you are only familiar with the Liskov substitution principle. This is why I think the topic of contravariance belongs squarely in the field of functional programming (and more generally mathematics), because it is almost trivial to see it from the perspective of functions. Let’s explore this!

Variance in functional programming

We’ve come across covariant constructions a few times so far in this series, but we just never named them as such because we hadn’t yet come across contravariant things to contrast them to. One example of a covariant relationship is our old friend map :

func map<A, B>(_ f: (A) -> B) -> ([A]) -> [B] {
  fatalError("Unimplemented")
}

Notice that we have a relationship (A) -> B being lifted up to a relationship ([A]) -> [B] . The order of the A and B with respect to -> has been preserved. In fact all map s we’ve encountered have been covariant: map on optionals, map on Result , and all those strange map s we defined in our episode on map and parametricity.

There was one particular type we looked atin the last episode. We gave it an abstract name F2 , but we’ll give it a proper name now:

struct Func<A, B> {
  let apply: (A) -> B
}

It’s just a struct wrapper around a function from A to B . We sawin that episode that this type supports a map like function on the second type parameter B :

func map<A, B, C>(_ f: @escaping (B) -> C) -> ((Func<A, B>) -> Func<A, C>) {
  return { g in
    Func(apply: g.apply >>> f)
  }
}

Notice that the relationship between B and C is preserved, hence this is a covariant operation. Interesting that map ing on the output of a function is covariant, much like subtyping the output was covariant!

However, we very purposely did not consider what it means to map on the input type parameter A . Let’s see what happens when we try:

func map<A, B, C>(_ f: @escaping (A) -> B) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
    f as (A) -> B
    g.apply as (A) -> C
    // ???
  }
}

These functions don’t match up, so there’s no way to compose them.

Let’s try something a bit strange here and flip our transform function from (A) -> B to (B) -> A .

func map<A, B, C>(_ f: @escaping (B) -> A) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
    f as (B) -> A
    g.apply as (A) -> C
    return Func(apply: f >>> g.apply)
  }
}

Now everything matches up and compiles. This isn’t the map we know and love, though, so we could call it, maybe, fakeMap .

This fakeMap is actually the thing we want when it comes to “transforming” a function by its input, so we should give it a proper name. Well, if map is covariant, then maybe we should call this contramap . And in fact that’s what many languages and libraries go with, although some also use cmap and comap .

func contramap<A, B, C>(_ f: @escaping (B) -> A) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
    Func(apply: f >>> g.call)
  }
}

Another way to see that the arrow flips from map , we can just copy paste the implementation of map on Func and literally flip the >>> arrow!

func contramap<A, B, C>(_ f: @escaping (B) -> A) -> ((Func<A, C>) -> Func<B, C>) {
  return { g in
//    Func(apply: f >>> g.call)
    Func(apply: g.apply <<< f)
  }
}

We defined <<< as backwards composition in our episode on setters in order to compose nested setters together, where backwards composition helped describe our intuitions of diving more deeply into a structure. It’s interesting to see how <<< can help show us, explicitly, the difference in defining map and contramap on this type.

So we have now seen that function arrow -> is covariant in its output, which means that we can “map” over its output via post-composition. And we have also see that function arrow -> is contravariant in its input, which means that we can “contramap” over its input via pre-composition.

Positive and negative positions

Ok, now that we understand what contravariance is, technically speaking, let’s do a lil bit of work to make ourselves comfortable with it because it does seem a bit odd and against our intuitions. Since contravariance seems to naturally pop out of function signatures, let’s see what happens with more complicated functions.

For example, in ourlast episode on map and parametricity we came across the following strange type:

struct F3<A> {
  let run: (@escaping (A) -> Void) -> Void
}

We noted that it was kinda reminiscent of callbacks that we might encounter in Cocoa or other libraries.

Now A is appearing on the left side of function arrow -> , so naturally we’d expect this to be a contravariant construction. However, in thelast episode we defined a map operation on this, and showed that this is the only such implementation of map :

func map<A, B>(_ f: @escaping (A) -> B) -> (F3<A>) -> F3<B> {
  return { f3 in
    return F3 { callback in
      f3.run(f >>> callback)
    }
  }
}

This definitely seems covariant, so what is going on here? Well, notice that A appears on the left side of -> twice. It’s kind of doubly contravariant, and somehow they are neutralizing each other. This is akin to how -1 * -1 = 1 , or if you geometrically reflect something twice you get back where you started, or how two wrongs make a right :stuck_out_tongue:

This analogy with the negative sign of a number is really powerful, and we can use it as a tool to unravel the variance of a type parameter in a construction. We start by saying that a type parameter is in “positive” position if it appears on the right side of -> and in “negative” position if it appears on the left side of -> . Consider the following:

// (A) -> B
//  -1    +1

B is in positive position, and A is in negative position.

We can also use this sign terminology when referring to the sign of an entire expression. For example:

// ((A) -> Void) -> Void
//  |_|    |__|
//  -1      +1
// |___________|    |__|
//      -1           +1

Here, the ((A) -> Void) term is in negative position, and then (A) inside that in negative position.

Now, to determine the sign of the position of a type parameter, we will simply multiply all the -1 s and +1 s that we cross as we move from the outer layer into the inner layer. In this example, to get to A we cross -1 and then cross -1 again, hence -1 * -1 = 1 and A is in positive position.

Let’s look at a more complication function:

// (A) -> ((B) -> C) -> D)

This is a function that takes a value in A and returns a function. The function it returns takes a function (B) -> C and returns a value in D .

Breaking it down, in the outer layer we have two terms:

// (A) -> ((B) -> C) -> D)
// |_|    |______________|
// -1           +1

The second term has more layers, so diving in we see we have two more terms:

// (A) -> ((B) -> C) -> D)
//         |_______|   |_|
//            -1       +1
// |_|    |______________|
// -1           +1

And we still have one more layer in the middle, so diving in yet again we have:

// (A) -> ((B) -> C) -> D)
//         |_|   |_|
//         -1    +1
//         |_______|   |_|
//            -1       +1
// |_|    |______________|
// -1           +1

So we see that in this type B and D are covariant and A and C are contravariant, and therefore you should be able to define map and contramap on those type parameters respectively.

This is a handy tool to be able to instantly unravel the variance of a type parameter.

Yeesh, ok, that’s interesting, but also intense. So we’ve now see that there’s the idea of covariance and contravariance that we were all probably already vaguely familiar with due to subtyping in classes. And then we saw that secretly this was just a special case of variance in functions, which also was just pre-composition and post-composition of functions, which made it seem really simple even though it has scary names.

But, it’s time to ask: what’s the point? Are we going to be able to use this in our everyday code?

Yes! Of course! Contravariance is just the other half, or dual, to covariance which is something we come across a lot and has been useful to us. So it stands to reason that we would find just as much use for contravariance. This is the exact same story that played out with algebraic data types. For so long we had used product types, structs, because that’s all we knew. And then one day we were introduced to sum types, enums, and they seemed strange at first but we found a lot of use for them.

Let’s look at a particular example. Everyone is probably familiar with the Set type in Swift. It’s an unordered collection type that holds at most one instance of a value:

// Set<A>
let xs = Set<Int>([1, 2, 3, 4, 4, 4, 4])

One strange thing about this type is that the generic is constrained to Hashable , which inherits from Equatable . So you are restricted to what kinds of values you are allowed to put into a set. The reason for this is to optimize how values are stored internally, which must be some kind of hash map like a [A: Bool] type. It also has the drawback that you cannot have a set that holds all values in A and you cannot invert a set.

There is another way to formulate a set, and that’s as just a simple predicate function:

struct PredicateSet<A> {
  let contains: (A) -> Bool
}

This completely skips the problem of how to store values in a set, and just jumps straight to answering the question: “does this set contain a particular value”.

Many uses of Set can be replaced with PredicateSet , for example:

let ys = PredicateSet { [1, 2, 3, 4].contains($0) }

Let’s play a little game! For every drawback that I claim Set has I will show that PredicateSet can remedy that drawback, and conversely for every drawback of PredicateSet we will see that Set excels in that area.

PredicateSet on the other hand, being just a contains function under the hood, excels at modeling sets that contain infinitely many values:

let evens = PredicateSet { $0 % 2 == 0 }
let allInts = PredicateSet<Int> { _ in true }
let longStrings = PredicateSet<String> { $0.count > 100 }

xs.forEach { print($0) }

PredicateSet on the other hand has no problem with this. For example, we can invert our xs set to contain all integers that aren’t contained in the set.

let allIntsNot1234 = PredicateSet { !ys.contains($0) }

We can even cook up a function to do this more generally for all predicate sets, but we leave it as an exercise to the viewer!

func map<A, B>(_ f: @escaping (A) -> B) -> (Set<A>) -> Set<B> {
  fatalError("Unimplemented")
}

Well, first of all, this isn’t correct because A and B need to be constrained to Hashable . Now, Swift doesn’t require this because it tries to help you out and infer it since it knows that Set needs Hashable .

So really under the hood it looks like:

func map<A: Hashable, B: Hashable>(_ f: @escaping (A) -> B) -> (Set<A>) -> Set<B> {
  fatalError("Unimplemented")
}

But now we have destroyed the genericity of the function by constraining the type parameters. It’s no longer allowed to work over all types, which is precisely what allowed us to apply parametricity for map and what gave us “theorems for free.”

Not all types can conform to Hashable either, like our Func type, so this form of map definitely precludes some useful things.

This map has even more problems, and to see that let’s implement it:

func map<A: Hashable, B: Hashable>(
  _ f: @escaping (A) -> B
  ) -> (Set<A>) -> Set<B> {

  return { xs in
    var ys = Set<B>()
    for x in xs {
      ys.insert(f(x))
    }
    return ys
  }
}

Because values in Set are unique by their Equatable conformance, we can see that it’s possible to map over a set and get something smaller as a result:

let zs: Set<Int> = [-1, 0, 1]
zs
  |> map(square)
// {0, 1}

This seems strange. So far none of our map s have had this kind of destructive quality about them. Maybe it doesn’t seem like such a big deal, but this problem manifests itself in a much bigger problem, which is it breaks our compositional intuition for map . Recall that we have often said the phrase “the map of a composition is the composition of the map s”. This means:

// map(f >>> g) == map(f) >>> map(g)

We have seen this property hold true for many map s, including arrays, optionals, results, the first and second functions on tuples, and more. We have also seen that it can lead to actual real world performance gains because it allows us to apply two transformations on a contained value at once, rather than creating an intermediate container with a single transformation applied.

Unfortunately, the map on Set we have defined completely breaks this. The quickest way to see this is to define a new generic type with a trivial Hashable implementation:

struct Trivial<A>: Hashable {
  let value: A

  static func == (lhs: Trivial, rhs: Trivial) -> Bool {
    return true
  }

  var hashValue: Int {
    return 1
  }
}

So what could go wrong with this type?

zs
  |> map(Trivial.init >>> ^\.value)
// {-1, 0, 1}

zs
  |> map(Trivial.init)
  |> map(^\.value)
// {-1}

Yikes, that’s a bummer! And this problem can manifest itself in real code! For example, you may have an equatable conformance that only tests on a subset of fields, like perhaps only the id field of a user. Then, as you transform a set of users in various ways, you may (even temporarily) have two users be equal to each other, and then set will collapse them into a single value.

What we are seeing here is that map on Set doesn’t make sense if we want to have all the same intuitions from our other map s.

Now, Swift does actually come with a map on Set unfortunately, but only because Set conforms to the Sequence protocol. And fortunately, Swift’s type system is not strong enough to express that map transforms into the same container, so the function actually returns an array, not a set:

zs.map(Trivial.init).map(^\.value)
// [-1, 0, 1]

We still, however, cannot rely on the order of the resulting array, but at least we aren’t missing values. It’d be nice if this method had a different name from map since it doesn’t share any of the nice properties that the other map ’s have.

PredicateSet and contramap

So, what does this have to do with contramap ? As we have seen, the story of map with Set<A> is messy and doesn’t have a satisfying end. But the contramap story for PredicateSet is simple and wonderful! And in fact, it’s exactly the contramap we defined on Func :

extension PredicateSet {
  // ...
  func contramap<B>(_ f: @escaping (B) -> A) -> PredicateSet<B> {
    return PredicateSet<B>(contains: f >>> self.contains)
  }
}

What does this contramap mean? It is precisely what we wanted from map on Set . If we contramap with a transformation we get a new set where the values have been transformed. However, remember, PredicateSet doesn’t actually contain values, rather it’s just a function for determining the membership of a value, and so to transform the membership means to just precompose with a function!

Lets take our evens set and use contramap to derive an odds set by just shifting all the evens over by 1:

let evens = PredicateSet { $0 % 2 == 0}
let odds = evens.contramap { $0 + 1 }

odds.contains(3) // true
odds.contains(4) // fasle

You can also think of contramap as a way of lifting predicates from substructures to parent structures. Let’s start with a simple predicate:

let isLessThan10 = PredicateSet { $0 < 10 }

We can derive a new predicate set for a User type where we compare their user id:

isLessThan10.contramap(^\User.id)

Now we have a predicate on User that checks if their id is less than 10 .

We could even traverse deeper into User and compare their name’s length:

isLessThan10.contramap(^\User.name.count)

This allows us to focus on very small, composable units that glue together in all types of interesting ways. We were able to derive all new predicate sets with very little work.

And this is the point of studying contramap . We have now seen that there was a very important transformation on PredicateSet hiding right in plain site! It feels a little weird at first since it flips the relationship, but nonetheless its there and its useful.

There are even implementations of PredicateSet in popular languages such as Kotlin and Rust that provide no way to transform sets like this. I think it’s because the composition is kinda strange and might be hidden from you if you are not familiar with looking at things in this way.

This kind of composition will come up many times in this series. We have 3 examples of it in the exercises for this episode, and we will soon come across even more interesting examples!