Category: The Essence of Composition

Exercises

Implement, as best as you can, the identity function in your favorite language (or the second favorite, if your favorite language happens to be Haskell).

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

For any type T, id maps a value of type T back to itself without changing it.

Implement the composition function in your favorite language. It takes two functions as arguments and returns a function that is their composition.

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

Composition would be compose(f, g)(x) -> f(g(x)). In rust it’s a bit clunkier since we need generics.

To call this:

fn add_one(x: i32) -> i32 {  
    x + 1  
}  
 
fn add_two(x: i32) -> i32 {  
    x + 2  
}
 
let f = compose(add_one, add_two);
 
f(10) // 13

Write a program that tries to test that your composition function respects identity.

To test this, compose(f, id) and compose(id, f) should return the same result.

assert_eq!(compose(id, add_one), compose(add_one, id));

A category needs objects, morphisms, composition, and identity for every object.

Web pages are objects, but they need a way to link between objects, composition, and identity, which they don’t have.

Links are also close but not always stable.

Facebook isn’t a category because there’s no composition of A -> B && B -> C implying A -> C.