karpal_free/
free_ap.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::applicative::Applicative;
10use karpal_core::hkt::HKT;
11
12// ---- Private dyn-safe trait for existential encoding ----
13
14/// Dyn-safe trait for a node in the Free Applicative tree.
15///
16/// Each node erases some intermediate type `B` via trait-object dispatch.
17/// Only methods that use types already in the trait parameters (F, A) are
18/// dyn-compatible.
19trait FreeApNode<F: HKT + 'static, A: 'static> {
20    /// Retract into F's own Applicative. Dyn-safe because F and A are
21    /// trait-level type parameters.
22    fn retract_node(self: Box<Self>) -> F::Of<A>
23    where
24        F: Applicative;
25
26    /// Count the number of `lift_f` effects in this subtree.
27    fn count_effects(&self) -> usize;
28}
29
30/// Lift node: stores `F<B>` and continuation `FreeAp<F, Box<dyn Fn(B) -> A>>`.
31///
32/// Represents the GADT constructor: `Ap :: f b -> FreeAp f (b -> a) -> FreeAp f a`
33struct LiftNode<F: HKT + 'static, A: 'static, B: Clone + 'static> {
34    effect: F::Of<B>,
35    rest: FreeAp<F, Box<dyn Fn(B) -> A>>,
36}
37
38impl<F: HKT + 'static, A: 'static, B: Clone + 'static> FreeApNode<F, A> for LiftNode<F, A, B> {
39    fn retract_node(self: Box<Self>) -> F::Of<A>
40    where
41        F: Applicative,
42    {
43        let f_fn: F::Of<Box<dyn Fn(B) -> A>> = self.rest.retract();
44        let f_b: F::Of<B> = self.effect;
45        F::ap(f_fn, f_b)
46    }
47
48    fn count_effects(&self) -> usize {
49        1 + self.rest.count_effects()
50    }
51}
52
53/// Fmap node: deferred map operation.
54struct FmapNode<F: HKT + 'static, Src: 'static, A: 'static> {
55    inner: FreeAp<F, Src>,
56    transform: Box<dyn Fn(Src) -> A>,
57}
58
59impl<F: HKT + 'static, Src: 'static, A: 'static> FreeApNode<F, A> for FmapNode<F, Src, A> {
60    fn retract_node(self: Box<Self>) -> F::Of<A>
61    where
62        F: Applicative,
63    {
64        let f_src: F::Of<Src> = self.inner.retract();
65        F::fmap(f_src, self.transform)
66    }
67
68    fn count_effects(&self) -> usize {
69        self.inner.count_effects()
70    }
71}
72
73/// Ap node: deferred applicative application.
74struct ApNode<F: HKT + 'static, Src: Clone + 'static, A: 'static> {
75    ff: FreeAp<F, Box<dyn Fn(Src) -> A>>,
76    fa: FreeAp<F, Src>,
77}
78
79impl<F: HKT + 'static, Src: Clone + 'static, A: 'static> FreeApNode<F, A> for ApNode<F, Src, A> {
80    fn retract_node(self: Box<Self>) -> F::Of<A>
81    where
82        F: Applicative,
83    {
84        let f_fn: F::Of<Box<dyn Fn(Src) -> A>> = self.ff.retract();
85        let f_src: F::Of<Src> = self.fa.retract();
86        F::ap(f_fn, f_src)
87    }
88
89    fn count_effects(&self) -> usize {
90        self.ff.count_effects() + self.fa.count_effects()
91    }
92}
93
94// ---- Public FreeAp type ----
95
96#[allow(private_interfaces)]
97/// Free Applicative Functor — build applicative computations as data.
98///
99/// `FreeAp<F, A>` stores a computation tree where effects from `F`
100/// can be statically analyzed before interpretation. Unlike `Free<F, A>`
101/// (the free monad), effects in `FreeAp` do not depend on the results
102/// of previous effects.
103///
104/// ```text
105/// Pure(a)     — a finished computation
106/// Ap(node)    — an effect step (existentially quantified)
107/// ```
108///
109/// # Interpretation
110///
111/// The primary eliminator is `retract`, which collapses the tree into
112/// `F`'s own applicative. To interpret into a *different* applicative `M`
113/// via a natural transformation `NT: F ~> M`, apply `NT` at each
114/// `lift_f` call site:
115///
116/// ```text
117/// // Instead of fold_map:
118/// let free_m: FreeAp<M, A> = build_tree_with(|effect| lift_f(NT::transform(effect)));
119/// let result: M::Of<A> = free_m.retract();
120/// ```
121///
122/// This decomposition (`fold_map nt ≡ retract . hoist nt`) is necessary
123/// because Rust's type system cannot dispatch a generic natural
124/// transformation through trait objects (the intermediate type `B` is
125/// erased, preventing compile-time monomorphization of `NT::transform<B>`).
126///
127/// # When to use FreeAp vs Free
128///
129/// - Use `FreeAp<F, A>` when effects are independent and you want
130///   static analysis of the effect structure.
131/// - Use `Free<F, A>` when later effects depend on earlier results
132///   (monadic sequencing).
133pub enum FreeAp<F: HKT + 'static, A: 'static> {
134    /// A pure value.
135    Pure(A),
136    /// An effect step with erased intermediate type.
137    Ap(Box<dyn FreeApNode<F, A>>),
138}
139
140impl<F: HKT + 'static, A: 'static> FreeAp<F, A> {
141    /// Wrap a pure value into the free applicative.
142    pub fn pure(a: A) -> Self {
143        FreeAp::Pure(a)
144    }
145
146    /// Lift a single effect `F<A>` into the free applicative.
147    ///
148    /// `A: Clone` is required because `Apply::ap` needs it.
149    pub fn lift_f(fa: F::Of<A>) -> Self
150    where
151        A: Clone,
152        F::Of<A>: 'static,
153    {
154        FreeAp::Ap(Box::new(LiftNode {
155            effect: fa,
156            rest: FreeAp::Pure(Box::new(|b| b) as Box<dyn Fn(A) -> A>),
157        }))
158    }
159
160    /// Map a function over the result. No bounds on `F` required.
161    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> FreeAp<F, B> {
162        match self {
163            FreeAp::Pure(a) => FreeAp::Pure(f(a)),
164            FreeAp::Ap(node) => FreeAp::Ap(Box::new(FmapNode {
165                inner: FreeAp::Ap(node),
166                transform: Box::new(f),
167            })),
168        }
169    }
170
171    /// Applicative `ap`: apply a wrapped function to this value.
172    ///
173    /// `ff` contains functions `A → B`, `self` contains `A` values.
174    pub fn ap<B: 'static>(ff: FreeAp<F, Box<dyn Fn(A) -> B>>, fa: FreeAp<F, A>) -> FreeAp<F, B>
175    where
176        A: Clone,
177    {
178        match ff {
179            FreeAp::Pure(f) => fa.fmap(f),
180            FreeAp::Ap(node) => FreeAp::Ap(Box::new(ApNode {
181                ff: FreeAp::Ap(node),
182                fa,
183            })),
184        }
185    }
186
187    /// Interpret by collapsing back into `F` itself.
188    ///
189    /// Requires `F: Applicative`.
190    pub fn retract(self) -> F::Of<A>
191    where
192        F: Applicative,
193    {
194        match self {
195            FreeAp::Pure(a) => F::pure(a),
196            FreeAp::Ap(node) => node.retract_node(),
197        }
198    }
199
200    /// Count the number of `lift_f` effects in this computation tree.
201    ///
202    /// This demonstrates the key advantage of free applicatives over
203    /// free monads: the tree structure can be statically analyzed
204    /// without interpretation.
205    pub fn count_effects(&self) -> usize {
206        match self {
207            FreeAp::Pure(_) => 0,
208            FreeAp::Ap(node) => node.count_effects(),
209        }
210    }
211}
212
213/// Marker type for `FreeAp<F, _>`.
214///
215/// Note: Cannot implement `HKT` or `Functor` due to Rust's GAT limitations
216/// (`type Of<T>` cannot add `T: 'static` in impl when trait doesn't have it).
217/// Use `FreeAp::fmap` directly.
218pub struct FreeApF<F: HKT + 'static>(PhantomData<F>);
219
220#[cfg(test)]
221mod tests {
222    use super::*;
223    use karpal_core::hkt::OptionF;
224
225    #[test]
226    fn pure_retract() {
227        let fa = FreeAp::<OptionF, i32>::pure(42);
228        let result = fa.retract();
229        assert_eq!(result, Some(42));
230    }
231
232    #[test]
233    fn lift_f_retract() {
234        let fa = FreeAp::<OptionF, i32>::lift_f(Some(10));
235        let result = fa.retract();
236        assert_eq!(result, Some(10));
237    }
238
239    #[test]
240    fn lift_f_none() {
241        let fa = FreeAp::<OptionF, i32>::lift_f(None);
242        let result = fa.retract();
243        assert_eq!(result, None);
244    }
245
246    #[test]
247    fn fmap_pure_retract() {
248        let fa = FreeAp::<OptionF, i32>::pure(5).fmap(|x| x * 3);
249        let result = fa.retract();
250        assert_eq!(result, Some(15));
251    }
252
253    #[test]
254    fn fmap_lift_retract() {
255        let fa = FreeAp::<OptionF, i32>::lift_f(Some(4)).fmap(|x| x + 10);
256        let result = fa.retract();
257        assert_eq!(result, Some(14));
258    }
259
260    #[test]
261    fn ap_pure_pure() {
262        let ff = FreeAp::<OptionF, Box<dyn Fn(i32) -> i32>>::pure(
263            Box::new(|x| x * 2) as Box<dyn Fn(i32) -> i32>
264        );
265        let fa = FreeAp::<OptionF, i32>::pure(21);
266        let result = FreeAp::ap(ff, fa).retract();
267        assert_eq!(result, Some(42));
268    }
269
270    #[test]
271    fn ap_lift_lift() {
272        let ff = FreeAp::<OptionF, Box<dyn Fn(i32) -> i32>>::pure(
273            Box::new(|x| x + 100) as Box<dyn Fn(i32) -> i32>
274        );
275        let fa = FreeAp::<OptionF, i32>::lift_f(Some(5));
276        let result = FreeAp::ap(ff, fa).retract();
277        assert_eq!(result, Some(105));
278    }
279
280    #[test]
281    fn count_effects_pure() {
282        let fa = FreeAp::<OptionF, i32>::pure(42);
283        assert_eq!(fa.count_effects(), 0);
284    }
285
286    #[test]
287    fn count_effects_single() {
288        let fa = FreeAp::<OptionF, i32>::lift_f(Some(1));
289        assert_eq!(fa.count_effects(), 1);
290    }
291
292    #[test]
293    fn count_effects_fmapped() {
294        let fa = FreeAp::<OptionF, i32>::lift_f(Some(1)).fmap(|x| x + 1);
295        assert_eq!(fa.count_effects(), 1);
296    }
297
298    #[test]
299    fn count_effects_ap() {
300        let ff =
301            FreeAp::<OptionF, Box<dyn Fn(i32) -> String>>::pure(
302                Box::new(|x: i32| format!("{x}")) as Box<dyn Fn(i32) -> String>
303            );
304        let fa = FreeAp::<OptionF, i32>::lift_f(Some(5));
305        let apped = FreeAp::ap(ff, fa);
306        // pure contributes 0, lift_f contributes 1
307        assert_eq!(apped.count_effects(), 1);
308    }
309
310    #[test]
311    fn fmap_identity() {
312        let fa = FreeAp::<OptionF, i32>::lift_f(Some(7));
313        let mapped = fa.fmap(|x| x);
314        let result = mapped.retract();
315        assert_eq!(result, Some(7));
316    }
317
318    #[test]
319    fn fmap_composition() {
320        let f = |x: i32| x + 1;
321        let g = |x: i32| x * 2;
322
323        let left = FreeAp::<OptionF, i32>::lift_f(Some(3))
324            .fmap(move |a| g(f(a)))
325            .retract();
326        let right = FreeAp::<OptionF, i32>::lift_f(Some(3))
327            .fmap(f)
328            .fmap(g)
329            .retract();
330        assert_eq!(left, right);
331    }
332
333    #[test]
334    fn multiple_fmaps() {
335        let fa = FreeAp::<OptionF, i32>::lift_f(Some(2))
336            .fmap(|x| x * 10)
337            .fmap(|x| x + 5);
338        let result = fa.retract();
339        assert_eq!(result, Some(25)); // 2*10+5
340    }
341}
342
343#[cfg(test)]
344mod law_tests {
345    use super::*;
346    use karpal_core::hkt::OptionF;
347    use proptest::prelude::*;
348
349    proptest! {
350        // Functor identity: fmap(id)(x) == x
351        #[test]
352        fn functor_identity(a in any::<i32>()) {
353            let original = FreeAp::<OptionF, i32>::lift_f(Some(a)).retract();
354            let mapped = FreeAp::<OptionF, i32>::lift_f(Some(a)).fmap(|x| x).retract();
355            prop_assert_eq!(original, mapped);
356        }
357
358        // Functor composition: fmap(g . f) == fmap(f) . fmap(g)
359        #[test]
360        fn functor_composition(a in any::<i32>()) {
361            let f = |x: i32| x.wrapping_add(1);
362            let g = |x: i32| x.wrapping_mul(2);
363
364            let left = FreeAp::<OptionF, i32>::lift_f(Some(a))
365                .fmap(move |x| g(f(x)))
366                .retract();
367            let right = FreeAp::<OptionF, i32>::lift_f(Some(a))
368                .fmap(f)
369                .fmap(g)
370                .retract();
371            prop_assert_eq!(left, right);
372        }
373
374        // Applicative identity: ap(pure(id), x) == x
375        #[test]
376        fn applicative_identity(a in any::<i32>()) {
377            let id_fn = FreeAp::<OptionF, Box<dyn Fn(i32) -> i32>>::pure(
378                Box::new(|x| x) as Box<dyn Fn(i32) -> i32>,
379            );
380            let fa = FreeAp::<OptionF, i32>::lift_f(Some(a));
381            let result = FreeAp::ap(id_fn, fa).retract();
382            let expected = FreeAp::<OptionF, i32>::lift_f(Some(a)).retract();
383            prop_assert_eq!(result, expected);
384        }
385
386        // Applicative homomorphism: ap(pure(f), pure(x)) == pure(f(x))
387        #[test]
388        fn applicative_homomorphism(a in any::<i32>()) {
389            let ff = FreeAp::<OptionF, Box<dyn Fn(i32) -> i32>>::pure(
390                Box::new(|x: i32| x.wrapping_mul(3)) as Box<dyn Fn(i32) -> i32>,
391            );
392            let fa = FreeAp::<OptionF, i32>::pure(a);
393            let left = FreeAp::ap(ff, fa).retract();
394            let right = FreeAp::<OptionF, i32>::pure(a.wrapping_mul(3)).retract();
395            prop_assert_eq!(left, right);
396        }
397    }
398}
karpal_free/free_ap.rs

karpal_free/
free_ap.rs
