Crate fp_library

Expand description

A functional programming library for Rust featuring your favourite higher-kinded types and type classes.

§Motivation

Rust is a multi-paradigm language with strong functional programming features like iterators, closures, and algebraic data types. However, it lacks native support for Higher-Kinded Types (HKT), which limits the ability to write generic code that abstracts over type constructors (e.g., writing a function that works for any Monad, whether it’s Option, Result, or Vec).

fp-library aims to bridge this gap by providing:

A robust encoding of HKTs in stable Rust.
A comprehensive set of standard type classes (Functor, Monad, Traversable, etc.).
Zero-cost abstractions that respect Rust’s performance characteristics.

§Features

§Higher-Kinded Types (HKT)

Implemented using lightweight higher-kinded polymorphism (type-level defunctionalization/brands). Procedural macros (trait_kind!, impl_kind!, Apply!, #[kind]) simplify defining and applying HKT encodings. m_do! provides monadic do-notation; a_do! provides applicative do-notation.

§Type Class Hierarchy

The library provides a comprehensive set of type classes. Blanket implementations automatically derive composite traits (Applicative, Monad, Comonad, Alternative, MonadPlus) from their components.

graph TD
    Functor --> Alt --> Plus
    Functor --> Extend
    Extend --> Comonad
    Extract --> Comonad
    Functor --> Semiapplicative
    Lift --> Semiapplicative
    Lift --> ApplyFirst
    Lift --> ApplySecond
    Semiapplicative --> Applicative
    Pointed --> Applicative
    ApplyFirst --> Applicative
    ApplySecond --> Applicative
    Applicative --> Alternative
    Plus --> Alternative
    Applicative --> Monad
    Semimonad --> Monad
    Monad --> MonadPlus
    Alternative --> MonadPlus
    Monad --> MonadRec
    Foldable --> Traversable
    Functor --> Traversable
    Compactable --> Filterable
    Functor --> Filterable
    Filterable --> Witherable
    Traversable --> Witherable

graph TD
    Bifunctor --> Bitraversable
    Bifoldable --> Bitraversable

graph TD
    Profunctor --> Strong --> Wander
    Profunctor --> Choice --> Wander
    Profunctor --> Closed
    Profunctor --> Costrong
    Profunctor --> Cochoice

graph TD
    Semigroup --> Monoid
    Semigroupoid --> Category

Indexed variants: FunctorWithIndex, FoldableWithIndex, TraversableWithIndex, FilterableWithIndex extend their base traits with a shared WithIndex associated index type.

Parallel variants: ParFunctor, ParFoldable, ParCompactable, ParFilterable, ParFunctorWithIndex, ParFoldableWithIndex, ParFilterableWithIndex mirror the sequential hierarchy with Send + Sync bounds. Enable the rayon feature for true parallel execution.

Laziness and effects: RefFunctor, SendRefFunctor for mapping over memoized types. Deferrable, SendDeferrable for lazy construction. LazyConfig, TryLazyConfig for memoization strategy abstraction.

§Optics

Composable data accessors using profunctor encoding (port of PureScript’s purescript-profunctor-lenses): Iso, Lens, Prism, AffineTraversal, Traversal, Getter, Setter, Fold, Review, Grate. Each has a monomorphic Prime variant. Indexed variants available for Lens, Traversal, Getter, Fold, Setter. Zero-cost composition via Composed and optics_compose.

§Data Types

Standard library instances: Option, Result, Vec, String implement relevant type classes.

Lazy evaluation and stack safety:

Type	Purpose
`Thunk` / `SendThunk`	Lightweight deferred computation.
`Trampoline`	Stack-safe recursion via the `Free` monad.
`Lazy` (`RcLazy`, `ArcLazy`)	Memoized (evaluate-at-most-once) computation.
`TryThunk` / `TrySendThunk`	Fallible deferred computation.
`TryTrampoline`	Fallible stack-safe recursion.
`TryLazy` (`RcTryLazy`, `ArcTryLazy`)	Fallible memoized computation.

Free functors:

Type	Wrapper	Clone	Send	Map fusion
`Coyoneda`	`Box`	No	No	No (k calls)
`RcCoyoneda`	`Rc`	Yes	No	No (k calls)
`ArcCoyoneda`	`Arc`	Yes	Yes	No (k calls)
`CoyonedaExplicit`	None	No	Conditional	Yes (1 call)

Containers: Identity, Pair, CatList (O(1) append/uncons catenable list).

Function wrappers: Endofunction (dynamically composed a -> a), Endomorphism (monoidally composed a -> a).

§Numeric Algebra

Semiring, Ring, CommutativeRing, EuclideanRing, DivisionRing, Field, HeytingAlgebra.

§Newtype Wrappers

Additive, Multiplicative, Conjunctive, Disjunctive, First, Last, Dual for selecting Semigroup/Monoid instances.

§Helper Functions

compose, constant, flip, identity, on, pipe.

§How it Works

§Higher-Kinded Types (HKT)

Since Rust doesn’t support HKTs directly (i.e., it’s not possible to use Option in impl Functor for Option, instead of Option<T>), this library uses Lightweight Higher-Kinded Polymorphism (also known as the “Brand” pattern or type-level defunctionalization).

Each type constructor has a corresponding Brand type (e.g., OptionBrand for Option). These brands implement the Kind traits, which map the brand and generic arguments back to the concrete type. The library provides macros to simplify this process.

use fp_library::{
	impl_kind,
	kinds::*,
};

pub struct OptionBrand;

impl_kind! {
	for OptionBrand {
		type Of<'a, A: 'a>: 'a = Option<A>;
	}
}

§Zero-Cost Abstractions & Uncurried Semantics

Unlike many functional programming libraries that strictly adhere to curried functions (e.g., map(f)(fa)), fp-library adopts uncurried semantics (e.g., map(f, fa)) for its core abstractions.

Why? Traditional currying in Rust often requires:

Creating intermediate closures for each partial application.
Heap-allocating these closures (boxing) or wrapping them in reference counters (Rc/Arc) to satisfy type system constraints.
Dynamic dispatch (dyn Fn), which inhibits compiler optimizations like inlining.

By using uncurried functions with impl Fn or generic bounds, fp-library achieves zero-cost abstractions:

No Heap Allocation: Operations like map and bind do not allocate intermediate closures.
Static Dispatch: The compiler can fully monomorphize generic functions, enabling aggressive inlining and optimization.
Ownership Friendly: Better integration with Rust’s ownership and borrowing system.

This approach ensures that using high-level functional abstractions incurs no runtime penalty compared to hand-written imperative code.

Exceptions: While the library strives for zero-cost abstractions, some operations inherently require dynamic dispatch or heap allocation due to Rust’s type system:

Functions as Data: When functions are stored in data structures (e.g., inside a Vec for Semiapplicative::apply, or in Lazy thunks), they must often be “type-erased” (wrapped in Rc<dyn Fn> or Arc<dyn Fn>). This is because every closure in Rust has a unique, anonymous type. To store multiple different closures in the same container, or to compose functions dynamically (like in Endofunction), they must be coerced to a common trait object.
Lazy Evaluation: The Lazy type relies on storing a thunk that can be cloned and evaluated later, which typically requires reference counting and dynamic dispatch.

For these specific cases, the library provides Brand types (like RcFnBrand and ArcFnBrand) to let you choose the appropriate wrapper (single-threaded vs. thread-safe) while keeping the rest of your code zero-cost. The library uses a unified Pointer hierarchy to abstract over these choices.

§Lazy Evaluation & Effect System

Rust is an eagerly evaluated language. To enable functional patterns like deferred execution and safe recursion, fp-library provides a granular set of types that let you opt-in to specific behaviors without paying for unnecessary overhead.

User stories:

Thunk / SendThunk: “I want to defer a computation and evaluate it later.”
Trampoline (Free): “I want to chain binds without blowing the stack.”
Lazy (RcLazy / ArcLazy): “I want to compute a value at most once and cache it.”
Try* variants: “I want any of the above, but the computation may fail.”

§Type Overview

The hierarchy consists of infallible computation types, fallible counterparts, and the Free monad infrastructure. Each type makes different trade-offs around stack safety, memoization, lifetimes, and thread safety.

Type	Underlying	HKT	Stack Safe	Memoized	Lifetimes	Send
`Thunk<'a, A>`	`Box<dyn FnOnce() -> A + 'a>`	Yes (full)	Partial (`tail_rec_m` only)	No	`'a`	No
`SendThunk<'a, A>`	`Box<dyn FnOnce() -> A + Send + 'a>`	No	Partial (`tail_rec_m` only)	No	`'a`	Yes
`Trampoline<A>`	`Free<ThunkBrand, A>`	No	Yes	No	`'static`	No
`RcLazy<'a, A>`	`Rc<LazyCell<A, ...>>`	Partial (`RefFunctor`)	N/A	Yes	`'a`	No
`ArcLazy<'a, A>`	`Arc<LazyLock<A, ...>>`	Partial (`SendRefFunctor`)	N/A	Yes	`'a`	Yes
`TryThunk<'a, A, E>`	`Thunk<'a, Result<A, E>>`	Yes (full)	Partial (`tail_rec_m` only)	No	`'a`	No
`TrySendThunk<'a, A, E>`	`SendThunk<'a, Result<A, E>>`	No	Partial (`tail_rec_m` only)	No	`'a`	Yes
`TryTrampoline<A, E>`	`Trampoline<Result<A, E>>`	No	Yes	No	`'static`	No
`RcTryLazy<'a, A, E>`	`Rc<LazyCell<Result<A, E>, ...>>`	Partial (`RefFunctor`, `Foldable`)	N/A	Yes	`'a`	No
`ArcTryLazy<'a, A, E>`	`Arc<LazyLock<Result<A, E>, ...>>`	Partial (`SendRefFunctor`, `Foldable`)	N/A	Yes	`'a`	Yes
`Free<F, A>`	CatList-based “Reflection without Remorse”	No	Yes	No	`'static`	No

Config-dependent Send: ArcLazy/ArcTryLazy are Send + Sync; RcLazy/RcTryLazy are not.

At a glance, the primary use cases are:

Type	Primary Use Case
`Thunk<'a, A>`	Glue Code & Borrowing. Lightweight deferred computation. Best for short chains and working with references.
`SendThunk<'a, A>`	Thread-Safe Glue Code. Like `Thunk`, but the closure is `Send`. Enables truly lazy `into_arc_lazy()`.
`Trampoline<A>`	Deep Recursion & Pipelines. Heavy-duty computation. Uses a trampoline to guarantee stack safety for infinite recursion.
`Lazy<'a, A>`	Caching. Wraps a computation to ensure it runs at most once. `RcLazy` for single-threaded, `ArcLazy` for thread-safe.

Each of these has a fallible counterpart that wraps Result<A, E> with ergonomic error-handling combinators (TryThunk, TrySendThunk, TryTrampoline, TryLazy).

§Supporting Traits

Trait	Purpose	Implementors in hierarchy
`Deferrable<'a>`	Lazy construction from thunk	`Thunk`, `SendThunk`, `Trampoline`, `RcLazy`, `ArcLazy`, `RcTryLazy`, `ArcTryLazy`, `TryThunk`, `TrySendThunk`, `Free<ThunkBrand, A>`
`SendDeferrable<'a>`	Thread-safe lazy construction (extends `Deferrable`)	`SendThunk`, `TrySendThunk`, `ArcLazy`, `ArcTryLazy`
`RefFunctor`	Mapping with `&A` input	`LazyBrand<RcLazyConfig>`, `TryLazyBrand<E, RcLazyConfig>`
`SendRefFunctor`	Thread-safe mapping with `&A` input	`LazyBrand<ArcLazyConfig>`, `TryLazyBrand<E, ArcLazyConfig>`
`LazyConfig`	Infallible memoization strategy (pointer + cell choice)	`RcLazyConfig`, `ArcLazyConfig`
`TryLazyConfig`	Fallible memoization strategy (extends `LazyConfig`)	`RcLazyConfig`, `ArcLazyConfig`

§The “Why” of Multiple Types

Unlike lazy languages (e.g., Haskell) where the runtime handles everything, Rust requires us to choose our trade-offs:

Thunk vs Trampoline: Thunk is faster and supports borrowing (&'a T). Its tail_rec_m is stack-safe, but deep bind chains will overflow the stack. Trampoline guarantees stack safety for all operations via a trampoline (the Free monad) but requires types to be 'static. Note that !Send types like Rc<T> are fully supported. A key distinction is that Thunk implements Functor, Applicative, and Monad directly, making it suitable for generic programming, while Trampoline does not.
Thunk vs SendThunk: Thunk wraps Box<dyn FnOnce() -> A + 'a> and is !Send. SendThunk wraps Box<dyn FnOnce() -> A + Send + 'a> and can cross thread boundaries. Use SendThunk when you need truly lazy into_arc_lazy() (converting to ArcLazy without eager evaluation), or when building deferred computation chains that will be consumed on another thread. TrySendThunk is the fallible counterpart.
Computation vs Caching: Thunk and Trampoline describe computations that are not memoized. Each instance is consumed on .evaluate() (which takes self by value), so the computation runs exactly once per instance, but constructing a new instance re-executes the work. Lazy, by contrast, caches the result so that all clones share a single evaluation. If you have an expensive operation (like a DB call), convert it to a Lazy to guarantee it runs at most once.
RefFunctor vs Functor: Lazy::evaluate() returns &A, not A. The standard Functor trait expects owned A, so automatically cloning would violate the library’s zero-cost abstraction principle. RefFunctor honestly represents what Lazy can do: mapping with &A -> B.
LazyConfig vs TryLazyConfig: The memoization strategy is split into two traits. LazyConfig covers infallible memoization (pointer type, lazy cell, thunk type). TryLazyConfig extends it with fallible variants (TryLazy, TryThunk). Third-party implementations can choose to implement only LazyConfig when fallible memoization is not needed.

§Quick Decision Guide

Short deferred computation chains: Use Thunk.
Deep recursion or long pipelines: Use Trampoline.
Cache an expensive result (single-threaded): Use RcLazy.
Cache an expensive result (multi-threaded): Use ArcLazy.
Deferred computation that must be Send: Use SendThunk.
Any of the above, but fallible: Use the Try* counterpart.
Generic programming over lazy types: Use Deferrable / SendDeferrable trait bounds.

§Workflow Example: Expression Evaluator

A robust pattern is to use TryTrampoline for stack-safe, fallible recursion, TryLazy to memoize expensive results, and TryThunk to create lightweight views.

Consider an expression evaluator that handles division errors and deep recursion:

use fp_library::types::*;

#[derive(Clone)]
enum Expr {
	Val(i32),
	Add(Box<Expr>, Box<Expr>),
	Div(Box<Expr>, Box<Expr>),
}

// 1. Stack-safe recursion with error handling (TryTrampoline)
fn eval(expr: &Expr) -> TryTrampoline<i32, String> {
	let expr = expr.clone(); // Capture owned data for 'static closure
	TryTrampoline::defer(move || match expr {
		Expr::Val(n) => TryTrampoline::ok(n),
		Expr::Add(lhs, rhs) => eval(&lhs).bind(move |l| eval(&rhs).map(move |r| l + r)),
		Expr::Div(lhs, rhs) => eval(&lhs).bind(move |l| {
			eval(&rhs).bind(move |r| {
				if r == 0 {
					TryTrampoline::err("Division by zero".to_string())
				} else {
					TryTrampoline::ok(l / r)
				}
			})
		}),
	})
}

// Usage
fn main() {
	let expr = Expr::Div(Box::new(Expr::Val(100)), Box::new(Expr::Val(2)));

	// 2. Memoize result (TryLazy)
	// The evaluation runs at most once, even if accessed multiple times.
	let result = RcTryLazy::new(move || eval(&expr).evaluate());

	// 3. Create deferred view (TryThunk)
	// Borrow the cached result to format it.
	let view: TryThunk<String, String> = TryThunk::new(|| {
		let val = result.evaluate().map_err(|e| e.clone())?;
		Ok(format!("Result: {}", val))
	});

	assert_eq!(view.evaluate(), Ok("Result: 50".to_string()));
}

§Thread Safety and Parallelism

The library provides a parallel trait hierarchy that mirrors the sequential one. All par_* free functions accept plain impl Fn + Send + Sync closures: no wrapper types required. Element types require A: Send; closures require Send + Sync.

graph TD
    ParFunctor --> ParFilterable
    ParCompactable --> ParFilterable
    ParFunctor --> ParFunctorWithIndex
    ParFoldable --> ParFoldableWithIndex
    ParFilterable --> ParFilterableWithIndex
    ParFoldableWithIndex --> ParFilterableWithIndex

Parallel trait	Operations	Supertraits
`ParFunctor`	`par_map`	`Kind`
`ParCompactable`	`par_compact`, `par_separate`	`Kind`
`ParFilterable`	`par_filter_map`, `par_filter`	`ParFunctor + ParCompactable`
`ParFoldable`	`par_fold_map`	`Kind`
`ParFunctorWithIndex`	`par_map_with_index`	`ParFunctor + FunctorWithIndex`
`ParFoldableWithIndex`	`par_fold_map_with_index`	`ParFoldable + FoldableWithIndex`
`ParFilterableWithIndex`	`par_filter_map_with_index`	`ParFilterable + ParFoldableWithIndex + WithIndex`

ParFilterable provides default implementations of par_filter_map and par_filter derived from par_map + par_compact; types can override them for single-pass efficiency.

SendCloneableFn: Extends CloneableFn to provide Send + Sync function wrappers. Implemented by ArcFnBrand.
Rayon Support: When the rayon feature is enabled, par_* functions use rayon for true parallel execution. Otherwise they fall back to sequential equivalents.

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

let v = vec![1, 2, 3, 4, 5];
// Map in parallel (uses rayon if feature is enabled)
let doubled: Vec<i32> = par_map::<VecBrand, _, _>(|x: i32| x * 2, v.clone());
assert_eq!(doubled, vec![2, 4, 6, 8, 10]);
// Compact options in parallel
let opts = vec![Some(1), None, Some(3), None, Some(5)];
let compacted: Vec<i32> = par_compact::<VecBrand, _>(opts);
assert_eq!(compacted, vec![1, 3, 5]);
// Fold in parallel
let result = par_fold_map::<VecBrand, _, _>(|x: i32| x.to_string(), v);
assert_eq!(result, "12345".to_string());

§Example: Using `Functor` with `Option`

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

let x = Some(5);
// Map a function over the `Option` using the `Functor` type class
let y = map::<OptionBrand, _, _>(|i| i * 2, x);
assert_eq!(y, Some(10));

§Example: Monadic Do-Notation with `m_do!`

The m_do! macro provides Haskell/PureScript-style do-notation for flat monadic code. It desugars <- binds into nested bind calls.

use fp_library::{brands::*, functions::*};
use fp_macros::m_do;

let result = m_do!(OptionBrand {
	x <- Some(5);
	y <- Some(x + 1);
	let z = x * y;
	pure(z)
});
assert_eq!(result, Some(30));

// Works with any monad brand
let result = m_do!(VecBrand {
	x <- vec![1, 2];
	y <- vec![10, 20];
	pure(x + y)
});
assert_eq!(result, vec![11, 21, 12, 22]);

§Crate Features

rayon: Enables true parallel execution for par_* functions using the rayon library. Without this feature, par_* functions fall back to sequential equivalents.
serde: Enables serialization and deserialization support for pure data types using the serde library.
stacker: Enables adaptive stack growth for deep Coyoneda, RcCoyoneda, and ArcCoyoneda map chains via the stacker crate. Without this feature, deeply chained maps can overflow the stack.

Modules§

brands: Brands represent higher-kinded (unapplied/partially-applied) forms of types, as opposed to concrete types, which are fully-applied.
classes: Defines traits for common algebraic structures and functional abstractions, such as Functor, Applicative and Monad.
functions: Contains generic, helper free functions and re-exports of free versions of type class functions.
kinds: Kind traits represent the arity of a kind.
types: Concrete data types, their corresponding implementations and type aliases.

Macros§

Apply: Applies a brand to type arguments.
Kind: Generates the name of a Kind trait based on its signature.
a_do: Applicative do-notation.
generate_function_re_exports: Generates re-exports for all public free functions in a directory.
generate_trait_re_exports: Generates re-exports for all public traits in a directory.
impl_kind: Implements a Kind trait for a brand.
m_do: Monadic do-notation.
trait_kind: Defines a new Kind trait.

Attribute Macros§

document_examples: Inserts a ### Examples heading and validates doc comment code blocks.
document_module: Orchestrates documentation generation for an entire module.
document_parameters: Generates documentation for a function’s parameters.
document_returns: Generates documentation for the return value of a function.
document_signature: Generates a Hindley-Milner style type signature for a function.
document_type_parameters: Generates documentation for type parameters.
kind: Adds a Kind supertrait bound to a trait definition.

Crate fp_library

Crate fp_library Copy item path

§Motivation

§Features

§Higher-Kinded Types (HKT)

§Type Class Hierarchy

§Optics

§Data Types

§Numeric Algebra

§Newtype Wrappers

§Helper Functions

§How it Works

§Higher-Kinded Types (HKT)

§Zero-Cost Abstractions & Uncurried Semantics

§Lazy Evaluation & Effect System

§Type Overview

§Supporting Traits

§The “Why” of Multiple Types

§Quick Decision Guide

§Workflow Example: Expression Evaluator

§Thread Safety and Parallelism

§Example: Using Functor with Option

§Example: Monadic Do-Notation with m_do!

§Crate Features

Modules§

Macros§

Attribute Macros§

Crate fp_library

§Example: Using `Functor` with `Option`

§Example: Monadic Do-Notation with `m_do!`