Struct Free 

pub struct Free<F, A>(/* private fields */)
where
    F: Functor + 'static,
    A: 'static;

The Free monad with O(1) bind via CatList.

This implementation follows “Reflection without Remorse” to ensure that left-associated binds do not degrade performance.

HKT and Lifetime Limitations

Free does not implement HKT traits (like Functor, Monad) from this library.

The Conflict

• The Traits: The Kind trait implemented by the Functor hierarchy requires the type constructor to accept any lifetime 'a (e.g., type Of<'a, A> = Free<F, A>).
• The Implementation: This implementation uses Box<dyn Any> to type-erase continuations for the “Reflection without Remorse” optimization. dyn Any strictly requires A: 'static.

This creates an unresolvable conflict: Free cannot support non-static references (like &'a str), so it cannot satisfy the Kind signature.

Why not use the “Naive” Recursive Definition?

A naive definition (enum Free { Pure(A), Wrap(F<Box<Free<F, A>>>) }) would support lifetimes and HKT traits. However, it was rejected because:

1. Stack Safety: run would not be stack-safe for deep computations.
2. Performance: bind would be O(N), leading to quadratic complexity for sequences of binds.

This implementation prioritizes stack safety and O(1) bind over HKT trait compatibility.

Type Parameters

• F: The base functor (must implement Functor).
• A: The result type.

Examples

use fp_library::{brands::*, types::*};

let free = Free::<ThunkBrand, _>::pure(42);

Implementations

impl<F, A> Free<F, A>

where F: Functor + 'static, A: 'static,

pub fn pure(a: A) -> Self

Creates a pure Free value.

Type Signature

forall self. A -> self

Parameters

• a: The value to wrap.

Returns

A Free computation that produces a.

Examples

use fp_library::{brands::*, types::*};

let free = Free::<ThunkBrand, _>::pure(42);

pub fn wrap(fa: <F as Kind_cdc7cd43dac7585f>::Of<'static, Free<F, A>>) -> Self

Creates a suspended computation from a functor value.

Type Signature

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

Parameters

• fa: The functor value containing the next step.

Returns

A Free computation that performs the effect fa.

Examples

use fp_library::{brands::*, types::*};

let eval = Thunk::new(|| Free::pure(42));
let free = Free::<ThunkBrand, _>::wrap(eval);

pub fn lift_f(fa: <F as Kind_cdc7cd43dac7585f>::Of<'static, A>) -> Self

Lifts a functor value into the Free monad.

This is the primary way to inject effects into Free monad computations. Equivalent to PureScript’s liftF and Haskell’s liftF.

Type Signature

forall self. Functor self => F A -> self

Implementation

liftF fa = wrap (map pure fa)

Parameters

• fa: The functor value to lift.

Returns

A Free computation that performs the effect and returns the result.

Examples

use fp_library::{brands::*, types::*};

// Lift a simple computation
let thunk = Thunk::new(|| 42);
let free = Free::<ThunkBrand, _>::lift_f(thunk);
assert_eq!(free.evaluate(), 42);

// Build a computation from raw effects
let computation = Free::<ThunkBrand, _>::lift_f(Thunk::new(|| 10))
    .bind(|x| Free::lift_f(Thunk::new(move || x * 2)))
    .bind(|x| Free::lift_f(Thunk::new(move || x + 5)));
assert_eq!(computation.evaluate(), 25);

pub fn bind<B: 'static>( self, f: impl FnOnce(A) -> Free<F, B> + 'static, ) -> Free<F, B>

Monadic bind with O(1) complexity.

Type Signature

forall b. (A -> Free F b) -> Free F b

Type Parameters

• B: The result type of the new computation.

Parameters

• f: The function to apply to the result of this computation.

Returns

A new Free computation that chains f after this computation.

Examples

use fp_library::{brands::*, types::*};

let free = Free::<ThunkBrand, _>::pure(42)
    .bind(|x| Free::pure(x + 1));

pub fn evaluate(self) -> A

where F: Evaluable,

Executes the Free computation, returning the final result.

This is the “trampoline” that iteratively processes the CatList of continuations without growing the stack.

Type Signature

Evaluable F => A

Returns

The final result of the computation.

Examples

use fp_library::{brands::*, types::*};

let free = Free::<ThunkBrand, _>::pure(42);
assert_eq!(free.evaluate(), 42);

Trait Implementations

impl<A: 'static> Deferrable<'static> for Free<ThunkBrand, A>

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

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

Creates a Free computation from a thunk.

This delegates to Free::wrap and Thunk::new.

Type Signature

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

Type Parameters

• F: The type of the thunk.

Parameters

• f: A thunk that produces the free computation.

Returns

The deferred free computation.

Examples

use fp_library::{brands::*, functions::*, types::*, classes::Deferrable};

let task: Free<ThunkBrand, i32> = Deferrable::defer(|| Free::pure(42));
assert_eq!(task.evaluate(), 42);

impl<F, A> Drop for Free<F, A>

where F: Functor + 'static, A: 'static,

fn drop(&mut self)

Executes the destructor for this type.