Applying functional programming to learn deep and meaningful things about your program

[Jayshua]

I was recently working with a struct passed around during view construction that contained a special msg function with this signature:

(Maybe msg, UpdateType) -> msg

This function lets the user encode a regular msg and an UpdateType msg into a single msg value. But that’s beside the point. What’s important here is that the function is invariant on the msg type parameter.

Functions structured like this are covariant on msg: anything -> msg

Functions structured like this are contravariant on msg: msg -> anything

Functions structured like this are invariant on msg: msg -> msg

(The rules get a bit more complicated when anything is itself a function that contains the msg type in its signature, but we can ignore that.)

You’re probably familiar with regular map functions that look like this: (a -> b) -> Container a -> Container b. Turns out this is only possible with containers that are covariant on their type parameter. Most things are covariant though (lists, maybes, results, etc.), which is why most things have a map function.

This container is contravariant over a:

type ContravariantThing a = ContravariantThing (a -> Int)

It’s not actually possible to define a regular map function for this type. (Try it!) Instead, if you want to change the type parameter, you need to use this function:

contramap : (b -> a) -> ContravariantThing a -> ContravariantThing b
contramap bToA (ContravariantThing innerFunc) =
	ContravariantThing (\bValue -> innerFunc (bToA bValue))

It almost looks like the mapping is happening in reverse. In a way, it is! But that’s a story for another time.

If you have an invariant thing, you need both a forward mapping function and a backward mapping function in order to change the type parameter:

invmap : (a -> b) -> (b -> a) -> InvariantThing a -> InvariantThing b

Which leads me right back to the struct I mentioned earlier. We wanted to implement a map function for the element type we use to build our UI. (Like Html.map.) Since the Element type uses this invariant-on-msg struct it isn’t actually possible! I struggled with the compiler for half an hour before I made the connection that (Maybe msg, UpdateType) -> msg is invariant. With that knowledge I realized that it simply isn’t possible to implement an ordinary map function for the struct. That understanding probably saved another several hours of struggling with the compiler.

Guess this means that the category theory/functional programming stuff can occasionally be useful.

[rupert]

Interesting. What are the rules for more complex function types?

Covariant in a:
b → a

Contravariant in a:
a → b

I am guessing covarient?
b → c → a

Contravariant?
b → a → c

No idea (does it flip it being in a function arg?)
(a → b) → c

[Jayshua]

The intuition for it is whether the function as a whole consumes an a or produces an a.

This function consumes an a: a -> b (contravariant)

This function produces an a: b -> a (covariant)

This function produces an a: (a -> Container b) -> Container c.
Reason: In the definition of this function you have to provide an a to the function argument in order to get a Container b back. It doesn’t matter that the a might not actually be returned from the function as a whole. Inside the function it still has to create an a in order to get a Container b and is therefore covariant on a.

Formally, you can view covariance as positive and contravariance as negative. If the type variable appears as the result of a function, then it is in a positive (covariant) position. If the type variable appears as the input of a function, then it is in a negative (contravariant) position. The names positive and negative are used because you can follow regular multiplication rules to determine the overall variance of a type variable:

(a -> Container b) -> Container c

a appears as the input to (a -> Container b) so it is in a negative position. However, (a -> Container b) is in a negative position in the overall function, so you multiply the two negatives together and conclude that a is in a positive position and is therefore covariant.

(Container b -> a) -> Container c

Same story here. a is in a positive position in the inner function, but that inner function is in a negative position in the overall signature. Positive * negative = negative, so the overall function is contravariant on a. Informally you can see that this function will have an a after calling (Container b -> a) - it didn’t need to create one itself.

a -> b -> c is the same as a -> (b -> c) so the same rules can be applied to conclude that the function is contravariant on a and b and covariant on c.

[rupert]

Thanks for the explanation - I never understood until now why it gets flipped inside a function argument.

This is quite useful stuff to know, as sometimes I have struggled when trying to do map like stuff over functions. I usually managed to get there in the end, but I feel like understanding the terms covariant, contravariant and invariant and how they arise would have gotten me there a lot quicker.

[Jayshua]

You’re welcome! This is the video that really clarified my understanding of variance, higher kinded types, and Haskell’s type classes (functor, applicative, monad, bifunctor, profunctor, etc.)

Phil Freeman - Fun with Profunctors

Not so much because it was explained perfectly, (there are a few parts where I had to sit down and work through an incomplete explanation myself) but because it was such a practical take on the concepts that everything finally clicked into place. He actually gave a concrete explanation for why you would want to implement the Profunctor typeclass for something along with several examples of actually doing it - that’s an explanation I wasn’t able to find anywhere else.

I imagine it was also because I had gotten to the point where I had enough background for it to click into place though, so YMMV. Burritos and all that.