karpal_recursion/
nu.rs

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

karpal_recursion/
nu.rs
