karpal_recursion/
fix.rs

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

karpal_recursion/
fix.rs
