246: Adjunctions

/// Adjunctions: F ⊣ G
///
/// F and G are adjoint if there is a natural isomorphism:
///   Hom(F A, B) ≅ Hom(A, G B)
///
/// Equivalently, there are natural transformations:
///   unit   :: A -> G(F(A))       (also called η)
///   counit :: F(G(B)) -> B       (also called ε)
///
/// satisfying the triangle identities:
///   counit(F(unit(a))) = a   (or in Rust: counit . F(unit) = id)
///   G(counit(unit(g))) = g
///
/// ── The canonical example: Product ⊣ Exponential ──────────────────────────
///
///   F(A) = A × C   (product with C on the right)
///   G(B) = C → B   (exponential / function type)
///
/// Hom(A × C, B) ≅ Hom(A, C → B)
/// This is just curry/uncurry!
///
/// ── Monad from adjunction ─────────────────────────────────────────────────
/// G ∘ F is a monad with:
///   return = unit
///   join   = G(counit . F)  (which becomes State monad for this adjunction)

// ── Curry/Uncurry Adjunction ─────────────────────────────────────────────────

use std::rc::Rc;

/// curry: (A × C -> B) -> (A -> C -> B)
/// This is the isomorphism Hom(F A, B) -> Hom(A, G B)
pub fn curry<A: Clone + 'static, B: 'static, C: 'static>(
    f: impl Fn(A, C) -> B + 'static,
) -> impl Fn(A) -> Box<dyn Fn(C) -> B> {
    let f = Rc::new(f);
    move |a: A| {
        let a2 = a.clone();
        let f2 = f.clone();
        Box::new(move |c: C| f2(a2.clone(), c))
    }
}

/// uncurry: (A -> C -> B) -> (A × C -> B)
/// This is the inverse isomorphism Hom(A, G B) -> Hom(F A, B)
pub fn uncurry<A: Clone + 'static, B: 'static, C: 'static>(
    f: impl Fn(A) -> Box<dyn Fn(C) -> B> + 'static,
) -> impl Fn(A, C) -> B {
    move |a, c| (f(a))(c)
}

/// unit of the adjunction: a -> C -> (A × C)
/// unit_adj c a = (a, c) — pair a with the fixed context c
pub fn unit_adj<A: Clone, C: Clone>(c: C) -> impl Fn(A) -> (A, C) {
    move |a| (a, c.clone())
}

/// counit of the adjunction: (A × C -> B) × (A × C) -> B
/// = function application
pub fn counit_adj<A, B, C>(f: impl Fn(A, C) -> B, a: A, c: C) -> B {
    f(a, c)
}

// ── List Adjunction: Free ⊣ Forgetful ────────────────────────────────────────
///
/// The free monoid adjunction:
///   F(A) = Vec<A>   (free monoid on A)
///   G(M) = underlying set of M (forgetful functor)
///
/// Hom_Mon(Vec<A>, M) ≅ Hom_Set(A, G M)
/// A monoid homomorphism from Vec<A> is determined by where it sends generators.

/// Unit of the Free ⊣ Forgetful adjunction: a -> [a]
pub fn free_unit<A>(a: A) -> Vec<A> {
    vec![a]
}

/// Counit: fold a Vec<Vec<A>> (free monad structure) into Vec<A>
/// This is Vec::concat (flatten)
pub fn free_counit<A>(vv: Vec<Vec<A>>) -> Vec<A> {
    vv.into_iter().flatten().collect()
}

/// The monad arising from the Free-Forgetful adjunction is Vec (list monad).
/// return = free_unit, bind = flat_map
pub fn list_bind<A: Clone, B>(xs: Vec<A>, f: impl Fn(A) -> Vec<B>) -> Vec<B> {
    xs.into_iter().flat_map(f).collect()
}

// ── Option Adjunction ─────────────────────────────────────────────────────────
///
/// Option ⊣ Diagonal (in some sense):
/// More precisely, the adjunction between pointed sets and sets.
/// Return = Some, join = Option::flatten

pub fn option_return<A>(a: A) -> Option<A> {
    Some(a)
}

pub fn option_join<A>(oa: Option<Option<A>>) -> Option<A> {
    oa.flatten()
}

// ── Verify the triangle identities ──────────────────────────────────────────

fn main() {
    println!("=== Adjunctions ===\n");
    println!("F ⊣ G means: Hom(F A, B) ≅ Hom(A, G B)");
    println!("Unit:   η :: A -> G(F(A))");
    println!("Counit: ε :: F(G(B)) -> B\n");

    println!("── Product ⊣ Exponential (curry/uncurry) ──\n");

    let add = |a: i32, b: i32| a + b;
    let curried_add = curry(add);
    println!("curry(add)(3)(4) = {}", (curried_add(3))(4));

    // uncurry expects fn that returns Box<dyn Fn>
    let mul_boxed = |a: i32| -> Box<dyn Fn(i32) -> i32> { Box::new(move |b: i32| a * b) };
    let uncurried_mul = uncurry(mul_boxed);
    println!("uncurry(mul)(3, 4) = {}", uncurried_mul(3, 4));

    // Verify: curry . uncurry = id
    let add2 = |a: i32, b: i32| a + b;
    let add2_rt = uncurry(curry(add2));
    assert_eq!(add2_rt(3, 4), 7);
    println!("\nuncurry(curry(add))(3,4) = {} ✓", add2_rt(3, 4));

    // Verify: uncurry . curry = id
    let m1 = 5_i32 * 6;
    let mul_boxed2 = |a: i32| -> Box<dyn Fn(i32) -> i32> { Box::new(move |b: i32| a * b) };
    let m2 = (curry(uncurry(mul_boxed2))(5))(6);
    assert_eq!(m1, m2);
    println!("curry(uncurry(mul))(5)(6) = {} ✓", m2);

    // Unit and counit
    println!("\nUnit (pair with context 10): {:?}", unit_adj(10_i32)(42_i32));
    let f = |a: i32, c: i32| a + c;
    println!("Counit (apply): f(3, 10) = {}", counit_adj(f, 3, 10));

    println!("\n── Free ⊣ Forgetful (Vec / list monad) ──\n");

    // Free unit: a -> [a]
    println!("free_unit(42) = {:?}", free_unit(42_i32));

    // Counit: flatten
    println!("free_counit([[1,2],[3],[4,5]]) = {:?}",
        free_counit(vec![vec![1, 2], vec![3], vec![4, 5]]));

    // List monad from adjunction
    let result = list_bind(vec![1_i32, 2, 3], |x| vec![x, x * 10]);
    println!("list_bind [1,2,3] (\\x -> [x, x*10]) = {:?}", result);

    println!("\n── Option monad from adjunction ──\n");
    println!("option_return(5) = {:?}", option_return(5_i32));
    println!("option_join(Some(Some(3))) = {:?}", option_join(Some(Some(3_i32))));
    println!("option_join(Some(None::<i32>)) = {:?}", option_join(Some(None::<i32>)));
    println!("option_join(None::<Option<i32>>) = {:?}", option_join(None::<Option<i32>>));

    println!();
    println!("Key theorem: every adjunction F ⊣ G yields a monad G∘F.");
    println!("Product ⊣ Exponential → State monad (see example 249).");
    println!("Free ⊣ Forgetful → List monad.");
    println!("Maybe ⊣ Pointed Set → Option monad.");
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_curry_uncurry_roundtrip() {
        let f = |a: i32, b: i32| a + b;
        let g = uncurry(curry(f));
        assert_eq!(g(3, 4), 7);
        assert_eq!(g(0, 0), 0);
    }

    #[test]
    fn test_uncurry_curry_roundtrip() {
        let f = |a: i32| -> Box<dyn Fn(i32) -> i32> { Box::new(move |b: i32| a * b) };
        assert_eq!((curry(uncurry(f))(3))(4), 12);
    }

    #[test]
    fn test_unit_adj() {
        let u = unit_adj(99_i32);
        assert_eq!(u(42_i32), (42, 99));
    }

    #[test]
    fn test_list_bind() {
        let result = list_bind(vec![1_i32, 2], |x| vec![x * 2, x * 3]);
        assert_eq!(result, vec![2, 3, 4, 6]);
    }

    #[test]
    fn test_free_counit() {
        let r = free_counit(vec![vec![1, 2], vec![3]]);
        assert_eq!(r, vec![1, 2, 3]);
    }

    #[test]
    fn test_option_join() {
        assert_eq!(option_join(Some(Some(7_i32))), Some(7));
        assert_eq!(option_join(Some(None::<i32>)), None);
        assert_eq!(option_join(None::<Option<i32>>), None);
    }
}