karpal_recursion/
fix.rs

1#[cfg(feature = "std")]
2use std::rc::Rc;
3
4#[cfg(all(not(feature = "std"), feature = "alloc"))]
5use alloc::rc::Rc;
6
7use core::marker::PhantomData;
8
9use karpal_core::functor::Functor;
10use karpal_core::hkt::HKT;
11
12/// The fixed point of a functor `F`.
13///
14/// `Fix<F>` ties the recursive knot: `Fix<F> ≅ F<Fix<F>>`.
15/// It is the core type for recursion schemes — catamorphisms fold
16/// a `Fix<F>` down, anamorphisms build one up.
17///
18/// Uses `Rc` for indirection, which makes cloning cheap (reference count
19/// bump). This is essential for paramorphism, which needs to both
20/// preserve and consume each subterm.
21pub struct Fix<F: HKT>(Rc<F::Of<Fix<F>>>);
22
23impl<F: HKT> Clone for Fix<F> {
24    fn clone(&self) -> Self {
25        Fix(Rc::clone(&self.0))
26    }
27}
28
29impl<F: HKT> Fix<F> {
30    /// Wrap one layer of `F<Fix<F>>` into `Fix<F>`.
31    pub fn new(f: F::Of<Fix<F>>) -> Self {
32        Fix(Rc::new(f))
33    }
34
35    /// Unwrap one layer, consuming the `Fix`.
36    ///
37    /// If this is the sole owner, the inner value is moved out.
38    /// Otherwise a shallow clone is made (each child `Fix` inside
39    /// is `Rc`-cloned, which is O(1)).
40    pub fn unfix(self) -> F::Of<Fix<F>>
41    where
42        F::Of<Fix<F>>: Clone,
43    {
44        match Rc::try_unwrap(self.0) {
45            Ok(val) => val,
46            Err(rc) => (*rc).clone(),
47        }
48    }
49
50    /// Borrow one layer without consuming.
51    pub fn unfix_ref(&self) -> &F::Of<Fix<F>> {
52        &self.0
53    }
54}
55
56/// `Mu<F>` is the least fixed point — structurally identical to `Fix<F>` in Rust,
57/// since Rust cannot enforce finiteness at the type level.
58pub type Mu<F> = Fix<F>;
59
60/// HKT marker for `Fix<F>`. Primarily used for type-level programming.
61pub struct FixF<F: HKT>(PhantomData<F>);
62
63impl<F: HKT> HKT for FixF<F> {
64    type Of<T> = Fix<F>;
65}
66
67impl<F: HKT + Functor> Functor for FixF<F> {
68    fn fmap<A, B>(fa: Fix<F>, _f: impl Fn(A) -> B) -> Fix<F> {
69        fa
70    }
71}
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76    use karpal_core::hkt::OptionF;
77
78    fn zero() -> Fix<OptionF> {
79        Fix::new(None)
80    }
81
82    fn succ(n: Fix<OptionF>) -> Fix<OptionF> {
83        Fix::new(Some(n))
84    }
85
86    fn nat(n: u32) -> Fix<OptionF> {
87        let mut result = zero();
88        for _ in 0..n {
89            result = succ(result);
90        }
91        result
92    }
93
94    fn to_u32(n: Fix<OptionF>) -> u32 {
95        match n.unfix() {
96            None => 0,
97            Some(pred) => 1 + to_u32(pred),
98        }
99    }
100
101    #[test]
102    fn fix_unfix_roundtrip() {
103        assert_eq!(to_u32(nat(5)), 5);
104    }
105
106    #[test]
107    fn zero_is_none() {
108        let z = zero();
109        assert!(z.unfix_ref().is_none());
110    }
111
112    #[test]
113    fn succ_is_some() {
114        let one = succ(zero());
115        assert!(one.unfix_ref().is_some());
116    }
117
118    #[test]
119    fn mu_is_fix() {
120        let n: Mu<OptionF> = nat(3);
121        assert_eq!(to_u32(n), 3);
122    }
123
124    #[test]
125    fn clone_fix() {
126        let n = nat(4);
127        let n2 = n.clone();
128        assert_eq!(to_u32(n), 4);
129        assert_eq!(to_u32(n2), 4);
130    }
131}
karpal_recursion/fix.rs

karpal_recursion/
fix.rs
