236: Coyoneda

/// Coyoneda: The Free Functor.
///
/// Coyoneda f a = ∃b. (b -> a, f b)
///
/// Any type constructor `f` becomes a functor "for free" via Coyoneda,
/// even if `f` itself has no Functor instance. This is the *left* Kan
/// extension of `f` along the identity functor.
///
/// Key property: fmap via Coyoneda composes functions *without* running them.
/// Only `lower` (the "run") actually traverses the structure. This gives
/// automatic fusion: N fmaps = 1 traversal.
///
/// ⚠  Rust HKT limitation: we can't write `Coyoneda<F, A>` for arbitrary `F`.
/// We fix F = Vec and use a trait object for the erased intermediate type `b`.

/// Coyoneda of Vec: holds a Vec<B> (for some hidden B) and a function B->A.
/// The existential `∃b` is encoded via a trait object + boxed closure.
pub struct Coyoneda<A> {
    /// The internal implementation that, when called, applies the accumulated
    /// function to the original data and returns Vec<A>.
    lower_fn: Box<dyn FnOnce() -> Vec<A>>,
}

impl<A: 'static> Coyoneda<A> {
    /// Lift a Vec<A> into Coyoneda — the identity transformation.
    /// Corresponds to: `lift xs = Coyoneda id xs`
    pub fn lift(data: Vec<A>) -> Self {
        Coyoneda {
            lower_fn: Box::new(move || data),
        }
    }

    /// fmap: compose a new function WITHOUT executing it.
    /// Corresponds to: `fmap f (Coyoneda g xs) = Coyoneda (f . g) xs`
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> Coyoneda<B> {
        Coyoneda {
            lower_fn: Box::new(move || {
                let data = (self.lower_fn)();
                data.into_iter().map(f).collect()
            }),
        }
    }

    /// Lower: execute the accumulated transformation (single traversal).
    pub fn lower(self) -> Vec<A> {
        (self.lower_fn)()
    }
}

/// Alternative encoding that makes the deferred composition more explicit.
/// Stores (original_data, composed_function) as separate fields.
pub struct CoyonedaExplicit<A> {
    // We store the original data as Vec<i32> (a concrete "hidden" type B=i32)
    // and a composed function i32 -> A.
    // In full Coyoneda, B would be existentially hidden.
    original: Vec<i32>,
    transform: Box<dyn Fn(i32) -> A>,
}

impl<A: 'static> CoyonedaExplicit<A> {
    pub fn lift(data: Vec<i32>) -> CoyonedaExplicit<i32>
    where
        i32: 'static,
    {
        CoyonedaExplicit {
            original: data,
            transform: Box::new(|x| x),
        }
    }
}

impl<A: 'static> CoyonedaExplicit<A> {
    /// fmap: just composes — O(1) per fmap call, not O(n)
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> CoyonedaExplicit<B> {
        let prev = self.transform;
        CoyonedaExplicit {
            original: self.original,
            transform: Box::new(move |x| f(prev(x))),
        }
    }

    /// Lower: single pass applies ALL composed functions
    pub fn lower(self) -> Vec<A> {
        self.original.into_iter().map(|x| (self.transform)(x)).collect()
    }
}

fn main() {
    println!("=== Coyoneda: The Free Functor ===\n");
    println!("Coyoneda f a = ∃b. (b -> a, f b)");
    println!("Any type constructor becomes a functor for free.\n");

    println!("⚠  Rust HKT limitation: F is fixed to Vec; b is type-erased.");
    println!("   In OCaml/Haskell, Coyoneda works for ANY type constructor F.\n");

    let data = vec![1_i32, 2, 3, 4, 5];

    // Via Coyoneda: lift, chain fmaps, lower
    let result = Coyoneda::lift(data.clone())
        .fmap(|x| x * 2)
        .fmap(|x| x + 1)
        .fmap(|x| x.to_string())
        .lower();

    println!("Coyoneda fused maps: {:?}", result);

    // Direct computation for comparison
    let direct: Vec<String> = data.iter()
        .map(|&x| (x * 2 + 1).to_string())
        .collect();
    println!("Direct:              {:?}", direct);
    assert_eq!(result, direct, "Coyoneda must equal direct");
    println!("Results identical ✓\n");

    // Explicit Coyoneda
    let result2 = CoyonedaExplicit::<i32>::lift(vec![10, 20, 30])
        .fmap(|x: i32| x + 5)
        .fmap(|x: i32| x * 2)
        .fmap(|x: i32| format!("val={}", x))
        .lower();
    println!("CoyonedaExplicit: {:?}", result2);

    println!();
    println!("Key property: N calls to fmap = 1 traversal when lowered.");
    println!("The functions compose: fmap f (fmap g x) = fmap (f.g) x");
    println!("This is the Coyoneda lemma: Nat(Coyoneda F, G) ≅ Nat(F, G)");
    println!("(natural transformations out of Coyoneda = natural transformations out of F)");
}

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

    #[test]
    fn test_lift_lower_roundtrip() {
        let data = vec![1, 2, 3, 4, 5];
        let result = Coyoneda::lift(data.clone()).lower();
        assert_eq!(result, data);
    }

    #[test]
    fn test_fmap_fusion() {
        let result = Coyoneda::lift(vec![1_i32, 2, 3])
            .fmap(|x| x * 10)
            .fmap(|x| x + 1)
            .lower();
        assert_eq!(result, vec![11, 21, 31]);
    }

    #[test]
    fn test_type_change() {
        let result = Coyoneda::lift(vec![1_i32, 2, 3])
            .fmap(|x| x.to_string())
            .lower();
        assert_eq!(result, vec!["1", "2", "3"]);
    }

    #[test]
    fn test_explicit_fmap() {
        let result = CoyonedaExplicit::lift(vec![1, 2, 3])
            .fmap(|x: i32| x * 2)
            .lower();
        assert_eq!(result, vec![2, 4, 6]);
    }

    #[test]
    fn test_fused_equals_composed() {
        let data = vec![1_i32, 2, 3, 4];
        let fused = Coyoneda::lift(data.clone())
            .fmap(|x| x * 3)
            .fmap(|x| x - 1)
            .lower();
        let direct: Vec<i32> = data.iter().map(|&x| x * 3 - 1).collect();
        assert_eq!(fused, direct);
    }
}