Exploring Category Theory with Haskell: Challenge Problem

Posted on 2009-10-22 by Travis Cardwell :: comments enabled

Here’s a little challenge to try before the presentation on October 29th. For those of you who have studied category theory, it will be very simple, but it should be more fun for the rest of you. All you need to solve the challenge is your mind, though a pencil and paper may help.

During my presentation I will give a whiteboard overview of introductory category theory as applied to finite sets. I will then present the Haskell code that I wrote, along with the solution to the challenge problem.1

The Problem

How many idempotent endomaps exist for any finite set of a given size?

In not-so-mathematical terms, find the number of functions from a given finite set to itself where f(x) == f(f(x)). Your answer should be an equation with the size of the finite set as the parameter.

For example, consider a finite set A of 2 elements {1,2}. There are four functions
f :: A -> A as follows:

f1(1) = 1,  f1(2) = 1
f2(1) = 1,  f2(2) = 2
f3(1) = 2,  f3(2) = 1
f4(1) = 2,  f4(2) = 2

By calculation, you can determine that functions f1, f2, and f4 satisfy the relation f(x) == f(f(x)); the number of idempotent endomaps for any finite set of two elements is 3. The challenge is to find an equation to determine this for a finite set of any size.

  1. Please note that while the code that I will present was fun to write, it is neither impressive nor particularly useful for anything but exploring category theory as applied to finite sets. The process of writing the code is what helps learn, of course, so anybody interested in learning and exploring category theory in a similar manner should write their own. ;)

Add a comment »
comments are moderated