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,

• F: The base functor.
• A: The result type.

pub fn pure(a: A) -> Self

Creates a pure Free value.

Type Signature

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

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 F A. Functor F => F (Free F A) -> Free F A

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 F A. Functor F => F A -> Free F A

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 F A B. Functor F => (Free F A, A -> Free F B) -> Free F B

Type Parameters

• B: The result type of the new computation.

Parameters

• &mut self: The Free monad instance to operate on.
• 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 erase_type(self) -> Free<F, TypeErasedValue>

Converts to type-erased form.

Type Signature

forall F A. Functor F => Free F A -> Free F TypeErasedValue

pub fn boxed_erase_type(self) -> Box<Free<F, TypeErasedValue>>

Converts to boxed type-erased form.

Type Signature

forall F A. Functor F => Free F A -> Free F TypeErasedValue

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

forall F A. (Evaluable F, Functor F) => Free F A -> 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>

• A: The result type.

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 A. (() -> Free A) -> Free A

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,

Type Parameters

• F: The base functor.
• A: The result type.

fn drop(&mut self)

Type Signature

forall F A. Functor F => &mut Free F A -> ()