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), Roll(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 f a. 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 roll(fa: <F as Kind_cdc7cd43dac7585f>::Of<'static, Free<F, A>>) -> Self

Creates a suspended computation from a functor value.

Type Signature

forall f a. 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, _>::roll(eval);

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

Monadic bind (flatMap) with O(1) complexity.

Type Signature

forall f b a. (a -> Free f b, Free f a) -> 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 run(self) -> A

where F: Runnable,

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. Runnable 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.run(), 42);

Trait Implementations

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

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

fn drop(&mut self)

Executes the destructor for this type.