1
$\begingroup$

When I'm writing out categories of my Haskell programs, I often get stuck whilst trying to describe morphisms that involve functions that involve more than one argument, such as 2-tuple construction.

For instance, I may have a function ${\lambda a.\lambda b.\left<a,b\right> }$. I have an object ${A}$, and I apply the function as a morphism, returning (essentially) ${\lambda b.\left<a \in A, b\right>}$, which in Haskell, is a type, and therefore an object. The problem is, how can I then use that as a morphism? Is there another representation for morphisms in this pattern?

My question is, how can I describe morphisms which require two arguments, such as 2-tuples, in a category?

$\endgroup$
  • $\begingroup$ Could you give an example of where you get stuck? $\endgroup$ – Calle Apr 12 '15 at 12:00
  • $\begingroup$ @Calle Added, I hope it helps. $\endgroup$ – AJFarmar Apr 12 '15 at 12:06
  • $\begingroup$ So you have f : a -> b -> (a,b) and then apply f (x:a)? $\endgroup$ – Calle Apr 12 '15 at 12:22
  • $\begingroup$ That's pretty much it. $\endgroup$ – AJFarmar Apr 12 '15 at 12:29
  • $\begingroup$ You can either use products (which is the usual way) or exponential objects (which corresponds to curried functions). $\endgroup$ – Zhen Lin Apr 12 '15 at 14:04
4
$\begingroup$

I'm not sure what exactly you are asking, but your function $λa. λb. (a, b)$ is an element of type $a → (b → a × b)$, or more conventionally $((a × b)^b)^a$. If you apply it to a specific $a ∈ A$, you get an element of type $b → a × b$, which is a function from $b$ to $a × b$.

In categorical language, this is the setting of a cartesian closed category, which are characterized by having finite products, and a functor $[-, -] : \mathscr C^\mathrm{op} × \mathscr C → \mathscr C$ such that $\hom(A × B, C) ≅ \hom(A, [B, C])$ holds naturally in $A$, $B$ and $C$. In the category of sets, which is cartesian closed, $[A, B]$ is of course $B^A$, the set of all functions from $A$ to $B$, and in Haskell, $[a, b] = (a → b)$. The bijection $\hom(A × B, C) ≅ \hom(A, [B, C])$ (currying) is a very strong condition, and it enables us to interpret $[A, B]$ as an object of morphisms from $A$ to $B$ even in general cartesian closed categories. Note for example that we have $\hom(A, B) ≅ \hom(1 × A, B) ≅ \hom(1, [A, B])$, where $1$ is the terminal object of $\mathscr C$, so morphisms from $A$ to $B$ are in bijection with morphisms from $1$ to $[A, B]$, so $[A, B]$ itself "knows" what $\hom(A, B)$ is. More generally, you can do this in any monoidally closed category.

In fact, the notion of a morphism of multiple arguments makes sense in any monoidal category $(\mathscr C, ⊗, I)$. You can call a morphism $A ⊗ B → C$ a "morphism with two arguments", and you can "partially apply" these too in a sense, but you loose "objects of morphisms" ie. what corresponds to Haskell's function types, and with it the evaluation morphism $\mathrm{ev} : [A, B] ⊗ A → B$, you have in monoidally closed categories, and finally the ability to convert functions of multiple arguments into functions of a single argument.

$\endgroup$

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.