Struct Trampoline 

pub struct Trampoline<A: 'static>(/* private fields */);

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-based bind stack, ensuring O(1) 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:

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

• A: The type of the value produced by the task.

Fields

• 0: 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);

Implementations

impl<A: 'static + Send> Trampoline<A>

pub fn pure(a: A) -> Self

Creates a Trampoline from an already-computed value.

Complexity

O(1) creation, O(1) evaluation

Type Signature

forall self. A -> self

Type Parameters

• A: The type of the value.

Parameters

• a: 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);

pub fn new<F>(f: F) -> Self

where F: FnOnce() -> A + 'static,

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

forall self. (() -> A) -> self

Type Parameters

• F: The type of the closure.

Parameters

• f: 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!"

pub fn defer<F>(f: F) -> Self

where F: FnOnce() -> Trampoline<A> + 'static,

Defers the construction of a Trampoline itself.

This is critical for stack-safe recursion: instead of building a chain of Trampolines directly (which grows the stack), we defer the construction.

Type Signature

forall self. (() -> Trampoline A) -> self

Type Parameters

• F: The type of the closure.

Parameters

• f: 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();

pub fn bind<B: 'static + Send, F>(self, f: F) -> Trampoline<B>

where F: FnOnce(A) -> Trampoline<B> + 'static,

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

forall b. (A -> Trampoline b) -> Trampoline b

Type Parameters

• B: The type of the result of the new task.
• F: The type of the binding function.

Parameters

• f: 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));
}

pub fn map<B: 'static + Send, F>(self, f: F) -> Trampoline<B>

where F: FnOnce(A) -> B + 'static,

Functor map: transforms the result without changing structure.

Type Signature

forall b. (A -> b) -> Trampoline b

Type Parameters

• B: The type of the result of the mapping function.
• F: The type of the mapping function.

Parameters

• f: 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);

pub fn evaluate(self) -> A

Forces evaluation and returns the result.

This runs the trampoline loop, iteratively processing the CatList of continuations without growing the stack.

Type Signature

A

Returns

The result of the computation.

Examples

use fp_library::types::*;

let task = Trampoline::new(|| 1 + 1);
assert_eq!(task.evaluate(), 2);

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,

Combines two Trampolines, running both and combining results.

Type Signature

forall b c. (Trampoline b, (A, b) -> c) -> Trampoline c

Type Parameters

• B: The type of the second task’s result.
• C: The type of the combined result.
• F: The type of the combining function.

Parameters

• other: The second task.
• f: 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 then<B: 'static + Send>(self, other: Trampoline<B>) -> Trampoline<B>

Sequences two Trampolines, discarding the first result.

Type Signature

forall b. Trampoline b -> Trampoline b

Type Parameters

• B: The type of the second task’s result.

Parameters

• other: 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 tail_rec_m<S: 'static + Send, F>(f: F, initial: S) -> Self

where F: Fn(S) -> Trampoline<Step<S, A>> + Clone + 'static,

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

forall self s. (s -> Trampoline (Step s A), s) -> self

Type Parameters

• S: The type of the state.
• F: The type of the step function.

Parameters

• f: The function that performs one step of the recursion.
• initial: 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 arc_tail_rec_m<S: 'static + Send, F>(f: F, initial: S) -> Self

where F: Fn(S) -> Trampoline<Step<S, A>> + 'static,

Arc-wrapped version for non-Clone closures.

Use this when your closure captures non-Clone state.

Type Signature

forall self s. (s -> Trampoline (Step s A), s) -> self

Type Parameters

• S: The type of the state.
• F: The type of the step function.

Parameters

• f: The function that performs one step of the recursion.
• initial: 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);

Trait Implementations

impl<A: 'static + Send> Deferrable<'static> for Trampoline<A>

fn defer<F>(f: F) -> Self

where F: FnOnce() -> Self + 'static, Self: Sized,

Creates a Trampoline from a computation that produces it.

Type Signature

forall self. Deferrable self => (() -> self) -> self

Type Parameters

• F: The type of the thunk.

Parameters

• f: 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);

impl<A: 'static + Send + Clone, Config: LazyConfig> From<Lazy<'static, A, Config>> for Trampoline<A>

fn from(lazy: Lazy<'static, A, Config>) -> Self

Converts to this type from the input type.

impl<'a, A> From<Trampoline<A>> for Lazy<'a, A, RcLazyConfig>

where A: Send,

fn from(task: Trampoline<A>) -> Self

Converts to this type from the input type.

impl<A, E> From<Trampoline<A>> for TryTrampoline<A, E>

where A: Send + 'static, E: Send + 'static,

fn from(task: Trampoline<A>) -> Self

Converts to this type from the input type.