Category Theory: Types and Functions

In my last post on Category Theory, I summarized the main ideas from Chapter 1 of Category Theory for Programmers by Bartosz Milewski. In this post I’m moving on to Chapter 2: Types and Functions.

Category Theory is about composing arrows (or rather functions/morphisms), but to be able to compose any two arrows/functions their head and tail must match. This just means that the output of one function must have a type that matches the input of the next function.

Types and Sets

But what do we mean by “types” in the first place? I’ve worked with computers for years and the thought never occurred to me that a “type” is really a set. Think of type int/integer in whatever is your favorite programming language. It represents the set of positive and negative integers, though often with upper and lower bounds so that the compiler can assume a certain number of bytes. However, many modern languages put no limits on how large or small an integer might be. (Python and Haskell allow for any sized integer.)

Category Theory has a “category of sets,” which is called 𝐒𝐞𝐭. In 𝐒𝐞𝐭, objects are sets and morphisms (arrows) are functions. (p. 15) Functions (arrows) therefore map elements of one set to elements of another set. F.unctions can map two elements in a set to one element in another, but never one element to two. An identity function maps each element of a set to itself.

Pure Functions

“Functions” in most programming languages don’t map well to the mathematical idea of a function. A mathematical function just maps values to values, so they have a single input and a single output. (Note: Haskell actually only has functions mapping a single input to a single output, but then has clever syntactic sugar to hide this fact.) Mathematical functions also never have any ‘side effects’ which is (in a programming function) where the function does something other than just return a value. This might be something like setting a global variable or printing to the console screen.

Side effects can have a nasty downside when it comes to the readability of the code. For example, imagine a function that uses and then updates a global variable. That function will not always give the same output for a given input.

Pure Functions are functions that “always produce the same result given the same input and [has] no side effects” (p. 20)

One special term for a special type of pure function is a predicate which is a function that returns a boolean value. (Think isAlpha)

Chapter 2 wasn’t the most useful, and this is all I managed to take away from it that was directly related to category theory.

Leave a Reply

Your email address will not be published. Required fields are marked *