<p>Let me quote the setoids subsection (sect. 2.4) from a paper by J. Gross, A. Chlipala, D.I. Spivak -- <a href="https://arxiv.org/pdf/1401.7694.pdf" rel="nofollow noreferrer">Experience Implementing a Performant Category-Theory Library in Coq</a> (2014):</p>

<blockquote>
  <p>A setoid [5] is a carrier type equipped with an equivalence relation; a map of setoids is a function between the carrier types and a proof that the function respects the equivalence relations of its domain and codomain. Many authors [11, 12, 15, 18] choose to use a <strong>setoid of morphisms</strong>, which allows for the definition of the category of set(oid)s, as well as the category of (small) categories, without assuming functional extensionality, and allows for the definition of categories where the objects are quotient types.</p>
</blockquote>

<p>The source the above is referring to as [12] is the Math-Classes library.
However, then the authors proceed with a caveat:</p>

<blockquote>
  <p>However, there is significant overhead associated with using setoids everywhere, which can lead to slower compile times. Every type that we talk about needs to come with a relation and a proof that this relation is an equivalence relation. Every function that we use needs to come with a proof that it sends equivalent elements to equivalent elements. Even worse, if we need an equivalence relation on the universe of “types with equivalence relations,” we need to provide a transport function between equivalent types that respects the equivalence relations of those types.</p>
</blockquote>
How to understand Setoid definition of category?
<p>I am having trouble understanding the following Coq definition of Categories  (defined <a href="https://github.com/math-classes/math-classes/blob/v8.5/interfaces/abstract_algebra.v" rel="nofollow noreferrer">here</a>), which involves <code>Setoid</code>. And I don't understand why <code>Setoid</code> is necessary or its role here. </p>

<pre><code>Class Category O `{!Arrows O} `{∀ x y: O, Equiv (x ⟶ y)}
 `{!CatId O} `{!CatComp O}: Prop :=
  { arrow_equiv :&gt; ∀ x y, Setoid (x ⟶ y)
  ; comp_proper :&gt; ∀ x y z, Proper ((=) ==&gt; (=) ==&gt; (=)) (comp x y z)
  ; comp_assoc :&gt; ArrowsAssociative O
  ; id_l :&gt; ∀ x y, LeftIdentity (comp x y y) cat_id
  ; id_r :&gt; ∀ x y, RightIdentity (comp x x y) cat_id }.
      (* note: no equality on objects. *)
</code></pre>

<p>The basic notion of Categories I learned so far only requires that </p>

<ol>
<li>there are arrows between objects, </li>
<li>the arrows compose (respects associativity) and </li>
<li>identity arrows exist and behave.</li>
</ol>

<p>I understand that Setoid is about equivalent classes, but I can't see where Setoids come in. Can someone please help explain the definition above and explain the difference from the usual category definition without Setoids? </p>