fp_library/types.rs
1//! Concrete data types, their corresponding implementations and type aliases.
2//!
3//! This module provides implementations of various functional programming
4//! data structures and wrappers, including `Identity`, `Lazy`, and extensions
5//! for standard library types like `Option` and `Result`.
6//!
7//! ### Examples
8//!
9//! ```
10//! use fp_library::types::Identity;
11//!
12//! let x = Identity(5);
13//! assert_eq!(x.0, 5);
14//! ```
15
16/// Thread-safe reference-counted pointer abstraction using [`Arc`](std::sync::Arc).
17///
18/// Provides trait implementations for using `Arc` in the library's pointer abstraction hierarchy.
19///
20/// ### Examples
21///
22/// ```
23/// use fp_library::{brands::*, functions::*};
24///
25/// let ptr = send_ref_counted_pointer_new::<ArcBrand, _>(42);
26/// assert_eq!(*ptr, 42);
27/// ```
28pub mod arc_ptr;
29
30/// Efficient queue-like structure with O(1) append and O(1) amortized uncons.
31///
32/// Implements the ["Reflection without Remorse"](http://okmij.org/ftp/Haskell/zseq.pdf) data structure used to enable O(1) left-associated [`bind`](crate::functions::bind) operations in the [`Free`] monad.
33///
34/// ### Examples
35///
36/// ```
37/// use fp_library::types::cat_list::CatList;
38///
39/// let list = CatList::singleton(1)
40/// .snoc(2)
41/// .snoc(3)
42/// .append(CatList::singleton(4));
43///
44/// let mut result = Vec::new();
45/// let mut current = list;
46/// while let Some((head, tail)) = current.uncons() {
47/// result.push(head);
48/// current = tail;
49/// }
50/// assert_eq!(result, vec![1, 2, 3, 4]);
51/// ```
52pub mod cat_list;
53
54/// Wrapper for endofunctions (functions `a -> a`) with [`Semigroup`](crate::classes::semigroup::Semigroup) and [`Monoid`](crate::classes::monoid::Monoid) instances based on function composition.
55///
56/// Used to treat function composition as a monoidal operation where [`append`](crate::functions::append) composes functions and [`empty`](crate::functions::empty) is the identity function.
57pub mod endofunction;
58
59/// Wrapper for endomorphisms (morphisms `c a a` in a category) with [`Semigroup`](crate::classes::semigroup::Semigroup) and [`Monoid`](crate::classes::monoid::Monoid) instances based on categorical composition.
60///
61/// A more general form of `Endofunction` that works with any [`Category`](crate::classes::category::Category), not just functions.
62pub mod endomorphism;
63
64/// Reference-counted cloneable function wrappers with [`Semigroupoid`](crate::classes::semigroupoid::Semigroupoid) and [`Category`](crate::classes::category::Category) instances.
65///
66/// Provides the [`FnBrand`](crate::brands::FnBrand) abstraction for wrapping closures in `Rc<dyn Fn>` or `Arc<dyn Fn>` for use in higher-kinded contexts.
67pub mod fn_brand;
68
69/// Stack-safe Free monad over a functor with O(1) [`bind`](crate::functions::bind) operations.
70///
71/// Enables building computation chains without stack overflow by using a catenable list of continuations. Note: requires `'static` types and cannot implement the library's HKT traits due to type erasure.
72///
73/// ## Comparison with PureScript
74///
75/// This implementation is based on the PureScript [`Control.Monad.Free`](https://github.com/purescript/purescript-free/blob/master/src/Control/Monad/Free.purs) module
76/// and the ["Reflection without Remorse"](http://okmij.org/ftp/Haskell/zseq.pdf) technique. It shares the same core algorithmic properties (O(1) bind, stack safety)
77/// but differs significantly in its intended use case and API surface.
78///
79/// ### Key Differences
80///
81/// 1. **Interpretation Strategy**:
82/// * **PureScript**: Designed as a generic Abstract Syntax Tree (AST) that can be interpreted into *any* target
83/// monad using `runFree` or `foldFree` by providing a natural transformation at runtime.
84/// * **Rust**: Designed primarily for **stack-safe execution** of computations. The interpretation logic is
85/// baked into the [`Runnable`](crate::classes::runnable::Runnable) trait implemented by the functor `F`.
86/// The [`Free::run`] method relies on `F` knowing how to "run" itself.
87///
88/// 2. **API Surface**:
89/// * **PureScript**: Rich API including `liftF`, `hoistFree`, `resume`, `foldFree`.
90/// * **Rust**: Minimal API focused on construction (`pure`, `roll`, `bind`) and execution (`run`).
91/// * `liftF` is missing (use `roll` + `map`).
92/// * `resume` is missing (cannot inspect the computation step-by-step).
93/// * `hoistFree` is missing.
94///
95/// 3. **Terminology**:
96/// * Rust's `Free::roll` corresponds to PureScript's `wrap`.
97///
98/// ### Capabilities and Limitations
99///
100/// **What it CAN do:**
101/// * Provide stack-safe recursion for monadic computations (trampolining).
102/// * Prevent stack overflows when chaining many `bind` operations.
103/// * Execute self-describing effects (like [`Thunk`]).
104///
105/// **What it CANNOT do (easily):**
106/// * Act as a generic DSL where the interpretation is decoupled from the operation type.
107/// * *Example*: You cannot easily define a `DatabaseOp` enum and interpret it differently for
108/// production (SQL) and testing (InMemory) using this `Free` implementation, because
109/// `DatabaseOp` must implement a single `Runnable` trait.
110/// * Inspect the structure of the computation (introspection) via `resume`.
111///
112/// ### Lifetimes and Memory Management
113///
114/// * **PureScript**: Relies on a garbage collector and `unsafeCoerce`. This allows it to ignore
115/// lifetimes and ownership, enabling a simpler implementation that supports all types.
116/// * **Rust**: Relies on ownership and `Box<dyn Any>` for type erasure. `Any` requires `'static`
117/// to ensure memory safety (preventing use-after-free of references). This forces `Free` to
118/// only work with `'static` types, preventing it from implementing the library's HKT traits
119/// which require lifetime polymorphism.
120///
121/// ### Examples
122///
123/// ```
124/// use fp_library::{brands::*, types::*};
125///
126/// // ✅ CAN DO: Stack-safe recursion
127/// let free = Free::<ThunkBrand, _>::pure(42)
128/// .bind(|x| Free::pure(x + 1));
129/// ```
130pub mod free;
131
132/// Trivial wrapper that contains a single value.
133///
134/// The simplest possible container type, often used as a base case for higher-kinded types or when a container is required but no additional effect is needed.
135pub mod identity;
136
137/// Memoized lazy evaluation with shared cache semantics.
138///
139/// Computes a value at most once on first access and caches the result. All clones share the same cache. Available in both single-threaded [`RcLazy`] and thread-safe [`ArcLazy`] variants.
140pub mod lazy;
141
142/// Functional programming trait implementations for the standard library [`Option`] type.
143///
144/// Extends `Option` with [`Functor`](crate::classes::functor::Functor), [`Monad`](crate::classes::semimonad::Semimonad), [`Foldable`](crate::classes::foldable::Foldable), [`Traversable`](crate::classes::traversable::Traversable), [`Filterable`](crate::classes::filterable::Filterable), and [`Witherable`](crate::classes::witherable::Witherable) instances.
145pub mod option;
146
147/// Two-value container with [`Bifunctor`](crate::classes::bifunctor::Bifunctor) and dual [`Functor`](crate::classes::functor::Functor) instances.
148///
149/// Can be used as a bifunctor over both values, or as a functor/monad by fixing either the first value [`PairWithFirstBrand`](crate::brands::PairWithFirstBrand) or second value [`PairWithSecondBrand`](crate::brands::PairWithSecondBrand).
150pub mod pair;
151
152/// Single-threaded reference-counted pointer abstraction using [`Rc`](std::rc::Rc).
153///
154/// Provides trait implementations for using `Rc` in the library's pointer abstraction hierarchy. Not thread-safe; use [`ArcBrand`](crate::brands::ArcBrand) for multi-threaded contexts.
155///
156/// ### Examples
157///
158/// ```
159/// use fp_library::{brands::*, functions::*};
160///
161/// let ptr = pointer_new::<RcBrand, _>(42);
162/// assert_eq!(*ptr, 42);
163/// ```
164pub mod rc_ptr;
165
166/// Functional programming trait implementations for the standard library [`Result`] type.
167///
168/// Extends `Result` with dual functor/monad instances: [`ResultWithErrBrand`](crate::brands::ResultWithErrBrand) (standard Result monad) functors over the success value, while [`ResultWithOkBrand`](crate::brands::ResultWithOkBrand) functors over the error value.
169pub mod result;
170
171/// Thread-safe wrapper for endofunctions with [`Semigroup`](crate::classes::semigroup::Semigroup) and [`Monoid`](crate::classes::monoid::Monoid) instances.
172///
173/// The `Send + Sync` counterpart to [`Endofunction`], wrapping functions that can be safely shared across threads.
174pub mod send_endofunction;
175
176/// Control type representing Loop/Done states for tail-recursive computations.
177///
178/// Used by [`MonadRec`](crate::classes::monad_rec::MonadRec) to implement stack-safe tail recursion. [`Step::Loop`] continues iteration, while [`Step::Done`] terminates with a result.
179///
180/// ### Examples
181///
182/// ```
183/// use fp_library::types::*;
184///
185/// // Count down from n to 0, accumulating the sum
186/// fn sum_to_zero(n: i32, acc: i32) -> Step<(i32, i32), i32> {
187/// if n <= 0 {
188/// Step::Done(acc)
189/// } else {
190/// Step::Loop((n - 1, acc + n))
191/// }
192/// }
193/// ```
194pub mod step;
195
196/// [`Semigroup`](crate::classes::semigroup::Semigroup) and [`Monoid`](crate::classes::monoid::Monoid) instances for the standard library [`String`] type.
197///
198/// Provides string concatenation as a monoidal operation with the empty string as the identity element.
199pub mod string;
200
201/// Deferred, non-memoized computation with higher-kinded type support.
202///
203/// Builds computation chains without stack safety guarantees but supports borrowing and lifetime polymorphism. Each call to [`Thunk::run`] re-executes the computation. For stack-safe alternatives, use [`Trampoline`].
204pub mod thunk;
205
206/// Stack-safe computation type with guaranteed safety for unlimited recursion depth.
207///
208/// Built on the [`Free`] monad with O(1) [`bind`](crate::functions::bind) operations. Provides complete stack safety at the cost of requiring `'static` types. Use this for deep recursion and heavy monadic pipelines.
209///
210/// ### Examples
211///
212/// ```
213/// use fp_library::types::*;
214///
215/// let task = Trampoline::new(|| 1 + 1)
216/// .bind(|x| Trampoline::new(move || x * 2))
217/// .bind(|x| Trampoline::new(move || x + 10));
218///
219/// assert_eq!(task.run(), 14);
220/// ```
221pub mod trampoline;
222
223/// Memoized lazy evaluation for fallible computations.
224///
225/// Computes a [`Result`] at most once and caches either the success value or error. All clones share the same cache. Available in both single-threaded [`RcTryLazy`] and thread-safe [`ArcTryLazy`] variants.
226pub mod try_lazy;
227
228/// Deferred, non-memoized fallible computation with higher-kinded type support.
229///
230/// The fallible counterpart to [`Thunk`]. Each call to [`TryThunk::run`] re-executes the computation and returns a [`Result`]. Supports borrowing and lifetime polymorphism.
231pub mod try_thunk;
232
233/// Stack-safe fallible computation type with guaranteed safety for unlimited recursion depth.
234///
235/// Wraps [`Trampoline<Result<A, E>>`](crate::types::Trampoline) with ergonomic combinators for error handling. Provides complete stack safety for fallible computations that may recurse deeply.
236///
237/// ### Examples
238///
239/// ```
240/// use fp_library::types::*;
241///
242/// let task: TryTrampoline<i32, String> = TryTrampoline::ok(10)
243/// .map(|x| x * 2)
244/// .bind(|x| TryTrampoline::ok(x + 5));
245///
246/// assert_eq!(task.run(), Ok(25));
247/// ```
248pub mod try_trampoline;
249
250/// Functional programming trait implementations for the standard library [`Vec`] type.
251///
252/// Extends `Vec` with [`Functor`](crate::classes::functor::Functor), [`Monad`](crate::classes::semimonad::Semimonad), [`Foldable`](crate::classes::foldable::Foldable), [`Traversable`](crate::classes::traversable::Traversable), [`Filterable`](crate::classes::filterable::Filterable), [`Witherable`](crate::classes::witherable::Witherable), and parallel folding instances.
253pub mod vec;
254
255pub use cat_list::CatList;
256pub use endofunction::Endofunction;
257pub use endomorphism::Endomorphism;
258pub use free::Free;
259pub use identity::Identity;
260pub use lazy::{ArcLazy, ArcLazyConfig, Lazy, LazyConfig, RcLazy, RcLazyConfig};
261pub use pair::Pair;
262pub use send_endofunction::SendEndofunction;
263pub use step::Step;
264pub use thunk::Thunk;
265pub use trampoline::Trampoline;
266pub use try_lazy::{ArcTryLazy, RcTryLazy, TryLazy};
267pub use try_thunk::TryThunk;
268pub use try_trampoline::TryTrampoline;