Invariant functors
source link: https://blog.ploeh.dk/2022/08/01/invariant-functors/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 functionf a -> f b
. - Contravariance means that any function
a -> b
can be lifted into a functionf b -> f a
. - Invariance means that in general, no function
a -> b
can be lifted into a function overf a
.
In general, that is. A limited escape hatch exists:
"an invariant type [...] allows you to map from
Sandy Maguire, Thinking with Typesa
tob
if and only ifa
andb
are isomorphic. In a very real sense, this isn't an interesting property - an isomorphism betweena
andb
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.
Recommend
-
183
S³FD: Single Shot Scale-invariant Face Detector A PyTorch Implementation of Single Shot Scale-invariant Face Detector. python wider_eval_pytorch.py cd eval/eval_tools_old-version octave wider_eval_pytorch.m
-
47
Making Convolutional Networks Shift-Invariant Again What’s wrong with modern convolutional networks and how can we fix them?
-
6
Conversation Contributor ...
-
1
Copy link Contributor lcnr commented...
-
3
What Is a Unitarily Invariant Norm? A norm on is un...
-
15
Constructing a Time-Invariant Measure of the Socio-economic Status of U.S. Census Tracts Your Privacy We use cookies to make sure t...
-
3
Endomorphism as an invariant functor by Mark Seemann An article (also) for object-oriented programmers. This article is part of
-
6
论文标题:Label-invariant Augmentation for Semi-Supervised Graph Classification论文作者:Han Yue, Chunhui Zhang, Chuxu Zhang, Hongfu Liu论文来源:2022,NeurIPS论文地址:
-
8
Table of ContentsNote: You can find the source code for this project here: https://github.com/GavinRay97/gcc-invariant-plugin...
-
4
Fooling polynomials using invariant theoryIEEE websites place cookies on your device to give you the best user experience. By using our websites, you agree to the placement of these cookies. To learn more, read our
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK