From page 29 of The algebra of programming :

For any category C the opposite category $C^{op}$ is defined to have the same objects and arrows as C, but the source and target operators are interchanged and composition is defined by swapping arguments:

$$ f \cdot g \text{ in } C^{op} = g \cdot f \text{ in } C. $$

This doesn't makes sense. Suppose C is the categories of all functions, and we have $f: A \leftarrow B$ and $g: B \leftarrow C$, then $g \cdot f$ doesn't even exist. Or, suppose $f: A \leftarrow B$ and $g: B \leftarrow A$, then $f \cdot g : A \leftarrow A$, and $g \cdot f : B \leftarrow B$, this is not interchanging source and target, this is changing both!

  • $\begingroup$ Your arrows are backwards compared to what would normally be written, do you mean \rightarrow: $\rightarrow$? $\endgroup$ Mar 8 '15 at 0:26
  • $\begingroup$ The author of that book insists that it should be this way. I tend to agree with him. $\endgroup$
    – qed
    Mar 8 '15 at 0:30
  • 1
    $\begingroup$ Fair enough. I'll switch to this format for this question :). $\endgroup$ Mar 8 '15 at 0:34

The problem in your first example is that the arrows don't compose. In the first, you have $f: A \leftarrow B$ and $g: C \leftarrow B$, so $f\circ g$ is not in $C$, hence in $C^{op}$ $f : B \leftarrow A$ and $g : B \leftarrow C$, and they still don't compose.

If you had $f: A \leftarrow B$ and $g: B \leftarrow C$, then they compose to $f\circ g =h : A \leftarrow C$ in $C$. In $C^{op}$ you have $f : B \leftarrow A$ and $g : C \leftarrow B$ and get $g\circ f = h : C \leftarrow A$ (remember in $C^{op}$ you want every thing running backwards) .

Your second example is fine, you just have $f : A \leftarrow B$ and $g : B \leftarrow A$ in $C$ and hence $f\circ g : A\leftarrow A$ and $g\circ f:B\leftarrow B$ in $C$. In $C^{op}$, they switch: $f :B \leftarrow A$, $g : A \leftarrow B$ are in $C^{op}$ and so are $g \circ f : A \leftarrow A$ and $f\circ g : B\leftarrow B$.

I wonder perhaps if the phrasing used by Bird is causing a problem. The rule is better stated:

If $h = g \circ f$ in $C$ , then $h = f \circ g$ in $C^{op}$.

There's also a kind of name overloading going on here, from a programmer's perspective, reusing the same names for the opposite versions is a bit odd, it might make more sense to think along the lines (restating one of the rules):

If $f : X \leftarrow Y$ is in $C$, then $f^{op} : Y \leftarrow X$ is in $C^{op}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.