# Invariant functors by Mark Seemann

*Containers that support mapping isomorphic values.*

This article series is part of a larger series of articles about functors, applicatives, and other mappable containers. So far, you've seen examples of both co- and contravariant functors, including profunctors. You've also seen a few examples of monomorphic functors - mappable containers where there's no variance at all.

What happens, on the other hand, if you have a container of (generic) values, but it's neither co- nor contravariant? An endomorphism is an example - it's neither co- nor contravariant. You'll see a treatment of that in a later article.

Even if neither co- nor contravariant mappings exists for a container, all may not be lost. It may still be an *invariant functor*.

### Invariance #

Consider a container `f`

(for *functor*). Depending on its variance, we call it *covariant*, *contravariant*, or *invariant*:

*Covariance*means that any function`a -> b`

can be lifted into a function`f a -> f b`

.*Contravariance*means that any function`a -> b`

can be lifted into a function`f b -> f a`

.*Invariance*means that in general, no function`a -> b`

can be lifted into a function over`f a`

.

*In general*, that is. A limited escape hatch exists:

"an invariant type [...] allows you to map from

`a`

to`b`

if and only if`a`

and`b`

are isomorphic. In a very real sense, this isn't an interesting property - an isomorphism between`a`

and`b`

means they're already the same thing to begin with."

In Haskell we may define an invariant functor (AKA exponential functor) as in the invariant package:

class Invariant f where invmap :: (a -> b) -> (b -> a) -> f a -> f b

This means that an *invariant functor* `f`

is a container of values where a translation from `f a`

to `f b`

exists if it's possible to translate contained values both ways: From `a`

to `b`

, and from `b`

to `a`

. Callers of the `invmap`

function must supply translations that go both ways.

### Invariant functor in C# #

It's possible to translate the concept to a language like C#. Since C# doesn't have higher-kinded types, we have to examine the abstraction as a set of patterns or templates. For functors and monads, the C# compiler can perform 'compile-time duck typing' to recognise these motifs to enable query syntax. For more advanced or exotic universal abstractions, such as bifunctors, profunctors, or invariant functors, we have to use a concrete container type as a stand-in for 'any' functor. In this article, I'll call it `Invariant<A>`

.

Such a generic class must have a mapping function that corresponds to the above `invmap`

. In C# it has this signature:

public Invariant<B> InvMap<B>(Func<A, B> aToB, Func<B, A> bToA)

In this example, `InvMap`

is an instance method on `Invariant<A>`

. You may use it like this:

Invariant<long> il = createInvariant(); Invariant<TimeSpan> its = il.InvMap(l => new TimeSpan(l), ts => ts.Ticks);

It's not that easy to find good examples of truly isomorphic primitives, but TimeSpan is just a useful wrapper of `long`

, so it's possible to translate back and forth without loss of information. To create a `TimeSpan`

from a `long`

, you can use the suitable constructor overload. To get a `long`

from a `TimeSpan`

, you can read the Ticks property.

Perhaps you find a method name like `InvMap`

non-idiomatic in C#. Perhaps a more idiomatic name might be `Select`

? That's not a problem:

public Invariant<B> Select<B>(Func<A, B> aToB, Func<B, A> bToA) { return InvMap(aToB, bToA); }

In that case, usage would look like this:

Invariant<long> il = createInvariant(); Invariant<TimeSpan> its = il.Select(l => new TimeSpan(l), ts => ts.Ticks);

In this article, I'll use `Select`

in order to be consistent with C# naming conventions. Using that name, however, will not make query syntax light up. While the name is fine, the signature is not one that the C# compiler will recognise as enabling special syntax. The name does, however, suggest a kinship with a normal functor, where the mapping in C# is called `Select`

.

### Laws #

As is usual with these kinds of universal abstractions, an invariant functor must satisfy a few laws.

The first one we might call the *identity law:*

invmap id id = id

This law corresponds to the first functor law. When performing the mapping operation, if the values in the invariant functor are mapped to themselves, the result will be an unmodified functor.

In C# such a mapping might look like this:

var actual = i.Select(x => x, x => x);

The law then says that `actual`

should be equal to `i`

.

The second law we might call the *composition law:*

invmap f2 f2' . invmap f1 f1' = invmap (f2 . f1) (f1' . f2')

Granted, this looks more complicated, but also directly corresponds to the second functor law. If two sequential mapping operations are performed one after the other, the result should be the same as a single mapping operation where the functions are composed.

In C# the left-hand side might look like this:

`Invariant<IntPtr> left = i.Select(f1, f1p).Select(f2, f2p);`

In C# you can't name functions or variables with a quotation mark (like the Haskell code's `f1'`

and `f2'`

), so instead I named them `f1p`

and `f2p`

(with a *p* for *prime*).

Likewise, the right-hand side might look like this:

Invariant<IntPtr> right = i.Select(ts => f2(f1(ts)), ip => f1p(f2p(ip)));

The composition law says that the `left`

and `right`

values must be equal.

You'll see some more detailed examples in later articles.

### Examples #

This is all too abstract to seem useful in itself, so example are warranted. You'll be able to peruse examples of specific invariant functors in separate articles:

- Endomorphism as an invariant functor
- Natural transformations as invariant functors
- Functors as invariant functors
- Contravariant functors as invariant functors

As two of the titles suggest, all functors are also invariant functors, and the same goes for contravariant functors:

To be honest, invariant functors are exotic, and you are unlikely to need them in all but the rarest cases. Still, I *did* run into a scenario where I needed an invariant functor instance to be able to perform a particular sleight of hand. The rabbit holes we sometimes fall into...

### Conclusion #

Invariant functors form a set that contains both co- and contravariant functors, as well as some data structures that are neither. This is an exotic abstraction that you may never need. It did, however, get me out of a bind at one time.

**Next:**Endomorphism as an invariant functor.

## Comments

Instead of 'compile-time duck typing', I think a better phrase to describe this is structural typing.

Tyson, thank you for writing. I wasn't aware of the term

structural typing, so thank you for the link. I've now read that Wikipedia article, but all I know is what's there. Based on it, though, it looks as though F#'s Statically Resolved Type Parameters are another example of structural typing, in addition to the OCaml example given in the article.IIRC, PureScript's

row polymorphismmay be another example, but it's been many years since I played with it. In other words, I could be mistaken.Based on the Wikipedia article, it looks as though structural typing is more concerned with polymorphism, but granted, so is duck typing. Given how wrong 'compile-time duck typing' actually is in the above context, 'structural typing' seems more correct.

I may still stick with 'compile-time duck typing' as a loose metaphor, though, because most people know what duck typing is, whereas I'm not sure as many people know of structural typing. The purpose of the metaphor is, after all, to be helpful.