Learning Category Theory with Rust

Introduction

Category theory is difficult. Or at least so I thought. And, admittedly, still think. I never formally took a course in it. To dispel my impression of category theory as an unapproachable and terrifyingly abstract subject, I decided to read the Category Theory book by Bartosz Milewski.

The book is located here.

It's an excellent resource with very good explanations and examples. It makes me look at programming very differently.

My interest started with two things:

1. I don't like to leave topics of interest unaddressed
2. At some point I went down the rabbit hole of reading about monads.

There is probably a bit of contribution from reading a book called "Learn Physics with Functional Programming" by Scott N. Walck. This book goes through physics via Haskell language examples.

Thus a combination of factors led me to finally dip my toes into category theory.

Some Assumptions

Here I do assume that these notions are familiar (with brief explanation informally provided here):

• Category (essentially a set of objects and mappings between them)
• Morphism (the aforementioned mapping between objects of a category)
• a coproduct (an object into which other objects of the category are "injected" into via special morphisms)

More on Coproducts

In a category \(C\), a coproduct or sum of two object \(A\) and \(B\) is an object \(A+B\) equipped with two morphisms \(f_1\) and \(f_2\). These morphisms must satisfy the fact that for any object \(X\) out of \(C\) and any two morphisms \(p:\,A\rightarrow X\) and \(q:\,B\rightarrow X\), there exists a unique morphism \([p,q]\) where

• \([p, q] \circ f_1 = p\)
• \([p, q] \circ f_2 = q\)

In Haskell, there is a datatype called Either which encapsulates exactly the notion of a coproduct.

In Haskell it is defined as follows (from the docs):

The Either type represents values with two possibilities: a value of type Either a b is either Left a or Right b.

The Either type is sometimes used to represent a value which is either correct or an error; by convention, the Left constructor is used to hold an error value and the Right constructor is used to hold a correct value (mnemonic: "right" also means "correct").

A particular function I wanted to implement was the namesake of the datatype:

either :: (a -> c) -> (b -> c) -> Either a b -> c

Notice how objects of types a and b are both mapped into c, essentially injected into the type. That is, Either accepts two mappings (morphisms) and returns appropriate result of type c (the type to which both morphisms lead).

Implementation in Rust

We start with a datatype. In Rust, we will create an enum object like so:

#[derive(Debug, Clone, PartialEq)]
enum Either<L, R> {
    Left(L),
    Right(R),
}

This object will designate input of type L as Left and input of type R as Right, where L and R are generic.

Now let's try and build the either function:

impl<L, R> Either<L,R>{
  // implementation block

  // constructors
  fn left(value: L) -> Either<L, R> {
      Either::Left(value)
  }

  fn right(value: R) -> Either<L, R> {
      Either::Right(value)
  }

  // the `either` function
  fn either<F1, F2, C>(self, f1: F1, f2: F2) -> C
    where
        F1: FnOnce(L) -> C, // morphism 1
        F2: FnOnce(R) -> C, // morphism 2
      {
          match self {
              Either::Left(value) => f1(value),
              Either::Right(value) => f2(value),
          }
      }
  }

This function does the following: given two morphisms (Rust-defined functions) one mapping from L to C the other from R to C, it decides which one to call by matching and deciding if the current value is left or right.

Here it is being used:

fn double(x: i32) -> i32 {
  // our morphism number 1
  // mapping a 32 bit integer to a 32 bit integer
  2 * x
}
fn str_len(x: String) -> i32 {
  // the second morphism
  // which maps a String object to a 32 bit integer
  x.len() as i32
}
fn main() {
  let left_val: Either<i32, String> = Either::left(42);
  let right_val: Either<i32, String> = Either::right("Hello".to_string());
  let result_1 = left_val.either(double, str_len);
  let result_2 = right_val.either(double, str_len);
  println!("{result_1}"); // results in 84 as the value is `left`
  println!("{result_2}"); // results in 5 as the value is `right`
}

Conclusion

We partially implemented the type of Either and its method either based on their definition in Haskell and their category theoretical background.

This concept is important in everyday programming and we use it quite often even when we don't think about it as coproduct.

As mentioned in Haskell docs, we can use it for error handling. In Python, for example:

def safe_divide(x: float, y: float) -> float | str: # py3.10+
    if y == 0:
        return "Error: Division by zero"  # Left case
    else:
        return x / y  # Right case

Rust has Result<T, E> type, which can do this error handling for us and is using essentially the same concept.

Hopefully, after reading this you will notice similar patterns in your or someone else's code. I know that as I am reading through the book, I am noticing these little nitpicks here and there in my code which can be explained via category theory.

Happy coding!