Category Theory for Programmers: Exercises (Chapter 4)

Kleisli Categories

1. Construct the Kleisli category for partial functions (define composition and identity).

type Optional<T> = [T, true] | [null, false];

// Define identity. 'true' is  the identity element of the monoid 
// of booleans under the AND operation.
const idOpt = <T,>(x: T): Optional<T> => {
    return [x, true];
};

// Define composition
const composeOpt = <T, U, V>(
    o1: (x: T) => Optional<U>,
    o2: (x: U) => Optional<V>,
) => {
    return (x: T) => {
        const [v, isValid] = o1(x);
        return isValid ? o2(v) : [null, false];
    };
};

const safeRoot = (x: number): Optional<number> => {
    return x >= 0 ? [Math.sqrt(x), true] : [null, false];
};

const isEven = (x: number): Optional<boolean> => {
    return Number.isInteger(x) ? [!(x % 2), true] : [null, false];
};

// Compose the two functors
const rootIsEven = composeOpt(safeRoot, isEven);

// Compose with identity
const isEven2 = composeOpt(idOpt<number>, isEven);
const isEven3 = composeOpt(isEven, idOpt);

rootIsEven(16); // [ true, true ]
rootIsEven(9); // [ false, true ]
rootIsEven(2); // [ null, false ]

isEven2(4); // [ true, true ]
isEven3(4); // [ true, true ]

isEven2(5); // [ false, true ]
isEven3(5); // [ false, true ]

2. Implement the embellished function safe_reciprocal that returns a valid reciprocal of its argument, if it’s different from zero.

const safeReciprocal = (x: number): Optional<number> => {
    return x === 0 ? [null, false] : [1 / x, true];
};

3. Compose safe_root and safe_reciprocal to implement safe_root_reciprocal that calculates sqrt(1/x) whenever possible.

const safeRootReciprocal = composeOpt(safeReciprocal, safeRoot);

safeRootReciprocal(0); // [ null, false ]
safeRootReciprocal(16); // [ 0.25, true ]
safeRootReciprocal(-5); // [ null, false ]