karpal_free/
lan.rs

1#[cfg(feature = "std")]
2use std::boxed::Box;
3
4#[cfg(all(not(feature = "std"), feature = "alloc"))]
5use alloc::boxed::Box;
6
7use core::marker::PhantomData;
8
9use karpal_core::hkt::{HKT, IdentityF};
10use karpal_core::natural::NaturalTransformation;
11
12use crate::coyoneda::Coyoneda;
13
14/// Left Kan Extension — `Lan G H A ≅ ∃B. (G B → A, H B)`.
15///
16/// Encodes a value `H B` together with a way to extract `A` from `G B`.
17/// The intermediate type `B` is visible in Rust (unlike Haskell's existential)
18/// because Rust lacks first-class existential types.
19///
20/// # Key properties
21///
22/// - **Functor in A**: `fmap` composes onto the extract function, no bounds needed.
23/// - **Specialisation**: `Lan<IdentityF, F, A, B>` is isomorphic to `Coyoneda<F, A>`.
24/// - **Lower**: Given a natural transformation `H ~> G`, collapse to `A`.
25pub struct Lan<G: HKT, H: HKT, A, B> {
26    extract_fn: Box<dyn Fn(G::Of<B>) -> A>,
27    source: H::Of<B>,
28    _marker: PhantomData<G>,
29}
30
31impl<G: HKT + 'static, H: HKT + 'static, A: 'static, B: 'static> Lan<G, H, A, B> {
32    /// Construct a Lan from a source value and an extract function.
33    pub fn new(source: H::Of<B>, f: impl Fn(G::Of<B>) -> A + 'static) -> Self {
34        Lan {
35            extract_fn: Box::new(f),
36            source,
37            _marker: PhantomData,
38        }
39    }
40
41    /// Map a function over the result type. No bounds on G or H required.
42    pub fn fmap<C: 'static>(self, f: impl Fn(A) -> C + 'static) -> Lan<G, H, C, B> {
43        let old_extract = self.extract_fn;
44        Lan {
45            extract_fn: Box::new(move |gb| f(old_extract(gb))),
46            source: self.source,
47            _marker: PhantomData,
48        }
49    }
50
51    /// Collapse the Lan using a natural transformation `NT: H ~> G`.
52    ///
53    /// Applies the nat-trans to the source, then extracts the result.
54    pub fn lower<NT: NaturalTransformation<H, G>>(self) -> A {
55        (self.extract_fn)(NT::transform(self.source))
56    }
57}
58
59/// When `G = IdentityF`, `Lan<IdentityF, H, A, B>` is isomorphic to `Coyoneda<H, A, B>`.
60impl<H: HKT + 'static, A: 'static, B: 'static> Lan<IdentityF, H, A, B>
61where
62    H::Of<B>: 'static,
63{
64    /// Convert to `Coyoneda<H, A, B>`.
65    ///
66    /// `Lan<IdentityF, H, A, B> ≅ (B → A, H B) = Coyoneda<H, A, B>`
67    pub fn to_coyoneda(self) -> Coyoneda<H, A, B> {
68        let extract = self.extract_fn;
69        Coyoneda::<H, _, _>::lift(self.source).fmap(move |b| (*extract)(b))
70    }
71}
72
73/// Marker type for `Lan<G, H, _, B>`.
74///
75/// Note: Cannot implement `HKT` or `Functor` due to Rust's GAT limitations
76/// (extra type parameters G, H, B cannot be threaded through `type Of<T>`).
77/// Use `Lan::fmap` directly.
78pub struct LanF<G: HKT, H: HKT, B>(PhantomData<(G, H, B)>);
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use karpal_core::hkt::OptionF;
84
85    #[test]
86    fn new_and_lower() {
87        struct OptToId;
88        impl NaturalTransformation<OptionF, IdentityF> for OptToId {
89            fn transform<A>(fa: Option<A>) -> A {
90                fa.unwrap()
91            }
92        }
93
94        let lan = Lan::<IdentityF, OptionF, i32, i32>::new(Some(42), |x| x);
95        let result = lan.lower::<OptToId>();
96        assert_eq!(result, 42);
97    }
98
99    #[test]
100    fn fmap_lan() {
101        struct OptToId;
102        impl NaturalTransformation<OptionF, IdentityF> for OptToId {
103            fn transform<A>(fa: Option<A>) -> A {
104                fa.unwrap()
105            }
106        }
107
108        let lan = Lan::<IdentityF, OptionF, i32, i32>::new(Some(5), |x| x);
109        let mapped = lan.fmap(|x| x * 3);
110        let result = mapped.lower::<OptToId>();
111        assert_eq!(result, 15);
112    }
113
114    #[test]
115    fn fmap_composition() {
116        struct OptToId;
117        impl NaturalTransformation<OptionF, IdentityF> for OptToId {
118            fn transform<A>(fa: Option<A>) -> A {
119                fa.unwrap()
120            }
121        }
122
123        let f = |x: i32| x + 1;
124        let g = |x: i32| x * 2;
125
126        let left = Lan::<IdentityF, OptionF, i32, i32>::new(Some(5), |x| x).fmap(move |a| g(f(a)));
127        let right = Lan::<IdentityF, OptionF, i32, i32>::new(Some(5), |x| x)
128            .fmap(f)
129            .fmap(g);
130
131        assert_eq!(left.lower::<OptToId>(), right.lower::<OptToId>());
132    }
133
134    #[test]
135    fn fmap_identity() {
136        struct OptToId;
137        impl NaturalTransformation<OptionF, IdentityF> for OptToId {
138            fn transform<A>(fa: Option<A>) -> A {
139                fa.unwrap()
140            }
141        }
142
143        let lan = Lan::<IdentityF, OptionF, i32, i32>::new(Some(7), |x| x);
144        let mapped = lan.fmap(|x| x);
145        assert_eq!(mapped.lower::<OptToId>(), 7);
146    }
147
148    #[test]
149    fn to_coyoneda_roundtrip() {
150        let lan =
151            Lan::<IdentityF, OptionF, String, i32>::new(Some(42), |x: i32| format!("val={x}"));
152        let coy = lan.to_coyoneda();
153        let result = coy.lower();
154        assert_eq!(result, Some("val=42".to_string()));
155    }
156
157    #[test]
158    fn to_coyoneda_with_fmap() {
159        let lan = Lan::<IdentityF, OptionF, i32, i32>::new(Some(10), |x| x);
160        let coy = lan.fmap(|x| x + 5).to_coyoneda();
161        let result = coy.lower();
162        assert_eq!(result, Some(15));
163    }
164
165    #[test]
166    fn lower_with_extract_transform() {
167        // Lan<OptionF, OptionF, String, i32>:
168        // extract: Option<i32> -> String
169        // source: Option<i32>
170        // lower with id nat-trans: extract(source)
171        struct OptionId;
172        impl NaturalTransformation<OptionF, OptionF> for OptionId {
173            fn transform<A>(fa: Option<A>) -> Option<A> {
174                fa
175            }
176        }
177
178        let lan =
179            Lan::<OptionF, OptionF, String, i32>::new(Some(99), |opt| format!("got: {:?}", opt));
180        let result = lan.lower::<OptionId>();
181        assert_eq!(result, "got: Some(99)");
182    }
183}
184
185#[cfg(test)]
186mod law_tests {
187    use super::*;
188    use karpal_core::hkt::OptionF;
189    use proptest::prelude::*;
190
191    struct OptToId;
192    impl NaturalTransformation<OptionF, IdentityF> for OptToId {
193        fn transform<A>(fa: Option<A>) -> A {
194            fa.unwrap()
195        }
196    }
197
198    proptest! {
199        // Functor identity: fmap(id, lan).lower() == lan.lower()
200        #[test]
201        fn functor_identity(x in any::<i32>()) {
202            let result = Lan::<IdentityF, OptionF, i32, i32>::new(Some(x), |a| a)
203                .fmap(|a| a)
204                .lower::<OptToId>();
205            prop_assert_eq!(result, x);
206        }
207
208        // Functor composition: fmap(g . f) == fmap(g) . fmap(f)
209        #[test]
210        fn functor_composition(x in any::<i32>()) {
211            let f = |a: i32| a.wrapping_add(1);
212            let g = |a: i32| a.wrapping_mul(2);
213
214            let left = Lan::<IdentityF, OptionF, i32, i32>::new(Some(x), |a| a)
215                .fmap(move |a| g(f(a)))
216                .lower::<OptToId>();
217            let right = Lan::<IdentityF, OptionF, i32, i32>::new(Some(x), |a| a)
218                .fmap(f)
219                .fmap(g)
220                .lower::<OptToId>();
221            prop_assert_eq!(left, right);
222        }
223    }
224}
karpal_free/lan.rs

karpal_free/
lan.rs
