fp_library/types/

trampoline.rs

//! Stack-safe computation type with guaranteed safety for unlimited recursion depth.
//!
//! Built on the [`Free`](crate::types::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.
//!
//! ### Examples
//!
//! ```
//! use fp_library::types::*;
//!
//! let task = Trampoline::new(|| 1 + 1)
//!     .bind(|x| Trampoline::new(move || x * 2))
//!     .bind(|x| Trampoline::new(move || x + 10));
//!
//! assert_eq!(task.evaluate(), 14);
//! ```

#[fp_macros::document_module]
mod inner {
	use crate::{
		brands::ThunkBrand,
		classes::Deferrable,
		types::{Free, Lazy, LazyConfig, Step, Thunk},
	};
	use fp_macros::{document_fields, document_parameters, document_type_parameters};

	/// A lazy, stack-safe computation that produces a value of type `A`.
	///
	/// `Trampoline` is the "heavy-duty" monadic type for deferred computations that
	/// require **guaranteed stack safety**. It is built on [`Free<Thunk, A>`] with
	/// [`CatList`](crate::types::CatList)-based bind stack, ensuring O(1) [`bind`](crate::functions::bind)
	/// operations and unlimited recursion depth without stack overflow.
	///
	/// # Requirements
	///
	/// - `A: 'static + Send` — Required due to type erasure via [`Box<dyn Any>`].
	///
	/// # Guarantees
	///
	/// - **Stack safe**: Will not overflow regardless of recursion depth.
	/// - **O(1) bind**: Left-associated `bind` chains don't degrade.
	/// - **Lazy**: Computation is deferred until [`Trampoline::evaluate`] is called.
	///
	/// # When to Use `Trampoline` vs [`Thunk`]
	///
	/// - Use **`Trampoline<A>`** for deep recursion, heavy monadic pipelines.
	/// - Use **`Thunk<'a, A>`** for HKT integration, borrowed references, glue code.
	///
	/// # Memoization
	///
	/// `Trampoline` does NOT memoize. Each call to `run` re-evaluates.
	/// For memoization, wrap in [`Lazy`]:
	///
	/// ```rust
	/// use fp_library::types::*;
	///
	/// let lazy: Lazy<i32> = Lazy::<_, RcLazyConfig>::new(|| Trampoline::new(|| 1 + 1).evaluate());
	/// lazy.evaluate(); // Computes
	/// lazy.evaluate(); // Returns cached
	/// ```
	///
	/// ### Type Parameters
	///
	#[document_type_parameters("The type of the value produced by the task.")]
	///
	/// ### Fields
	///
	#[document_fields("The internal `Free` monad representation.")]
	///
	/// ### Examples
	///
	/// ```
	/// use fp_library::types::*;
	///
	/// let task = Trampoline::new(|| 1 + 1)
	///     .bind(|x| Trampoline::new(move || x * 2))
	///     .bind(|x| Trampoline::new(move || x + 10));
	///
	/// assert_eq!(task.evaluate(), 14);
	/// ```
	pub struct Trampoline<A: 'static>(Free<ThunkBrand, A>);

	/// ### Type Parameters
	///
	#[document_type_parameters("The type of the value produced by the task.")]
	#[document_parameters("The `Trampoline` instance.")]
	impl<A: 'static + Send> Trampoline<A> {
		/// Creates a `Trampoline` from an already-computed value.
		///
		/// ### Complexity
		///
		/// O(1) creation, O(1) evaluation
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Parameters
		///
		#[document_parameters("The value to wrap.")]
		///
		/// ### Returns
		///
		/// A `Trampoline` that produces the value `a`.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// let task = Trampoline::pure(42);
		/// assert_eq!(task.evaluate(), 42);
		/// ```
		#[inline]
		pub fn pure(a: A) -> Self {
			Trampoline(Free::pure(a))
		}

		/// Creates a lazy `Trampoline` that computes `f` on first evaluation.
		///
		/// `Trampoline` does NOT memoize — each `evaluate()`
		/// re-evaluates. Use [`Lazy`] for caching.
		///
		/// # Complexity
		/// O(1) creation
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters("The type of the closure.")]
		///
		/// ### Parameters
		///
		#[document_parameters("The closure to execute.")]
		///
		/// ### Returns
		///
		/// A `Trampoline` that executes `f` when run.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// let task = Trampoline::new(|| {
		///     // println!("Computing!");
		///     1 + 1
		/// });
		///
		/// // Nothing printed yet
		/// let result = task.evaluate(); // Prints "Computing!"
		/// ```
		#[inline]
		pub fn new<F>(f: F) -> Self
		where
			F: FnOnce() -> A + 'static,
		{
			Trampoline(Free::wrap(Thunk::new(move || Free::pure(f()))))
		}

		/// Defers the construction of a `Trampoline` itself.
		///
		/// This is critical for stack-safe recursion: instead of
		/// building a chain of `Trampoline`s directly (which grows the stack),
		/// we defer the construction.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters("The type of the closure.")]
		///
		/// ### Parameters
		///
		#[document_parameters("The closure that produces a `Trampoline`.")]
		///
		/// ### Returns
		///
		/// A `Trampoline` that defers the creation of the inner task.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// fn recursive_sum(n: u64, acc: u64) -> Trampoline<u64> {
		///     if n == 0 {
		///         Trampoline::pure(acc)
		///     } else {
		///         // Defer construction to avoid stack growth
		///         Trampoline::defer(move || recursive_sum(n - 1, acc + n))
		///     }
		/// }
		///
		/// // This works for n = 1_000_000 without stack overflow!
		/// let result = recursive_sum(1_000, 0).evaluate();
		/// ```
		#[inline]
		pub fn defer<F>(f: F) -> Self
		where
			F: FnOnce() -> Trampoline<A> + 'static,
		{
			Trampoline(Free::wrap(Thunk::new(move || f().0)))
		}

		/// Monadic bind with O(1) complexity.
		///
		/// Chains computations together. The key property is that
		/// left-associated chains don't degrade to O(n²).
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters(
			"The type of the result of the new task.",
			"The type of the binding function."
		)]
		///
		/// ### Parameters
		///
		#[document_parameters("The function to apply to the result of this task.")]
		///
		/// ### Returns
		///
		/// A new `Trampoline` that chains `f` after this task.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// // This is O(n), not O(n²)
		/// let mut task = Trampoline::pure(0);
		/// for i in 0..100 {
		///     task = task.bind(move |x| Trampoline::pure(x + i));
		/// }
		/// ```
		#[inline]
		pub fn bind<B: 'static + Send, F>(
			self,
			f: F,
		) -> Trampoline<B>
		where
			F: FnOnce(A) -> Trampoline<B> + 'static,
		{
			Trampoline(self.0.bind(move |a| f(a).0))
		}

		/// Functor map: transforms the result without changing structure.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters(
			"The type of the result of the mapping function.",
			"The type of the mapping function."
		)]
		///
		/// ### Parameters
		///
		#[document_parameters("The function to apply to the result of this task.")]
		///
		/// ### Returns
		///
		/// A new `Trampoline` with the transformed result.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// let task = Trampoline::pure(10).map(|x| x * 2);
		/// assert_eq!(task.evaluate(), 20);
		/// ```
		#[inline]
		pub fn map<B: 'static + Send, F>(
			self,
			f: F,
		) -> Trampoline<B>
		where
			F: FnOnce(A) -> B + 'static,
		{
			self.bind(move |a| Trampoline::pure(f(a)))
		}

		/// Forces evaluation and returns the result.
		///
		/// This runs the trampoline loop, iteratively processing
		/// the CatList of continuations without growing the stack.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Parameters
		///
		#[document_parameters]
		///
		/// ### Returns
		///
		/// The result of the computation.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// let task = Trampoline::new(|| 1 + 1);
		/// assert_eq!(task.evaluate(), 2);
		/// ```
		pub fn evaluate(self) -> A {
			self.0.evaluate()
		}

		/// Combines two `Trampoline`s, running both and combining results.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters(
			"The type of the second task's result.",
			"The type of the combined result.",
			"The type of the combining function."
		)]
		///
		/// ### Parameters
		///
		#[document_parameters("The second task.", "The function to combine the results.")]
		///
		/// ### Returns
		///
		/// A new `Trampoline` producing the combined result.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// let t1 = Trampoline::pure(10);
		/// let t2 = Trampoline::pure(20);
		/// let t3 = t1.lift2(t2, |a, b| a + b);
		/// assert_eq!(t3.evaluate(), 30);
		/// ```
		pub fn lift2<B: 'static + Send, C: 'static + Send, F>(
			self,
			other: Trampoline<B>,
			f: F,
		) -> Trampoline<C>
		where
			F: FnOnce(A, B) -> C + 'static,
		{
			self.bind(move |a| other.map(move |b| f(a, b)))
		}

		/// Sequences two `Trampoline`s, discarding the first result.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters("The type of the second task's result.")]
		///
		/// ### Parameters
		///
		#[document_parameters("The second task.")]
		///
		/// ### Returns
		///
		/// A new `Trampoline` that runs both tasks and returns the result of the second.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::*;
		///
		/// let t1 = Trampoline::pure(10);
		/// let t2 = Trampoline::pure(20);
		/// let t3 = t1.then(t2);
		/// assert_eq!(t3.evaluate(), 20);
		/// ```
		pub fn then<B: 'static + Send>(
			self,
			other: Trampoline<B>,
		) -> Trampoline<B> {
			self.bind(move |_| other)
		}

		/// Stack-safe tail recursion within Trampoline.
		///
		/// # Clone Bound
		///
		/// The function `f` must implement `Clone` because each iteration
		/// of the recursion may need its own copy. Most closures naturally
		/// implement `Clone` when all their captures implement `Clone`.
		///
		/// For closures that don't implement `Clone`, use `arc_tail_rec_m`
		/// which wraps the closure in `Arc` internally.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters("The type of the state.", "The type of the step function.")]
		///
		/// ### Parameters
		///
		#[document_parameters(
			"The function that performs one step of the recursion.",
			"The initial state."
		)]
		///
		/// ### Returns
		///
		/// A `Trampoline` that performs the recursion.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::{Trampoline, Step};
		///
		/// // Fibonacci using tail recursion
		/// fn fib(n: u64) -> Trampoline<u64> {
		///     Trampoline::tail_rec_m(|(n, a, b)| {
		///         if n == 0 {
		///             Trampoline::pure(Step::Done(a))
		///         } else {
		///             Trampoline::pure(Step::Loop((n - 1, b, a + b)))
		///         }
		///     }, (n, 0u64, 1u64))
		/// }
		///
		/// assert_eq!(fib(50).evaluate(), 12586269025);
		/// ```
		pub fn tail_rec_m<S: 'static + Send, F>(
			f: F,
			initial: S,
		) -> Self
		where
			F: Fn(S) -> Trampoline<Step<S, A>> + Clone + 'static,
		{
			// Use defer to ensure each step is trampolined.
			fn go<A: 'static + Send, B: 'static + Send, F>(
				f: F,
				a: A,
			) -> Trampoline<B>
			where
				F: Fn(A) -> Trampoline<Step<A, B>> + Clone + 'static,
			{
				let f_clone = f.clone();
				Trampoline::defer(move || {
					f(a).bind(move |step| match step {
						Step::Loop(next) => go(f_clone.clone(), next),
						Step::Done(b) => Trampoline::pure(b),
					})
				})
			}

			go(f, initial)
		}

		/// Arc-wrapped version for non-Clone closures.
		///
		/// Use this when your closure captures non-Clone state.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters("The type of the state.", "The type of the step function.")]
		///
		/// ### Parameters
		///
		#[document_parameters(
			"The function that performs one step of the recursion.",
			"The initial state."
		)]
		///
		/// ### Returns
		///
		/// A `Trampoline` that performs the recursion.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::types::{Trampoline, Step};
		/// use std::sync::{Arc, atomic::{AtomicUsize, Ordering}};
		///
		/// // Closure captures non-Clone state
		/// let counter = Arc::new(AtomicUsize::new(0));
		/// Trampoline::arc_tail_rec_m(move |n| {
		///     counter.fetch_add(1, Ordering::SeqCst);
		///     if n == 0 {
		///         Trampoline::pure(Step::Done(0))
		///     } else {
		///         Trampoline::pure(Step::Loop(n - 1))
		///     }
		/// }, 100);
		/// ```
		pub fn arc_tail_rec_m<S: 'static + Send, F>(
			f: F,
			initial: S,
		) -> Self
		where
			F: Fn(S) -> Trampoline<Step<S, A>> + 'static,
		{
			use std::sync::Arc;
			let f = Arc::new(f);
			let wrapper = move |s: S| {
				let f = Arc::clone(&f);
				f(s)
			};
			Self::tail_rec_m(wrapper, initial)
		}
	}

	/// ### Type Parameters
	///
	#[document_type_parameters(
		"The type of the value produced by the task.",
		"The memoization configuration."
	)]
	impl<A: 'static + Send + Clone, Config: LazyConfig> From<Lazy<'static, A, Config>>
		for Trampoline<A>
	{
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Parameters
		///
		#[document_parameters("The lazy value to convert.")]
		fn from(lazy: Lazy<'static, A, Config>) -> Self {
			Trampoline::new(move || lazy.evaluate().clone())
		}
	}

	/// ### Type Parameters
	///
	#[document_type_parameters("The type of the value produced by the task.")]
	impl<A: 'static + Send> Deferrable<'static> for Trampoline<A> {
		/// Creates a `Trampoline` from a computation that produces it.
		///
		/// ### Type Signature
		///
		#[document_signature]
		///
		/// ### Type Parameters
		///
		#[document_type_parameters("The type of the closure.")]
		///
		/// ### Parameters
		///
		#[document_parameters("A thunk that produces the trampoline.")]
		///
		/// ### Returns
		///
		/// The deferred trampoline.
		///
		/// ### Examples
		///
		/// ```
		/// use fp_library::{brands::*, functions::*, types::*, classes::Deferrable};
		///
		/// let task: Trampoline<i32> = Deferrable::defer(|| Trampoline::pure(42));
		/// assert_eq!(task.evaluate(), 42);
		/// ```
		fn defer<F>(f: F) -> Self
		where
			F: FnOnce() -> Self + 'static,
			Self: Sized,
		{
			Trampoline::defer(f)
		}
	}
}
pub use inner::*;

#[cfg(test)]
mod tests {
	use super::*;
	use crate::types::step::Step;

	/// Tests `Trampoline::pure`.
	///
	/// Verifies that `pure` creates a task that returns the value immediately.
	#[test]
	fn test_task_pure() {
		let task = Trampoline::pure(42);
		assert_eq!(task.evaluate(), 42);
	}

	/// Tests `Trampoline::new`.
	///
	/// Verifies that `new` creates a task that computes the value when run.
	#[test]
	fn test_task_new() {
		let task = Trampoline::new(|| 42);
		assert_eq!(task.evaluate(), 42);
	}

	/// Tests `Trampoline::bind`.
	///
	/// Verifies that `bind` chains computations correctly.
	#[test]
	fn test_task_bind() {
		let task = Trampoline::pure(10).bind(|x| Trampoline::pure(x * 2));
		assert_eq!(task.evaluate(), 20);
	}

	/// Tests `Trampoline::map`.
	///
	/// Verifies that `map` transforms the result.
	#[test]
	fn test_task_map() {
		let task = Trampoline::pure(10).map(|x| x * 2);
		assert_eq!(task.evaluate(), 20);
	}

	/// Tests `Trampoline::defer`.
	///
	/// Verifies that `defer` delays the creation of the task.
	#[test]
	fn test_task_defer() {
		let task = Trampoline::defer(|| Trampoline::pure(42));
		assert_eq!(task.evaluate(), 42);
	}

	/// Tests `Trampoline::tail_rec_m`.
	///
	/// Verifies that `tail_rec_m` performs tail recursion correctly.
	#[test]
	fn test_task_tail_rec_m() {
		fn factorial(n: u64) -> Trampoline<u64> {
			Trampoline::tail_rec_m(
				|(n, acc)| {
					if n <= 1 {
						Trampoline::pure(Step::Done(acc))
					} else {
						Trampoline::pure(Step::Loop((n - 1, n * acc)))
					}
				},
				(n, 1u64),
			)
		}

		assert_eq!(factorial(5).evaluate(), 120);
	}

	/// Tests `Trampoline::map2`.
	///
	/// Verifies that `map2` combines two tasks.
	#[test]
	fn test_task_map2() {
		let t1 = Trampoline::pure(10);
		let t2 = Trampoline::pure(20);
		let t3 = t1.lift2(t2, |a, b| a + b);
		assert_eq!(t3.evaluate(), 30);
	}

	/// Tests `Trampoline::and_then`.
	///
	/// Verifies that `and_then` sequences two tasks.
	#[test]
	fn test_task_and_then() {
		let t1 = Trampoline::pure(10);
		let t2 = Trampoline::pure(20);
		let t3 = t1.then(t2);
		assert_eq!(t3.evaluate(), 20);
	}

	/// Tests `Trampoline::arc_tail_rec_m`.
	///
	/// Verifies that `arc_tail_rec_m` works with non-Clone closures.
	#[test]
	fn test_task_arc_tail_rec_m() {
		use std::sync::{
			Arc,
			atomic::{AtomicUsize, Ordering},
		};

		let counter = Arc::new(AtomicUsize::new(0));
		let counter_clone = Arc::clone(&counter);

		let task = Trampoline::arc_tail_rec_m(
			move |n| {
				counter_clone.fetch_add(1, Ordering::SeqCst);
				if n == 0 {
					Trampoline::pure(Step::Done(0))
				} else {
					Trampoline::pure(Step::Loop(n - 1))
				}
			},
			10,
		);

		assert_eq!(task.evaluate(), 0);
		assert_eq!(counter.load(Ordering::SeqCst), 11);
	}

	/// Tests `Trampoline::from_memo`.
	///
	/// Verifies that `From<Lazy>` creates a task that retrieves the memoized value lazily.
	#[test]
	fn test_task_from_memo() {
		use crate::types::{Lazy, RcLazyConfig};
		use std::cell::RefCell;
		use std::rc::Rc;

		let counter = Rc::new(RefCell::new(0));
		let counter_clone = counter.clone();
		let memo = Lazy::<_, RcLazyConfig>::new(move || {
			*counter_clone.borrow_mut() += 1;
			42
		});

		let task = Trampoline::from(memo.clone());

		// Should not have computed yet (lazy creation)
		assert_eq!(*counter.borrow(), 0);

		assert_eq!(task.evaluate(), 42);
		assert_eq!(*counter.borrow(), 1);

		// Run again, should use cached value
		let task2 = Trampoline::from(memo);
		assert_eq!(task2.evaluate(), 42);
		assert_eq!(*counter.borrow(), 1);
	}

	/// Tests `Trampoline::from` with `ArcLazy`.
	#[test]
	fn test_task_from_arc_memo() {
		use crate::types::{ArcLazyConfig, Lazy};
		use std::sync::{Arc, Mutex};

		let counter = Arc::new(Mutex::new(0));
		let counter_clone = counter.clone();
		let memo = Lazy::<_, ArcLazyConfig>::new(move || {
			*counter_clone.lock().unwrap() += 1;
			42
		});

		let task = Trampoline::from(memo.clone());

		// Should not have computed yet (lazy creation)
		assert_eq!(*counter.lock().unwrap(), 0);

		assert_eq!(task.evaluate(), 42);
		assert_eq!(*counter.lock().unwrap(), 1);

		// Run again, should use cached value
		let task2 = Trampoline::from(memo);
		assert_eq!(task2.evaluate(), 42);
		assert_eq!(*counter.lock().unwrap(), 1);
	}
}