karpal_free/
free_alt.rs

1#[cfg(feature = "std")]
2use std::{vec, vec::Vec};
3
4#[cfg(all(not(feature = "std"), feature = "alloc"))]
5use alloc::{vec, vec::Vec};
6
7use core::marker::PhantomData;
8
9use karpal_core::alternative::Alternative;
10use karpal_core::hkt::HKT;
11
12use crate::free_ap::FreeAp;
13
14/// Free Alternative Functor — build alternative computations as data.
15///
16/// `FreeAlt<F, A>` represents a choice among zero or more applicative
17/// computations, each built from `FreeAp<F, A>`. This gives a free
18/// `Alternative` instance for any functor `F`.
19///
20/// ```text
21/// FreeAlt f a ≅ [FreeAp f a]
22/// ```
23///
24/// An empty list represents `zero` (failure), a single element is a
25/// single computation, and multiple elements represent `alt` (choice).
26///
27/// # Interpretation
28///
29/// `retract` collapses the structure into `F`'s own Alternative,
30/// combining branches with `F::alt` and handling empty lists with
31/// `F::zero`.
32pub struct FreeAlt<F: HKT + 'static, A: 'static> {
33    alternatives: Vec<FreeAp<F, A>>,
34}
35
36impl<F: HKT + 'static, A: 'static> FreeAlt<F, A> {
37    /// Wrap a pure value.
38    pub fn pure(a: A) -> Self {
39        FreeAlt {
40            alternatives: vec![FreeAp::pure(a)],
41        }
42    }
43
44    /// Lift a single effect into the free alternative.
45    pub fn lift_f(fa: F::Of<A>) -> Self
46    where
47        A: Clone,
48        F::Of<A>: 'static,
49    {
50        FreeAlt {
51            alternatives: vec![FreeAp::lift_f(fa)],
52        }
53    }
54
55    /// The empty alternative (zero / failure).
56    pub fn zero() -> Self {
57        FreeAlt {
58            alternatives: Vec::new(),
59        }
60    }
61
62    /// Combine two alternatives (choice).
63    pub fn alt(self, other: FreeAlt<F, A>) -> Self {
64        let mut alts = self.alternatives;
65        alts.extend(other.alternatives);
66        FreeAlt { alternatives: alts }
67    }
68
69    /// Map a function over all branches.
70    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> FreeAlt<F, B> {
71        // We need to share f across all branches.
72        #[cfg(all(not(feature = "std"), feature = "alloc"))]
73        use alloc::rc::Rc;
74        #[cfg(feature = "std")]
75        use std::rc::Rc;
76
77        let f = Rc::new(f);
78        let alternatives = self
79            .alternatives
80            .into_iter()
81            .map(|branch| {
82                let f = f.clone();
83                branch.fmap(move |a| f(a))
84            })
85            .collect();
86        FreeAlt { alternatives }
87    }
88
89    /// Interpret by collapsing into `F`'s own Alternative.
90    ///
91    /// Requires `F: Alternative`.
92    pub fn retract(self) -> F::Of<A>
93    where
94        F: Alternative,
95    {
96        let mut iter = self.alternatives.into_iter();
97        match iter.next() {
98            None => F::zero(),
99            Some(first) => {
100                let mut result = first.retract();
101                for branch in iter {
102                    result = F::alt(result, branch.retract());
103                }
104                result
105            }
106        }
107    }
108
109    /// Count the total number of alternative branches.
110    pub fn count_alternatives(&self) -> usize {
111        self.alternatives.len()
112    }
113
114    /// Count the total number of effects across all branches.
115    pub fn count_effects(&self) -> usize {
116        self.alternatives.iter().map(|b| b.count_effects()).sum()
117    }
118}
119
120/// Marker type for `FreeAlt<F, _>`.
121///
122/// Note: Cannot implement `HKT`, `Functor`, `Alt`, or `Plus` due to Rust's
123/// GAT limitations (`type Of<T>` cannot add `T: 'static` in impl when trait
124/// doesn't have it). Use `FreeAlt` methods directly.
125pub struct FreeAltF<F: HKT + 'static>(PhantomData<F>);
126
127#[cfg(test)]
128mod tests {
129    use super::*;
130    use karpal_core::hkt::OptionF;
131
132    #[test]
133    fn pure_retract() {
134        let fa = FreeAlt::<OptionF, i32>::pure(42);
135        let result = fa.retract();
136        assert_eq!(result, Some(42));
137    }
138
139    #[test]
140    fn lift_f_retract() {
141        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(10));
142        let result = fa.retract();
143        assert_eq!(result, Some(10));
144    }
145
146    #[test]
147    fn zero_retract() {
148        let fa = FreeAlt::<OptionF, i32>::zero();
149        let result = fa.retract();
150        assert_eq!(result, None);
151    }
152
153    #[test]
154    fn alt_some_none() {
155        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(1));
156        let fb = FreeAlt::<OptionF, i32>::lift_f(None);
157        // Both are Some(1) and None; alt picks first non-None
158        let result = fa.alt(fb).retract();
159        assert_eq!(result, Some(1));
160    }
161
162    #[test]
163    fn alt_none_some() {
164        let fa = FreeAlt::<OptionF, i32>::lift_f(None);
165        let fb = FreeAlt::<OptionF, i32>::lift_f(Some(2));
166        let result = fa.alt(fb).retract();
167        assert_eq!(result, Some(2));
168    }
169
170    #[test]
171    fn alt_none_none() {
172        let fa = FreeAlt::<OptionF, i32>::lift_f(None);
173        let fb = FreeAlt::<OptionF, i32>::lift_f(None);
174        let result = fa.alt(fb).retract();
175        assert_eq!(result, None);
176    }
177
178    #[test]
179    fn alt_some_some() {
180        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(1));
181        let fb = FreeAlt::<OptionF, i32>::lift_f(Some(2));
182        // Option::alt takes the first Some
183        let result = fa.alt(fb).retract();
184        assert_eq!(result, Some(1));
185    }
186
187    #[test]
188    fn fmap_alt() {
189        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(5)).fmap(|x| x * 2);
190        let result = fa.retract();
191        assert_eq!(result, Some(10));
192    }
193
194    #[test]
195    fn count_alternatives_zero() {
196        let fa = FreeAlt::<OptionF, i32>::zero();
197        assert_eq!(fa.count_alternatives(), 0);
198    }
199
200    #[test]
201    fn count_alternatives_single() {
202        let fa = FreeAlt::<OptionF, i32>::pure(1);
203        assert_eq!(fa.count_alternatives(), 1);
204    }
205
206    #[test]
207    fn count_alternatives_multiple() {
208        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(1))
209            .alt(FreeAlt::lift_f(Some(2)))
210            .alt(FreeAlt::lift_f(Some(3)));
211        assert_eq!(fa.count_alternatives(), 3);
212    }
213
214    #[test]
215    fn count_effects_across_branches() {
216        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(1))
217            .alt(FreeAlt::pure(2))
218            .alt(FreeAlt::lift_f(Some(3)));
219        // lift_f: 1 effect, pure: 0 effects, lift_f: 1 effect
220        assert_eq!(fa.count_effects(), 2);
221    }
222
223    #[test]
224    fn alt_multiple() {
225        let fa = FreeAlt::<OptionF, i32>::lift_f(Some(1));
226        let fb = FreeAlt::<OptionF, i32>::lift_f(Some(2));
227        let result = fa.alt(fb);
228        assert_eq!(result.count_alternatives(), 2);
229    }
230}
231
232#[cfg(test)]
233mod law_tests {
234    use super::*;
235    use karpal_core::hkt::OptionF;
236    use proptest::prelude::*;
237
238    proptest! {
239        // Functor identity
240        #[test]
241        fn functor_identity(a in any::<i32>()) {
242            let original = FreeAlt::<OptionF, i32>::lift_f(Some(a)).retract();
243            let mapped = FreeAlt::<OptionF, i32>::lift_f(Some(a)).fmap(|x| x).retract();
244            prop_assert_eq!(original, mapped);
245        }
246
247        // Functor composition
248        #[test]
249        fn functor_composition(a in any::<i32>()) {
250            let f = |x: i32| x.wrapping_add(1);
251            let g = |x: i32| x.wrapping_mul(2);
252
253            let left = FreeAlt::<OptionF, i32>::lift_f(Some(a))
254                .fmap(move |x| g(f(x)))
255                .retract();
256            let right = FreeAlt::<OptionF, i32>::lift_f(Some(a))
257                .fmap(f)
258                .fmap(g)
259                .retract();
260            prop_assert_eq!(left, right);
261        }
262
263        // Alt associativity
264        #[test]
265        fn alt_associativity(a in any::<i32>(), b in any::<i32>(), c in any::<i32>()) {
266            let left = FreeAlt::<OptionF, i32>::lift_f(Some(a))
267                .alt(FreeAlt::lift_f(Some(b)))
268                .alt(FreeAlt::lift_f(Some(c)))
269                .retract();
270            let right = FreeAlt::<OptionF, i32>::lift_f(Some(a))
271                .alt(FreeAlt::lift_f(Some(b)).alt(FreeAlt::lift_f(Some(c))))
272                .retract();
273            prop_assert_eq!(left, right);
274        }
275
276        // Plus identity: alt(zero, x) == x and alt(x, zero) == x
277        #[test]
278        fn plus_left_identity(a in any::<i32>()) {
279            let left = FreeAlt::<OptionF, i32>::zero()
280                .alt(FreeAlt::lift_f(Some(a)))
281                .retract();
282            let right = FreeAlt::<OptionF, i32>::lift_f(Some(a)).retract();
283            prop_assert_eq!(left, right);
284        }
285
286        #[test]
287        fn plus_right_identity(a in any::<i32>()) {
288            let left = FreeAlt::<OptionF, i32>::lift_f(Some(a))
289                .alt(FreeAlt::zero())
290                .retract();
291            let right = FreeAlt::<OptionF, i32>::lift_f(Some(a)).retract();
292            prop_assert_eq!(left, right);
293        }
294    }
295}
karpal_free/free_alt.rs

karpal_free/
free_alt.rs
