<blockquote>
  <p>What profunctors lack compared to arrows is the ability to compose them. If we add composition, will we get an arrow?</p>
</blockquote>

<h2>MONOIDS</h2>

<p>This is exactly the question tackled in section 6 of "<a href="http://arxiv.org/pdf/1406.4823.pdf" rel="noreferrer">Notions of Computation as Monoids</a>," which unpacks a result from the (rather dense) "<a href="http://homepages.inf.ed.ac.uk/cheunen/publications/2008/arrows/arrows.pdf" rel="noreferrer">Categorical semantics for arrows</a>". "Notions" is a great paper because while it dives deep into category theory it (1) doesn't assume the reader has more than a cursory knowledge of abstract algebra and (2) illustrates most of the migraine-inducing mathematics with Haskell code. We can briefly summarize section 6 of the paper here:</p>

<p>Say we have</p>

<pre><code>class Profunctor p where
  dimap :: (contra' -&gt; contra) -&gt; (co -&gt; co') -&gt; p contra co -&gt; p contra' co'
</code></pre>

<p>Your bog-standard, negative-and-positive dividin' encoding of profunctors in Haskell. Now this data type,</p>

<pre><code>data (⊗) f g contra co = forall x. (f contra x) ⊗ (g x co)
</code></pre>

<p>as implemented in <a href="https://hackage.haskell.org/package/profunctors-5.2/docs/Data-Profunctor-Composition.html" rel="noreferrer">Data.Profunctor.Composition</a>, acts like composition for profunctor. We can, for example, demonstrate a lawful instance <code>Profunctor</code>:</p>

<pre><code>instance (Profunctor f, Profunctor g) =&gt; Profunctor (f ⊗ g) where
  dimap contra co (f ⊗ g) = (dimap contra id f) ⊗ (dimap id co g)
</code></pre>

<p>We will hand-wave the proof that it is lawful for reasons of time and space.</p>

<p>OK. Now the fun part. Say we this typeclass:</p>

<pre><code>class Profunctor p =&gt; ProfunctorMonoid p where
  e :: (a -&gt; b) -&gt; p a b
  m :: (p ⊗ p) a b -&gt; p a b
</code></pre>

<p>This is, with a lot more hand-waving, a way of encoding the notion of profunctor monoids in Haskell. Specifically this is a monoid in the monoidal category <code>Pro</code>, which is a monoidal structure for the functor category <code>[C^op x C, Set]</code> with <code>⊗</code> as the tensor and <code>Hom</code> as its unit. So there's a lot of ultraspecific mathematical diction to unpack here but for that you should just read the paper.</p>

<p>We then see that <code>ProfunctorMonoid</code> is isomorphic to <code>Arrow</code> ... almost.</p>

<pre><code>instance ProfunctorMonoid p =&gt; Category p where
  id = dimap id id
  (.) pbc pab = m (pab ⊗ pbc)

instance ProfunctorMonoid p =&gt; Arrow p where
  arr = e
  first = undefined

instance Arrow p =&gt; Profunctor p where
  lmap = (^&gt;&gt;)
  rmap = (&gt;&gt;^)

instance Arrow p =&gt; ProfunctorMonoid p where
  e = arr
  m (pax ⊗ pxb) = pax &gt;&gt; pxb
</code></pre>

<p>Of course we are ignoring the typeclass laws here but, as the paper shows, they do work out fantastically.</p>

<p>Now I said almost because crucially we were unable to implement <code>first</code>. What we have really done is demonstrated an isomorphism between <code>ProfunctorMonoid</code> and <em>pre-arrows</em> .The paper calls <code>Arrow</code> without <code>first</code> a <em>pre-arrow</em>. It then goes on to show that</p>

<pre><code>class Profunctor p =&gt; StrongProfunctor p where
  first :: p x y -&gt; p (x, z) (y, z)

class StrongProfunctor p =&gt; StrongProfunctorMonoid p where
  e :: (a -&gt; b) -&gt; p a b
  m :: (p ⊗ p) a b -&gt; p a b
</code></pre>

<p>is necessary and sufficient for the desired isomorphism to <code>Arrow</code>. The word "strong" comes from a specific notion in category theory and is described by the paper in better writing and richer detail than I could ever muster.</p>

<p>So to summarize:</p>

<ul>
<li><p>A monoid in the category of profunctors is a pre-arrow, and vice versa. (A previous version of the paper used the term "weak arrows" instead of pre-arrows, and that's OK too I guess.)</p></li>
<li><p>A monoid in the category of strong profunctors is an arrow, and vice versa.</p></li>
<li><p>Since monad is a monoid in the category of endofunctors we can think of the SAT analogy <code>Functor : Profunctor :: Monad : Arrow</code>. This is the real thrust of the notions-of-computation-as-monoids paper.</p></li>
<li><p>Monoids and monoidal categories are gentle sea creatures that appear everywhere, and it's a shame that some students will go through computer science or software engineering education without being taught monoids.</p></li>
<li><p>Category theory is fun.</p></li>
<li><p>Haskell is fun.</p></li>
</ul>
What's the relationship between profunctors and arrows?
<p>Apparently, every <code>Arrow</code> is a <a href="https://hackage.haskell.org/package/profunctors-4.3.2/docs/Data-Profunctor.html#t:Strong" rel="noreferrer"><code>Strong</code></a> profunctor. Indeed <a href="https://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Arrow.html#v:-94--62--62-" rel="noreferrer"><code>^&gt;&gt;</code></a> and <code>&gt;&gt;^</code> correspond to <code>lmap</code> and <code>rmap</code>. And <code>first'</code> and <code>second'</code> are just the same as <code>first</code> and <code>second</code>. Similarly every <code>ArrowChoice</code> is also <a href="https://hackage.haskell.org/package/profunctors-4.3.2/docs/Data-Profunctor.html#t:Choice" rel="noreferrer"><code>Choice</code></a>.</p>

<p>What profunctors lack compared to arrows is the ability to compose them. If we add composition, will we get an arrow? In other words, if a (strong) profunctor is also a <a href="https://hackage.haskell.org/package/base-4.9.0.0/docs/Control-Category.html#t:Category" rel="noreferrer">category</a>, is it already an arrow? If not, what's missing?</p>