<commit_before>---
layout: post
title: "Invariant functors"
description: "Containers that support mapping isomorphic values."
date: 2022-08-01 5:49 UTC
tags: [Software Design]
image: "/content/binary/invariant-functor-set-diagram.png"
image_alt: "Set diagram. The biggest set labelled invariant functos contains two other sets labelled functors and invariant functors."
---
{% include JB/setup %}

<div id="post">
	<p>
		<em>{{ page.description }}</em>
	</p>
	<p>
		This article series is part of <a href="/2018/03/19/functors-applicatives-and-friends">a larger series of articles about functors, applicatives, and other mappable containers</a>. So far, you've seen examples of both co- and <a href="/2021/09/02/contravariant-functors">contravariant functors</a>, including <a href="/2021/11/01/profunctors">profunctors</a>. You've also seen a few examples of <a href="/2020/10/19/monomorphic-functors">monomorphic functors</a> - mappable containers where there's no variance at all.
	</p>
	<p>
		What happens, on the other hand, if you have a container of (generic) values, but it's neither co- nor contravariant? An <a href="https://en.wikipedia.org/wiki/Endomorphism">endomorphism</a> is an example - it's neither co- nor contravariant. You'll see a treatment of that in a later article.
	</p>
	<p>
		Even if neither co- nor contravariant mappings exists for a container, all may not be lost. It may still be an <em>invariant functor</em>.
	</p>
	<h3 id="40d4c4a6deed4af593b3cf002563f085">
		Invariance <a href="#40d4c4a6deed4af593b3cf002563f085" title="permalink">#</a>
	</h3>
	<p>
		Consider a <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a> <code>f</code> (for <em>functor</em>). Depending on its variance, we call it <em>covariant</em>, <em>contravariant</em>, or <em>invariant</em>:
	</p>
	<ul>
		<li><em>Covariance</em> means that any function <code>a -&gt; b</code> can be lifted into a function <code>f a -&gt; f b</code>.</li>
		<li><em>Contravariance</em> means that any function <code>a -&gt; b</code> can be lifted into a function <code>f b -&gt; f a</code>.</li>
		<li><em>Invariance</em> means that in general, no function <code>a -&gt; b</code> can be lifted into a function over <code>f a</code>.</li>
	</ul>
	<p>
		<em>In general</em>, that is. A limited escape hatch exists:
	</p>
	<blockquote>
		<p>
			"an invariant type [...] allows you to map from <code>a</code> to <code>b</code> if and only if <code>a</code> and <code>b</code> are isomorphic. In a very real sense, this isn't an interesting property - an isomorphism between <code>a</code> and <code>b</code> means they're already the same thing to begin with."
		</p>
		<footer><cite><NAME>, <a href="https://thinkingwithtypes.com/">Thinking with Types</a></cite></footer>
	</blockquote>
	<p>
		In <a href="https://www.haskell.org/">Haskell</a> we may define an invariant functor (AKA <a href="http://comonad.com/reader/2008/rotten-bananas/">exponential functor</a>) as in the <a href="https://hackage.haskell.org/package/invariant">invariant</a> package:
	</p>
	<p>
		<pre><span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Invariant</span>&nbsp;f&nbsp;<span style="color:blue;">where</span>
&nbsp;&nbsp;<span style="color:#2b91af;">invmap</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;b</pre>
	</p>
	<p>
		This means that an <em>invariant functor</em> <code>f</code> is a container of values where a translation from <code>f a</code> to <code>f b</code> exists if it's possible to translate contained values both ways: From <code>a</code> to <code>b</code>, and from <code>b</code> to <code>a</code>. Callers of the <code>invmap</code> function must supply translations that go both ways.
	</p>
	<h3 id="36e114d8871c46c9addb2e38936a2872">
		Invariant functor in C# <a href="#36e114d8871c46c9addb2e38936a2872" title="permalink">#</a>
	</h3>
	<p>
		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 <a href="/2018/03/22/functors">functors</a> and <a href="/2022/03/28/monads">monads</a>, 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 <a href="/2018/12/24/bifunctors">bifunctors</a>, <a href="/2021/11/01/profunctors">profunctors</a>, 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 <code><span style="color:#2b91af;">Invariant</span>&lt;<span style="color:#2b91af;">A</span>&gt;</code>.
	</p>
	<p>
		Such a generic class must have a mapping function that corresponds to the above <code>invmap</code>. In C# it has this signature:
	</p>
	<p>
		<pre><span style="color:blue;">public</span>&nbsp;Invariant&lt;B&gt;&nbsp;<span style="color:#74531f;">InvMap</span>&lt;<span style="color:#2b91af;">B</span>&gt;(Func&lt;A,&nbsp;B&gt;&nbsp;<span style="color:#1f377f;">aToB</span>,&nbsp;Func&lt;B,&nbsp;A&gt;&nbsp;<span style="color:#1f377f;">bToA</span>)</pre>
	</p>
	<p>
		In this example, <code>InvMap</code> is an instance method on <code><span style="color:#2b91af;">Invariant</span>&lt;<span style="color:#2b91af;">A</span>&gt;</code>. You may use it like this:
	</p>
	<p>
		<pre>Invariant&lt;<span style="color:blue;">long</span>&gt;&nbsp;<span style="color:#1f377f;">il</span>&nbsp;=&nbsp;createInvariant();
Invariant&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">its</span>&nbsp;=&nbsp;il.InvMap(<span style="color:#1f377f;">l</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;TimeSpan(l),&nbsp;<span style="color:#1f377f;">ts</span>&nbsp;=&gt;&nbsp;ts.Ticks);</pre>
	</p>
	<p>
		It's not that easy to find good examples of truly isomorphic primitives, but <a href="https://docs.microsoft.com/dotnet/api/system.timespan">TimeSpan</a> is just a useful wrapper of <code>long</code>, so it's possible to translate back and forth without loss of information. To create a <code>TimeSpan</code> from a <code>long</code>, you can use the suitable constructor overload. To get a <code>long</code> from a <code>TimeSpan</code>, you can read the <a href="https://docs.microsoft.com/dotnet/api/system.timespan.ticks">Ticks</a> property.
	</p>
	<p>
		Perhaps you find a method name like <code>InvMap</code> non-idiomatic in C#. Perhaps a more <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> name might be <code>Select</code>? That's not a problem:
	</p>
	<p>
		<pre><span style="color:blue;">public</span>&nbsp;Invariant&lt;B&gt;&nbsp;<span style="color:#74531f;">Select</span>&lt;<span style="color:#2b91af;">B</span>&gt;(Func&lt;A,&nbsp;B&gt;&nbsp;<span style="color:#1f377f;">aToB</span>,&nbsp;Func&lt;B,&nbsp;A&gt;&nbsp;<span style="color:#1f377f;">bToA</span>)
{
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;InvMap(aToB,&nbsp;bToA);
}</pre>
	</p>
	<p>
		In that case, usage would look like this:
	</p>
	<p>
		<pre>Invariant&lt;<span style="color:blue;">long</span>&gt;&nbsp;<span style="color:#1f377f;">il</span>&nbsp;=&nbsp;createInvariant();
Invariant&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">its</span>&nbsp;=&nbsp;il.Select(<span style="color:#1f377f;">l</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;TimeSpan(l),&nbsp;<span style="color:#1f377f;">ts</span>&nbsp;=&gt;&nbsp;ts.Ticks);</pre>
	</p>
	<p>
		In this article, I'll use <code>Select</code> 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 <code>Select</code>.
	</p>
	<h3 id="4a5c0a55258d4e398931d2880df059fb">
		Laws <a href="#4a5c0a55258d4e398931d2880df059fb" title="permalink">#</a>
	</h3>
	<p>
		As is usual with these kinds of universal abstractions, an invariant functor must satisfy a few laws.
	</p>
	<p>
		The first one we might call the <em>identity law:</em>
	</p>
	<p>
		<pre>invmap id id = id</pre>
	</p>
	<p>
		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.
	</p>
	<p>
		In C# such a mapping might look like this:
	</p>
	<p>
		<pre><span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;i.Select(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x,&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x);</pre>
	</p>
	<p>
		The law then says that <code>actual</code> should be equal to <code>i</code>.
	</p>
	<p>
		The second law we might call the <em>composition law:</em>
	</p>
	<p>
		<pre>invmap f2 f2' . invmap f1 f1' = invmap (f2 . f1) (f1' . f2')</pre>
	</p>
	<p>
		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.
	</p>
	<p>
		In C# the left-hand side might look like this:
	</p>
	<p>
		<pre>Invariant&lt;IntPtr&gt;&nbsp;<span style="color:#1f377f;">left</span>&nbsp;=&nbsp;i.Select(f1,&nbsp;f1p).Select(f2,&nbsp;f2p);</pre>
	</p>
	<p>
		In C# you can't name functions or variables with a quotation mark (like the Haskell code's <code>f1'</code> and <code>f2'</code>), so instead I named them <code>f1p</code> and <code>f2p</code> (with a <em>p</em> for <em>prime</em>).
	</p>
	<p>
		Likewise, the right-hand side might look like this:
	</p>
	<p>
		<pre>Invariant&lt;IntPtr&gt;&nbsp;<span style="color:#1f377f;">right</span>&nbsp;=&nbsp;i.Select(<span style="color:#1f377f;">ts</span>&nbsp;=&gt;&nbsp;f2(f1(ts)),&nbsp;<span style="color:#1f377f;">ip</span>&nbsp;=&gt;&nbsp;f1p(f2p(ip)));</pre>
	</p>
	<p>
		The composition law says that the <code>left</code> and <code>right</code> values must be equal.
	</p>
	<p>
		You'll see some more detailed examples in later articles.
	</p>
	<h3 id="14c58dc57f9744dfbc955015d03b871e">
		Examples <a href="#14c58dc57f9744dfbc955015d03b871e" title="permalink">#</a>
	</h3>
	<p>
		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:
	</p>
	<ul>
		<li><a href="/2022/08/08/endomorphism-as-an-invariant-functor">Endomorphism as an invariant functor</a></li>
		<li><a href="/2022/08/29/natural-transformations-as-invariant-functors">Natural transformations as invariant functors</a></li>
		<li>Functors as invariant functors</li>
		<li>Contravariant functors as invariant functors</li>
	</ul>
	<p>
		As two of the titles suggest, all functors are also invariant functors, and the same goes for contravariant functors:
	</p>
	<p>
		<img src="/content/binary/invariant-functor-set-diagram.png" alt="Set diagram. The biggest set labelled invariant functos contains two other sets labelled functors and invariant functors.">
	</p>
	<p>
		To be honest, invariant functors are exotic, and you are unlikely to need them in all but the rarest cases. Still, I <em>did</em> run into a scenario where I needed an invariant functor instance to be able to perform <a href="/2022/09/05/the-state-pattern-and-the-state-monad">a particular sleight of hand</a>. The rabbit holes we sometimes fall into...
	</p>
	<h3 id="ffa0e597f09c40e7bcd1cabe808aa0d5">
		Conclusion <a href="#ffa0e597f09c40e7bcd1cabe808aa0d5" title="permalink">#</a>
	</h3>
	<p>
		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.
	</p>
	<strong>Next:</strong> <a href="/2022/08/08/endomorphism-as-an-invariant-functor">Endomorphism as an invariant functor</a>.
</div>

<div id="comments">
	<hr>
	<h2 id="comments-header">
		Comments
	</h2>
	<div class="comment" id="faae4a8cbe294be8ac7596488d675483">
		<div class="comment-author"><a href="https://about.me/tysonwilliams"><NAME></a></div>
		<div class="comment-content">
			<blockquote>
				For <a href="/2018/03/22/functors">functors</a> and <a href="/2022/03/28/monads">monads</a>, the C# compiler can perform 'compile-time duck typing' to recognise these motifs to enable query syntax.
			</blockquote>
			<p>
				Instead of 'compile-time duck typing', I think a better phrase to describe this is <a href="https://en.wikipedia.org/wiki/Structural_type_system">structural typing</a>.
			</p>
		</div>
		<div class="comment-date">2022-09-17 16:20 UTC</div>
	</div>
</div><commit_msg>Respond to comment<commit_after>---
layout: post
title: "Invariant functors"
description: "Containers that support mapping isomorphic values."
date: 2022-08-01 5:49 UTC
tags: [Software Design]
image: "/content/binary/invariant-functor-set-diagram.png"
image_alt: "Set diagram. The biggest set labelled invariant functos contains two other sets labelled functors and invariant functors."
---
{% include JB/setup %}

<div id="post">
	<p>
		<em>{{ page.description }}</em>
	</p>
	<p>
		This article series is part of <a href="/2018/03/19/functors-applicatives-and-friends">a larger series of articles about functors, applicatives, and other mappable containers</a>. So far, you've seen examples of both co- and <a href="/2021/09/02/contravariant-functors">contravariant functors</a>, including <a href="/2021/11/01/profunctors">profunctors</a>. You've also seen a few examples of <a href="/2020/10/19/monomorphic-functors">monomorphic functors</a> - mappable containers where there's no variance at all.
	</p>
	<p>
		What happens, on the other hand, if you have a container of (generic) values, but it's neither co- nor contravariant? An <a href="https://en.wikipedia.org/wiki/Endomorphism">endomorphism</a> is an example - it's neither co- nor contravariant. You'll see a treatment of that in a later article.
	</p>
	<p>
		Even if neither co- nor contravariant mappings exists for a container, all may not be lost. It may still be an <em>invariant functor</em>.
	</p>
	<h3 id="40d4c4a6deed4af593b3cf002563f085">
		Invariance <a href="#40d4c4a6deed4af593b3cf002563f085" title="permalink">#</a>
	</h3>
	<p>
		Consider a <a href="https://bartoszmilewski.com/2014/01/14/functors-are-containers">container</a> <code>f</code> (for <em>functor</em>). Depending on its variance, we call it <em>covariant</em>, <em>contravariant</em>, or <em>invariant</em>:
	</p>
	<ul>
		<li><em>Covariance</em> means that any function <code>a -&gt; b</code> can be lifted into a function <code>f a -&gt; f b</code>.</li>
		<li><em>Contravariance</em> means that any function <code>a -&gt; b</code> can be lifted into a function <code>f b -&gt; f a</code>.</li>
		<li><em>Invariance</em> means that in general, no function <code>a -&gt; b</code> can be lifted into a function over <code>f a</code>.</li>
	</ul>
	<p>
		<em>In general</em>, that is. A limited escape hatch exists:
	</p>
	<blockquote>
		<p>
			"an invariant type [...] allows you to map from <code>a</code> to <code>b</code> if and only if <code>a</code> and <code>b</code> are isomorphic. In a very real sense, this isn't an interesting property - an isomorphism between <code>a</code> and <code>b</code> means they're already the same thing to begin with."
		</p>
		<footer><cite><NAME>, <a href="https://thinkingwithtypes.com/">Thinking with Types</a></cite></footer>
	</blockquote>
	<p>
		In <a href="https://www.haskell.org/">Haskell</a> we may define an invariant functor (AKA <a href="http://comonad.com/reader/2008/rotten-bananas/">exponential functor</a>) as in the <a href="https://hackage.haskell.org/package/invariant">invariant</a> package:
	</p>
	<p>
		<pre><span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">Invariant</span>&nbsp;f&nbsp;<span style="color:blue;">where</span>
&nbsp;&nbsp;<span style="color:#2b91af;">invmap</span>&nbsp;::&nbsp;(a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;b)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(b&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;f&nbsp;b</pre>
	</p>
	<p>
		This means that an <em>invariant functor</em> <code>f</code> is a container of values where a translation from <code>f a</code> to <code>f b</code> exists if it's possible to translate contained values both ways: From <code>a</code> to <code>b</code>, and from <code>b</code> to <code>a</code>. Callers of the <code>invmap</code> function must supply translations that go both ways.
	</p>
	<h3 id="36e114d8871c46c9addb2e38936a2872">
		Invariant functor in C# <a href="#36e114d8871c46c9addb2e38936a2872" title="permalink">#</a>
	</h3>
	<p>
		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 <a href="/2018/03/22/functors">functors</a> and <a href="/2022/03/28/monads">monads</a>, 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 <a href="/2018/12/24/bifunctors">bifunctors</a>, <a href="/2021/11/01/profunctors">profunctors</a>, 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 <code><span style="color:#2b91af;">Invariant</span>&lt;<span style="color:#2b91af;">A</span>&gt;</code>.
	</p>
	<p>
		Such a generic class must have a mapping function that corresponds to the above <code>invmap</code>. In C# it has this signature:
	</p>
	<p>
		<pre><span style="color:blue;">public</span>&nbsp;Invariant&lt;B&gt;&nbsp;<span style="color:#74531f;">InvMap</span>&lt;<span style="color:#2b91af;">B</span>&gt;(Func&lt;A,&nbsp;B&gt;&nbsp;<span style="color:#1f377f;">aToB</span>,&nbsp;Func&lt;B,&nbsp;A&gt;&nbsp;<span style="color:#1f377f;">bToA</span>)</pre>
	</p>
	<p>
		In this example, <code>InvMap</code> is an instance method on <code><span style="color:#2b91af;">Invariant</span>&lt;<span style="color:#2b91af;">A</span>&gt;</code>. You may use it like this:
	</p>
	<p>
		<pre>Invariant&lt;<span style="color:blue;">long</span>&gt;&nbsp;<span style="color:#1f377f;">il</span>&nbsp;=&nbsp;createInvariant();
Invariant&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">its</span>&nbsp;=&nbsp;il.InvMap(<span style="color:#1f377f;">l</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;TimeSpan(l),&nbsp;<span style="color:#1f377f;">ts</span>&nbsp;=&gt;&nbsp;ts.Ticks);</pre>
	</p>
	<p>
		It's not that easy to find good examples of truly isomorphic primitives, but <a href="https://docs.microsoft.com/dotnet/api/system.timespan">TimeSpan</a> is just a useful wrapper of <code>long</code>, so it's possible to translate back and forth without loss of information. To create a <code>TimeSpan</code> from a <code>long</code>, you can use the suitable constructor overload. To get a <code>long</code> from a <code>TimeSpan</code>, you can read the <a href="https://docs.microsoft.com/dotnet/api/system.timespan.ticks">Ticks</a> property.
	</p>
	<p>
		Perhaps you find a method name like <code>InvMap</code> non-idiomatic in C#. Perhaps a more <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> name might be <code>Select</code>? That's not a problem:
	</p>
	<p>
		<pre><span style="color:blue;">public</span>&nbsp;Invariant&lt;B&gt;&nbsp;<span style="color:#74531f;">Select</span>&lt;<span style="color:#2b91af;">B</span>&gt;(Func&lt;A,&nbsp;B&gt;&nbsp;<span style="color:#1f377f;">aToB</span>,&nbsp;Func&lt;B,&nbsp;A&gt;&nbsp;<span style="color:#1f377f;">bToA</span>)
{
&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#8f08c4;">return</span>&nbsp;InvMap(aToB,&nbsp;bToA);
}</pre>
	</p>
	<p>
		In that case, usage would look like this:
	</p>
	<p>
		<pre>Invariant&lt;<span style="color:blue;">long</span>&gt;&nbsp;<span style="color:#1f377f;">il</span>&nbsp;=&nbsp;createInvariant();
Invariant&lt;TimeSpan&gt;&nbsp;<span style="color:#1f377f;">its</span>&nbsp;=&nbsp;il.Select(<span style="color:#1f377f;">l</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;TimeSpan(l),&nbsp;<span style="color:#1f377f;">ts</span>&nbsp;=&gt;&nbsp;ts.Ticks);</pre>
	</p>
	<p>
		In this article, I'll use <code>Select</code> 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 <code>Select</code>.
	</p>
	<h3 id="4a5c0a55258d4e398931d2880df059fb">
		Laws <a href="#4a5c0a55258d4e398931d2880df059fb" title="permalink">#</a>
	</h3>
	<p>
		As is usual with these kinds of universal abstractions, an invariant functor must satisfy a few laws.
	</p>
	<p>
		The first one we might call the <em>identity law:</em>
	</p>
	<p>
		<pre>invmap id id = id</pre>
	</p>
	<p>
		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.
	</p>
	<p>
		In C# such a mapping might look like this:
	</p>
	<p>
		<pre><span style="color:blue;">var</span>&nbsp;<span style="color:#1f377f;">actual</span>&nbsp;=&nbsp;i.Select(<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x,&nbsp;<span style="color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;x);</pre>
	</p>
	<p>
		The law then says that <code>actual</code> should be equal to <code>i</code>.
	</p>
	<p>
		The second law we might call the <em>composition law:</em>
	</p>
	<p>
		<pre>invmap f2 f2' . invmap f1 f1' = invmap (f2 . f1) (f1' . f2')</pre>
	</p>
	<p>
		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.
	</p>
	<p>
		In C# the left-hand side might look like this:
	</p>
	<p>
		<pre>Invariant&lt;IntPtr&gt;&nbsp;<span style="color:#1f377f;">left</span>&nbsp;=&nbsp;i.Select(f1,&nbsp;f1p).Select(f2,&nbsp;f2p);</pre>
	</p>
	<p>
		In C# you can't name functions or variables with a quotation mark (like the Haskell code's <code>f1'</code> and <code>f2'</code>), so instead I named them <code>f1p</code> and <code>f2p</code> (with a <em>p</em> for <em>prime</em>).
	</p>
	<p>
		Likewise, the right-hand side might look like this:
	</p>
	<p>
		<pre>Invariant&lt;IntPtr&gt;&nbsp;<span style="color:#1f377f;">right</span>&nbsp;=&nbsp;i.Select(<span style="color:#1f377f;">ts</span>&nbsp;=&gt;&nbsp;f2(f1(ts)),&nbsp;<span style="color:#1f377f;">ip</span>&nbsp;=&gt;&nbsp;f1p(f2p(ip)));</pre>
	</p>
	<p>
		The composition law says that the <code>left</code> and <code>right</code> values must be equal.
	</p>
	<p>
		You'll see some more detailed examples in later articles.
	</p>
	<h3 id="14c58dc57f9744dfbc955015d03b871e">
		Examples <a href="#14c58dc57f9744dfbc955015d03b871e" title="permalink">#</a>
	</h3>
	<p>
		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:
	</p>
	<ul>
		<li><a href="/2022/08/08/endomorphism-as-an-invariant-functor">Endomorphism as an invariant functor</a></li>
		<li><a href="/2022/08/29/natural-transformations-as-invariant-functors">Natural transformations as invariant functors</a></li>
		<li>Functors as invariant functors</li>
		<li>Contravariant functors as invariant functors</li>
	</ul>
	<p>
		As two of the titles suggest, all functors are also invariant functors, and the same goes for contravariant functors:
	</p>
	<p>
		<img src="/content/binary/invariant-functor-set-diagram.png" alt="Set diagram. The biggest set labelled invariant functos contains two other sets labelled functors and invariant functors.">
	</p>
	<p>
		To be honest, invariant functors are exotic, and you are unlikely to need them in all but the rarest cases. Still, I <em>did</em> run into a scenario where I needed an invariant functor instance to be able to perform <a href="/2022/09/05/the-state-pattern-and-the-state-monad">a particular sleight of hand</a>. The rabbit holes we sometimes fall into...
	</p>
	<h3 id="ffa0e597f09c40e7bcd1cabe808aa0d5">
		Conclusion <a href="#ffa0e597f09c40e7bcd1cabe808aa0d5" title="permalink">#</a>
	</h3>
	<p>
		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.
	</p>
	<strong>Next:</strong> <a href="/2022/08/08/endomorphism-as-an-invariant-functor">Endomorphism as an invariant functor</a>.
</div>

<div id="comments">
	<hr>
	<h2 id="comments-header">
		Comments
	</h2>
	<div class="comment" id="faae4a8cbe294be8ac7596488d675483">
		<div class="comment-author"><a href="https://about.me/tysonwilliams"><NAME></a></div>
		<div class="comment-content">
			<blockquote>
				For <a href="/2018/03/22/functors">functors</a> and <a href="/2022/03/28/monads">monads</a>, the C# compiler can perform 'compile-time duck typing' to recognise these motifs to enable query syntax.
			</blockquote>
			<p>
				Instead of 'compile-time duck typing', I think a better phrase to describe this is <a href="https://en.wikipedia.org/wiki/Structural_type_system">structural typing</a>.
			</p>
		</div>
		<div class="comment-date">2022-09-17 16:20 UTC</div>
	</div>

	<div class="comment" id="98be00b677484b11a51d8e583c25baa5">
		<div class="comment-author"><a href="{{ HOME_PATH }}"><NAME></a></div>
		<div class="comment-content">
			<p>
				Tyson, thank you for writing. I wasn't aware of the term <em>structural typing</em>, 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 <a href="https://fsharp.org">F#</a>'s <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/generics/statically-resolved-type-parameters">Statically Resolved Type Parameters</a> are another example of structural typing, in addition to the <a href="https://ocaml.org/">OCaml</a> example given in the article.
			</p>
			<p>
				IIRC, <a href="https://www.purescript.org/">PureScript</a>'s <em>row polymorphism</em> may be another example, but it's been many years since <a href="/2017/06/06/fractal-trees-with-purescript">I played with it</a>. In other words, I could be mistaken.
			</p>
			<p>
				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.
			</p>
			<p>
				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.
			</p>
		</div>
		<div class="comment-date">2022-09-19 14:46 UTC</div>
  	</div>
</div>
{'fraction_non_alphanumeric': 0.17143781917571746, 'fraction_numerical': 0.03873264763000791, 'mean_word_length': 5.2572007200720074, 'pattern_counts': {'":': 0, '<': 892, '<?xml version=': 0, '>': 892, 'https://': 22, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1998568', 'n_tokens_mistral': 10917, 'n_tokens_neox': 9670, 'n_words': 2812}