237: Day Convolution

/// Day Convolution: combining two functors into an applicative.
///
/// Day f g a = ∃b c. (f b, g c, b -> c -> a)
///
/// The Day convolution of two functors `f` and `g` yields a new functor,
/// and if both `f` and `g` are monoidal (have a "unit" and "multiply"),
/// then Day(f, g) is an applicative functor.
///
/// Concrete example: Day(Vec, Vec) = cartesian product (list applicative)
///   Day List List a = all ways to combine elements from two lists
///
/// This is the foundation of many applicative structures and is used in
/// profunctor optics and the `Conjoined` class in Haskell's `lens` library.

/// Concrete Day convolution over Vec:
/// `Day<B, C, A>` holds a `Vec<B>`, a `Vec<C>`, and a combiner `B -> C -> A`.
/// This represents "all ways to combine one element from each list."
pub struct Day<B, C, A> {
    left: Vec<B>,
    right: Vec<C>,
    combine: Box<dyn Fn(B, C) -> A>,
}

impl<B: Clone + 'static, C: Clone + 'static, A: 'static> Day<B, C, A> {
    pub fn new(left: Vec<B>, right: Vec<C>, combine: impl Fn(B, C) -> A + 'static) -> Self {
        Day {
            left,
            right,
            combine: Box::new(combine),
        }
    }

    /// Lower: compute the cartesian product applying the combiner.
    pub fn lower(self) -> Vec<A> {
        let mut result = Vec::new();
        for b in &self.left {
            for c in &self.right {
                result.push((self.combine)(b.clone(), c.clone()));
            }
        }
        result
    }

    /// fmap: post-compose a function on the result type A.
    pub fn fmap<D: 'static>(self, f: impl Fn(A) -> D + 'static) -> Day<B, C, D>
    where
        B: 'static,
        C: 'static,
    {
        let old_combine = self.combine;
        Day {
            left: self.left,
            right: self.right,
            combine: Box::new(move |b, c| f(old_combine(b, c))),
        }
    }
}

/// Day convolution as the list applicative.
/// `apply_list fs xs` applies each function in `fs` to each element in `xs`.
/// This is exactly the Day convolution: Day List List a
fn apply_list<A: Clone, B: Clone>(fs: &[impl Fn(A) -> B], xs: &[A]) -> Vec<B> {
    let mut result = Vec::new();
    for f in fs {
        for x in xs {
            result.push(f(x.clone()));
        }
    }
    result
}

/// General Day product: given `Vec<B>`, `Vec<C>`, and combiner `B -> C -> A`
fn day_product<B: Clone, C: Clone, A>(
    bs: &[B],
    cs: &[C],
    f: impl Fn(B, C) -> A,
) -> Vec<A> {
    let mut result = Vec::new();
    for b in bs {
        for c in cs {
            result.push(f(b.clone(), c.clone()));
        }
    }
    result
}

/// Day convolution for option types:
/// `Day<Option<B>, Option<C>, A>` — combines two optional values.
fn day_option<B: Clone, C: Clone, A>(
    ob: Option<B>,
    oc: Option<C>,
    f: impl Fn(B, C) -> A,
) -> Option<A> {
    match (ob, oc) {
        (Some(b), Some(c)) => Some(f(b, c)),
        _ => None,
    }
}

fn main() {
    println!("=== Day Convolution ===\n");
    println!("Day f g a = ∃b c. (f b, g c, b -> c -> a)");
    println!("Fundamental operation for building applicative functors.\n");

    // Basic Day convolution: all sums
    let xs = vec![1_i32, 2, 3];
    let ys = vec![10_i32, 20];

    let sums = day_product(&xs, &ys, |a, b| a + b);
    println!("All sums [1,2,3] × [10,20]: {:?}", sums);

    let products = day_product(&xs, &ys, |a, b| a * b);
    println!("All products:               {:?}", products);

    let pairs = day_product(&xs, &ys, |a, b| (a, b));
    println!("Cartesian product:          {:?}", pairs);

    println!();

    // Day as the list applicative: apply functions to values
    let fs: Vec<Box<dyn Fn(i32) -> i32>> = vec![
        Box::new(|x| x * 2),
        Box::new(|x| x + 100),
    ];
    let applied = {
        let mut result = Vec::new();
        for f in &fs {
            for &x in &xs {
                result.push(f(x));
            }
        }
        result
    };
    println!("List applicative [*2, +100] <*> [1,2,3]: {:?}", applied);

    // Day for options
    let day_opt_both = day_option(Some(3_i32), Some(4_i32), |a, b| a + b);
    let day_opt_missing = day_option(Some(3_i32), None::<i32>, |a, b| a + b);
    println!();
    println!("Day Option (Some(3), Some(4), +): {:?}", day_opt_both);
    println!("Day Option (Some(3), None,    +): {:?}", day_opt_missing);

    // Full Day struct with fmap
    println!();
    let d = Day::new(vec![1_i32, 2], vec![10_i32, 20], |a, b| a + b);
    let d2 = d.fmap(|x| x * 10);
    let result = d2.lower();
    println!("Day struct with fmap (*10): {:?}", result);

    println!();
    println!("Day convolution is associative and has a unit (the identity functor).");
    println!("Monoid in the category of functors under Day = Applicative functor.");
    println!("apply_list = Day List List applied to (fs, xs) via function application.");
}

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

    #[test]
    fn test_day_product_sums() {
        let result = day_product(&[1, 2], &[10, 100], |a: i32, b: i32| a + b);
        assert_eq!(result, vec![11, 101, 12, 102]);
    }

    #[test]
    fn test_day_option_both_some() {
        let result = day_option(Some(3_i32), Some(4), |a, b| a * b);
        assert_eq!(result, Some(12));
    }

    #[test]
    fn test_day_option_none() {
        let result: Option<i32> = day_option(None, Some(4_i32), |a, b: i32| a + b);
        assert_eq!(result, None);
    }

    #[test]
    fn test_day_struct_lower() {
        let d = Day::new(vec![1_i32, 2], vec![3_i32, 4], |a, b| a + b);
        let result = d.lower();
        assert_eq!(result, vec![4, 5, 5, 6]);
    }

    #[test]
    fn test_apply_list() {
        let fs: &[fn(i32) -> i32] = &[|x| x * 2, |x| x + 1];
        let result = apply_list(fs, &[1, 2, 3]);
        assert_eq!(result, vec![2, 4, 6, 2, 3, 4]);
    }
}