Functional Category Theory in JavaScript

gistfile1.md

Functional Category Theory in JavaScript

Category Theory Fundamentals and Implementation

1. Categories

A category C consists of:

• Objects: Ob(C)
• Morphisms: ∀A,B ∈ Ob(C), Hom(A,B)
• Identity: ∀A ∈ Ob(C), idₐ: A → A
• Composition: ∀f: A → B, g: B → C, g ∘ f: A → C

// A category is defined by its morphisms, as objects are implicit in morphism endpoints
const createCategory = (name) => {
    const morphisms = new Map();
    const cache = new Map(); // For memoizing compositions

    // f: A → B, represents morphism from A to B
    const addMorphism = (source, target, f) => {
        morphisms.set(`${source}->${target}`, f);
    };

    // id_A: A → A
    const identity = x => x;

    // Given f: A → B and g: B → C, returns g ∘ f: A → C
    const compose = (f, g) => {
        // Memoize compositions for performance
        const key = `${f.toString()}->${g.toString()}`;
        if (cache.has(key)) return cache.get(key);
        
        const composition = x => g(f(x));
        cache.set(key, composition);
        return composition;
    };

    // Verify category laws for a given set of values
    const verifyLaws = (testValues) => {
        for (const [key, f] of morphisms.entries()) {
            const [source, target] = key.split('->');
            
            // Identity law: f ∘ id = f = id ∘ f
            testValues.forEach(x => {
                const leftId = compose(identity, f)(x);
                const rightId = compose(f, identity)(x);
                const direct = f(x);
                
                if (leftId !== direct || rightId !== direct) {
                    throw new Error(`Identity law violated for ${source}->${target}`);
                }
            });

            // Test associativity for composable morphisms
            morphisms.forEach((g, keyG) => {
                morphisms.forEach((h, keyH) => {
                    const [gSource, gTarget] = keyG.split('->');
                    const [hSource, hTarget] = keyH.split('->');
                    
                    if (target === gSource && gTarget === hSource) {
                        // (h ∘ g) ∘ f = h ∘ (g ∘ f)
                        testValues.forEach(x => {
                            const left = compose(compose(f, g), h)(x);
                            const right = compose(f, compose(g, h))(x);
                            if (left !== right) {
                                throw new Error('Associativity law violated');
                            }
                        });
                    }
                });
            });
        });
        return true;
    };

    return { addMorphism, compose, identity, verifyLaws };
};

2. Functors

A functor F: C → D is:

• Object mapping: F: Ob(C) → Ob(D)
• Morphism mapping: F: Hom(C)(A,B) → Hom(D)(F(A),F(B))

Satisfying:

1. F(id_A) = id_F(A)
2. F(g ∘ f) = F(g) ∘ F(f)

const createFunctor = (sourceCategory, targetCategory, objectMap, morphismMap) => {
    // F(A) for object A
    const mapObject = objectMap;

    // F(f) for morphism f
    const mapMorphism = morphismMap;

    // Verify functor laws
    const verifyLaws = (testValues) => {
        // 1. F(id_A) = id_F(A)
        testValues.forEach(x => {
            const mapped = mapMorphism(sourceCategory.identity)(mapObject(x));
            const targetId = targetCategory.identity(mapObject(x));
            if (mapped !== targetId) {
                throw new Error('Functor identity law violated');
            }
        });

        // 2. F(g ∘ f) = F(g) ∘ F(f)
        sourceCategory.morphisms.forEach((f, keyF) => {
            sourceCategory.morphisms.forEach((g, keyG) => {
                const [fSource, fTarget] = keyF.split('->');
                const [gSource, gTarget] = keyG.split('->');
                
                if (fTarget === gSource) {
                    testValues.forEach(x => {
                        const composed = mapMorphism(
                            sourceCategory.compose(f, g)
                        )(mapObject(x));
                        
                        const mappedSeparately = targetCategory.compose(
                            mapMorphism(f),
                            mapMorphism(g)
                        )(mapObject(x));
                        
                        if (composed !== mappedSeparately) {
                            throw new Error('Functor composition law violated');
                        }
                    });
                }
            });
        });
        return true;
    };

    return { mapObject, mapMorphism, verifyLaws };
};

3. Monads

A monad is (T, η, μ) where:

• T: C → C (endofunctor)
• η: 1_C → T (unit)
• μ: T² → T (multiplication)

Satisfying:

1. μ ∘ Tμ = μ ∘ μT (associativity)
2. μ ∘ Tη = μ ∘ ηT = 1_T (unit laws)

const createMonad = (category) => (T, unit, join) => {
    // Kleisli composition (>=>): (A → TB) ∘ (B → TC) → (A → TC)
    const kleisliCompose = (f, g) => x => 
        join(T.mapMorphism(g)(f(x)));

    // bind (>>=): TA → (A → TB) → TB
    const bind = (ta, f) => join(T.mapMorphism(f)(ta));

    // Verify monad laws
    const verifyLaws = (testValues) => {
        // Associativity: (join ∘ T(join)) = (join ∘ join_T)
        testValues.forEach(x => {
            const TTTx = T.mapObject(T.mapObject(T.mapObject(x)));
            const left = join(T.mapMorphism(join)(TTTx));
            const right = join(join(TTTx));
            if (left !== right) {
                throw new Error('Monad associativity law violated');
            }
        });

        // Left unit: join ∘ T(unit) = id
        // Right unit: join ∘ unit_T = id
        testValues.forEach(x => {
            const Tx = T.mapObject(x);
            const leftUnit = join(T.mapMorphism(unit)(Tx));
            const rightUnit = join(unit(T.mapObject(x)));
            if (leftUnit !== Tx || rightUnit !== Tx) {
                throw new Error('Monad unit laws violated');
            }
        });
        return true;
    };

    return { bind, kleisliCompose, verifyLaws };
};

// Example: Maybe Monad Implementation
const maybeCategory = createCategory('Maybe');

const maybeT = createFunctor(
    maybeCategory,
    maybeCategory,
    x => x === null ? null : x,
    f => x => x === null ? null : f(x)
);

const maybeMonad = createMonad(maybeCategory)(
    maybeT,
    x => x,  // unit: A → Maybe(A)
    x => x === null ? null : x  // join: Maybe(Maybe(A)) → Maybe(A)
);

// Example: List Monad Implementation
const listCategory = createCategory('List');

const listT = createFunctor(
    listCategory,
    listCategory,
    x => [x],
    f => xs => xs.flatMap(f)
);

const listMonad = createMonad(listCategory)(
    listT,
    x => [x],  // unit: A → [A]
    xss => xss.flat()  // join: [[A]] → [A]
);

Practical Applications

1. Error Handling with Maybe Monad

// Safe division using Maybe monad
const safeDivide = (x, y) => y === 0 ? null : x / y;

const computeWithMaybe = (x, y, z) =>
    maybeMonad.bind(safeDivide(x, y), result =>
        maybeMonad.bind(safeDivide(result, z), final =>
            final
        )
    );

console.log(computeWithMaybe(10, 2, 2));  // 2.5
console.log(computeWithMaybe(10, 0, 2));  // null

2. List Processing with List Monad

// Generate all combinations using List monad
const combinations = (xs, ys) =>
    listMonad.bind(xs, x =>
        listMonad.bind(ys, y => [x + y])
    );

console.log(combinations([1, 2], [10, 20]));  // [11, 21, 12, 22]

3. Parser Combinators

const parser = createMonad(createCategory('Parser'))(
    createFunctor(
        /* Parser implementation */
        (input) => /* parsing logic */,
        (f) => (parser) => (input) => /* composition logic */
    ),
    (x) => (input) => [x, input],  // unit
    (p) => (input) => {  // join
        const [result, rest] = p(input);
        return result(rest);
    }
);

// Example parser usage
const numberParser = (input) => {
    const match = /^\d+/.exec(input);
    return match 
        ? [Number(match[0]), input.slice(match[0].length)]
        : null;
};

Mathematical Properties and Software Design

The implementation demonstrates several key mathematical properties:

1. Composition Safety

   • Category laws ensure safe composition of operations
   • Functor laws preserve structure across transformations
   • Monad laws guarantee consistent sequencing of effects

2. Algebraic Reasoning

   • Programs can be reasoned about using categorical algebra
   • Equational reasoning becomes possible through laws
   • Refactoring preserves semantics

3. Type Safety

   • Categories model type relationships
   • Functors ensure type-safe transformations
   • Monads provide type-safe effect handling