Home

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.


Read more
Add a comment »
comments are moderated