Category Theory with Rust (pt1)

As a pedagogical exercise, I am following Bartosz Milewski's Category Theory for Programmers. These blog posts apply the challenges in Rust. The order comes from the challenges and can jump around a little.

The identity function

The identity function is simply defined:

fn id<T>(x: T) -> T { x }

This is the same as in std::convert::identity, less the const specifier.

Function composition

Implementing function composition requires a decision on the bounding constraints. There are four available options: fn, FnOnce, Fn, and FnMut. We can rule out FnOnce, we want a composition that returns a function that can be repeatedly called. fn would restrict us to free functions, but having support for closures would be nice. A final constraint is to avoid mutability. This is not strictly necessary, but a nice to have to keep the functions as pure as possible.

So composition would look like:

fn compose<F, G, A, B, C>(f: F, g: G) -> impl Fn(A) -> C
where
    F: Fn(A) -> B,
    G: Fn(B) -> C,
{
    move |a| g(f(a))
}

We can test the composition, and also test how the identity function works.

#[test]
fn compose_test() {
    let append_count = compose(|s| s + " world!", |s: String| s.len());
    assert_eq!(append_count(String::from("Hello")), "Hello world!".len());
    assert_eq!(append_count(String::from("👋")), "👋 world!".len());

    let f = compose(|i| i + 2, id);
    assert_eq!(f(2), 4);
    assert_eq!(f(0), 2);
    assert_eq!(compose(id, |i| i + 2)(2), 4);
}

Representing bool as a Monoid

Using bool with both && (AND) and || (OR) are trivally associative. However, the neutral element is a little more subtle:

#[test]
fn bool_logical_monoids() {
    let and_neutral = true; // the AND neutral element is a true!
    assert_eq!(true && and_neutral, true);
    assert_eq!(false && and_neutral, false);

    let or_neutral = false; // the OR neutral element is a false
    assert_eq!(true || or_neutral, true);
    assert_eq!(false || or_neutral, false);
}

We could implement the AND operator category for bool like so:

// AND operator category
impl Monoid for bool {
    fn mempty() -> Self {
        true
    }

    fn mappend(self, b: Self) -> Self {
        self && b
    }
}

Implementing Kleisli category for optional types

The Kleisli category is one based on a monad. For this example, we'll implement the Kleisli category on an optional type (we will use Rust's Option type, but implement the functions ourselves).

First up, let us define the identity and composition:

fn option_id<T>(x: T) -> Option<T> {
    Some(x)
}

fn option_compose<F, G, A, B, C>(f: F, g: G) -> impl Fn(A) -> Option<C>
where
    F: Fn(A) -> Option<B>,
    G: Fn(B) -> Option<C>,
{
    move |a| match f(a) {
        Some(b) => g(b),
        None => None,
    }
    // this should be able to be written as
    // move |a| f(a).and_then(g)
    // but the compiler requires `g` to be `Copy`!
    // EDIT
    // Thanks to Caleb Sanders for pointing this out
    // (notice the borrow):
    // move |a| f(a).and_then(&g)
}

Now let's see it in action:

fn safe_reciprocal(x: f32) -> Option<f32> {
    (x != 0.).then(|| 1.0 / x)
}

fn safe_root(x: f32) -> Option<f32> {
    (x >= 0.).then(|| x.sqrt())
}

#[test]
fn compose_root_reciprocal() {
    let safe_root_reciprocal = option_compose(safe_reciprocal, safe_root);

    assert_eq!(safe_root_reciprocal(0.), None);
    assert_eq!(safe_root_reciprocal(-0.1), None);
    assert_eq!(safe_root_reciprocal(0.01), Some(10.));
}

Algebraic Data Types

Rust makes this easy, enum's are Sum types, whilst struct's are Product types.

Implementing Either

Implementing Either is simply a sum type generic over the left (A) or right (B) branches. Breaking with convention, I have used L and R type placeholders.

enum Either<L, R> {
    Left(L),
    Right(R)
}

Implementing Shape area with traits

The Shape type is implemented in Haskell as:

data Shape = Circle Float | Rect Float Float

First, lets define a function area as a trait implementing on independent structs.

trait Area {
    fn area(&self) -> f64;
}

struct Circle(f64);

impl Area for Circle {
    fn area(&self) -> f64 {
        self.0.powi(2) * f64::PI
    }
}

struct Rect(f64, f64);

impl Area for Rect {
    fn area(&self) -> f64 {
        self.0 * self.1
    }
}

This is constrasted with using a sum type:

enum Shape {
    Circle(f64),
    Rect(f64, f64)
}

impl Shape {
    fn area(&self) -> f64 {
        match self {
            Shape::Circle(r) => r.powi(2) * f64::PI,
            Shape::Rect(w, h) => w * h
        }
    }
}

Now another function is required, circumference, using the trait method:

trait Circ {
    fn circ(&self) -> f64;
}

impl Circ for Circle {
    fn circ(&self) -> f64 {
        2. * self.0 * f64::PI
    }
}

impl Circ for Rect {
    fn area(&self) -> f64 {
        (self.0 + self.1) * 2.
    }
}

While the sum type is a single function definition:

impl Shape {
    fn circ(&self) -> f64 {
        match self {
            Shape::Circle(r) => r * 2. * f64::PI,
            Shape::Rect(w, h) => (w + h) * 2.
        }
    }
}

Adding another variant (Square):

struct Square(f64);

impl Area for Square {
    fn area(&self) -> f64 {
        self.0.powi(2)
    }
}

impl Circ for Square {
    fn circ(&self) -> f64 {
        self.0 * 4
    }
}

// vs

enum Shape {
    Circle(f64),
    Rect(f64, f64),
    Square(f64)
}

impl Shape {
    fn area(&self) -> f64 {
        match self {
            Shape::Circle(r) => r.powi(2) * f64::PI,
            Shape::Rect(w, h) => w * h,
            Shape::Square(s) => s.powi(2),
        }
    }

    fn circ(&self) -> f64 {
        match self {
            Shape::Circle(r) => r * 2. * f64::PI,
            Shape::Rect(w, h) => (w + h) * 2.
            Shape::Square(s) => s * 4.
        }
    }
}