karpal_free/
lan.rs

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

karpal_free/
lan.rs
