Unlock This Episode
Our Free plan includes 1 subscriber-only episode of your choice, plus weekly updates from our newsletter.
Introduction
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.
Subscribe to Point-Free
Access this episode, plus all past and future episodes when you become a subscriber.
Already a subscriber? Log in
Exercises
Determine the sign of all the type parameters in the function
(A) -> (B) -> C
. Note that this is a curried function. It may be helpful to fully parenthesize the expression before determining variance.Solution
Recall from the episode on exponents and algebraic data types that function arrows parenthesize to the right, which means when we write
(A) -> (B) -> C
, we really mean(A) -> ((B) -> C)
. Now we can apply the bracketing method we demonstrated in the episode:// (A) -> ((B) -> C) // |_| |_| // -1 +1 // |_| |________| // -1 +1
So now we see that
A
is negative,B
is also negative, andC
is positive.Determine the sign of all the type parameters in the following function:
(A, B) -> (((C) -> (D) -> E) -> F) -> G
Solution
We will apply the bracketing method to this expression, it’s just a little more involved:
// (A, B) -> (((C) -> (D) -> E) -> F) -> G // |_| |_| |_| // -1 -1 +1 // |_||_| |_______________| |_| // +1 +1 -1 +1 // |____| |______________________| |_| // -1 -1 +1
That’s intense! One tricky part is how we determined that the
A
andB
inside the tuple were in positive position, and this is because tuples are naturally a covariant structure: you can definemap
on the first and second components.Now all we have to do is trace through the layers and multiply all the signs:
* A = -1 * +1 = -1 * B = -1 * +1 = -1 * C = -1 * -1 * -1 = -1 * D = -1 * -1 * -1 = -1 * E = -1 * -1 * +1 = +1 * F = -1 * +1 = -1 * G = +1
And there you have it!
Recall that a setter is just a function
((A) -> B) -> (S) -> T
. Determine the variance of each type parameter, and define amap
andcontramap
for each one. Further, for eachmap
andcontramap
write a description of what those operations mean intuitively in terms of setters.Solution
Again applying the bracketing method we see:
// ((A) -> B) -> (S) -> T // |_| |_| // -1 +1 // |________| |_| |_| // -1 -1 +1
So now we see:
A = -1 * -1 = +1
B = -1 * +1 = -1
S = -1
T = +1
This means we should be able to define
map
onA
andT
, andcontramap
onB
andS
. Here are the implementations of each, with comments that show the types of all the parts we need to plug together:typealias Setter<S, T, A, B> = ((@escaping (A) -> B) -> (S) -> T func map<S, T, A, B, C>(_ f: @escaping (A) -> C) -> (@escaping Setter<S, T, A, B>) -> Setter<S, T, C, B> { return { setter in return { update in return { s in // f: (A) -> C // setter: ((A) -> B) -> (S) -> T // update: (C) -> B // s: S setter(f >>> update)(s) } } } } func map<S, T, U, A, B>(_ f: @escaping (T) -> U) -> (@escaping Setter<S, T, A, B>) -> Setter<S, U, A, B> { return { setter in return { update in return { s in // f: (T) -> U // setter: ((A) -> B) -> (S) -> T // update: (A) -> B // s: S f(setter(update)(s)) } } } } func contramap<S, T, A, B, C>(_ f: @escaping (C) -> B) -> (@escaping Setter<S, T, A, B>) -> Setter<S, T, A, C> { return { setter in return { update in return { s in // f: (C) -> B // setter: ((A) -> B) -> (S) -> T // update: (A) -> C // s: S setter(update >>> f)(s) } } } } func contramap<S, T, U, A, B>(_ f: @escaping (U) -> S) -> (@escaping Setter<S, T, A, B>) -> Setter<U, T, A, B> { return { setter in return { update in return { u in // f: (U) -> S // setter: ((A) -> B) -> (S) -> T // update: (A) -> B // u: U setter(update)(f(u)) } } } }
It’s interesting to see that the implementation of
map
onA
is quite similar tocontramap
onB
, andmap
onT
is similar tocontramap
onS
.Define
union
,intersect
, andinvert
onPredicateSet
.This collection of exercises explores building up complex predicate sets and understanding their performance characteristics.
- Create a predicate set
powersOf2: PredicateSet<Int>
that determines if a value is a power of2
, i.e.2^n
for somen: Int
. - Use the above predicate set to derive a new one
powersOf2Minus1: PredicateSet<Int>
that tests if a number is of the form2^n - 1
forn: Int
. - Find an algorithm online for testing if an integer is prime, and turn it into a predicate
primes: PredicateSet<Int>
. - The intersection
primes.intersect(powersOf2Minus1)
consists of numbers known as Mersenne primes. Compute the first 10. - Recall that
&&
and||
are short-circuiting in Swift. How does that translate tounion
andintersect
? - What is the difference between
primes.intersect(powersOf2Minus1)
andpowersOf2Minus1.intersect(primes)
? Which one represents a more performant predicate set?
- Create a predicate set
It turns out that dictionaries
[K: V]
do not havemap
onK
for all the same reasonsSet
does not. There is an alternative way to define dictionaries in terms of functions. Do that and definemap
andcontramap
on that new structure.Define
CharacterSet
as a type alias ofPredicateSet
, and construct some of the sets that are currently available in the API.Let’s explore what happens when a type parameter appears multiple times in a function signature.
- Is
A
in positive or negative position in the function(B) -> (A, A)
? Define eithermap
orcontramap
onA
. - Is
A
in positive or negative position in(A, A) -> B
? Define eithermap
orcontramap
. - Consider the type
struct Endo<A> { let apply: (A) -> A }
. This type is calledEndo
because functions whose input type is the same as the output type are called “endomorphisms”. Notice thatA
is in both positive and negative position. Does that mean that bothmap
andcontramap
can be defined, or that neither can be defined? - Turns out,
Endo
has a different structure on it known as an “invariant structure”, and it comes equipped with a different kind of function calledimap
. Can you figure out what it’s signature should be?
- Is
Consider the type
struct Equate<A> { let equals: (A, A) -> Bool }
. This is just a struct wrapper around an equality check. You can think of it as a kind of “type erased”Equatable
protocol. Writecontramap
for this type.Consider the value
intEquate = Equate<Int> { $0 == $1 }
. Continuing the “type erased” analogy, this is like a “witness” to theEquatable
conformance ofInt
. Show how to usecontramap
defined above to transformintEquate
into something that defines equality of strings based on their character count.
References
Some news about contramap
Brandon Williams • Monday Oct 29, 2018A few months after releasing our episode on Contravariance we decided to rename this fundamental operation. The new name is more friendly, has a long history in mathematics, and provides some nice intuitions when dealing with such a counterintuitive idea.
Contravariance
Julie Moronuki & Chris MartinThis article describes the ideas of contravariance using the Haskell language. In many ways exploring functional programming concepts in Haskell is “easier” because the syntax is sparse and allows you to focus on just the core ideas.