karpal_recursion/
nu.rs

1#[cfg(feature = "std")]
2use std::boxed::Box;
3
4#[cfg(all(not(feature = "std"), feature = "alloc"))]
5use alloc::boxed::Box;
6
7use karpal_core::functor::Functor;
8use karpal_core::hkt::HKT;
9
10use crate::fix::Fix;
11use crate::schemes::ana;
12
13/// The greatest fixed point of a functor `F`.
14///
15/// `Nu<F, Seed>` represents a potentially infinite corecursive structure.
16/// It stores a seed value and a coalgebra that can observe one layer at a time.
17///
18/// The `Seed` type parameter is exposed because Rust lacks existential types.
19/// This is the same pragmatic compromise used by `Lan` in karpal-free.
20#[allow(clippy::type_complexity)]
21pub struct Nu<F: HKT, Seed> {
22    pub seed: Seed,
23    pub coalgebra: Box<dyn Fn(&Seed) -> F::Of<Seed>>,
24}
25
26impl<F: HKT, Seed> Nu<F, Seed> {
27    /// Create a `Nu` from a seed and a coalgebra.
28    pub fn new(seed: Seed, coalgebra: impl Fn(&Seed) -> F::Of<Seed> + 'static) -> Self {
29        Nu {
30            seed,
31            coalgebra: Box::new(coalgebra),
32        }
33    }
34
35    /// Apply the coalgebra once to observe one layer.
36    pub fn observe(&self) -> F::Of<Seed> {
37        (self.coalgebra)(&self.seed)
38    }
39
40    /// Convert to `Fix<F>` by fully unfolding via anamorphism.
41    ///
42    /// This will diverge for truly infinite structures — only call on
43    /// coalgebras that eventually terminate.
44    pub fn to_fix(self) -> Fix<F>
45    where
46        F: Functor,
47        Seed: Clone,
48    {
49        let coalg = self.coalgebra;
50        ana(|s: Seed| coalg(&s), self.seed)
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57    use karpal_core::hkt::OptionF;
58
59    #[test]
60    fn observe_once() {
61        let nu = Nu::<OptionF, u32>::new(3, |&s| if s == 0 { None } else { Some(s - 1) });
62        assert_eq!(nu.observe(), Some(2));
63    }
64
65    #[test]
66    fn observe_at_zero() {
67        let nu = Nu::<OptionF, u32>::new(0, |&s| if s == 0 { None } else { Some(s - 1) });
68        assert_eq!(nu.observe(), None);
69    }
70
71    #[test]
72    fn to_fix_converts() {
73        let nu = Nu::<OptionF, u32>::new(3, |&s| if s == 0 { None } else { Some(s - 1) });
74        let fixed = nu.to_fix();
75        // Should be Succ(Succ(Succ(Zero))) = 3
76        fn count(f: Fix<OptionF>) -> u32 {
77            match f.unfix() {
78                None => 0,
79                Some(pred) => 1 + count(pred),
80            }
81        }
82        assert_eq!(count(fixed), 3);
83    }
84}
karpal_recursion/nu.rs

karpal_recursion/
nu.rs
