Implemented via lightweight higher-kinded polymorphism (brand pattern). Write generic code
over Functor, Monad, Traversable, etc. that works with Option, Result, Vec,
or your own types. Procedural macros (trait_kind!, impl_kind!, Apply!,
InferableBrand!) simplify defining and applying HKT encodings. m_do! provides monadic
do-notation; a_do! provides applicative do-notation. Both support a ref qualifier for
by-reference dispatch and an inferred mode (m_do!({ ... })) where the brand is inferred
from container types. See Higher-Kinded Types.
For types with a single unambiguous brand (Option, Vec, Identity, Thunk, Lazy, etc.),
free functions like map, bind, fold_right, and bimap infer the brand automatically
from the container type via InferableBrand traits. No turbofish needed:
use fp_library::functions::*;
let y = map(|x: i32| x + 1, Some(5)); // infers OptionBrand
let z: Vec<i32> = bind(vec![1, 2], |x: i32| vec![x, x*10]); // infers VecBrand
let w = bimap((|e: i32| e+1, |s: i32| s*2), Ok::<i32, i32>(5)); // infers ResultBrand
assert_eq!(y, Some(6));
assert_eq!(z, vec![1, 10, 2, 20]);
assert_eq!(w, Ok(10));Types with multiple brands (Result at arity 1, Tuple2, Pair, ControlFlow) require the
explicit:: variants (explicit::map::<Brand, ...>) for arity-1 operations.
InferableBrand traits are auto-generated by trait_kind! and impl_kind!. The
#[no_inferable_brand] attribute on impl_kind! suppresses generation for multi-brand types.
See Brand Inference.
Each free function routes to either a by-value or by-reference trait method based on the
closure's argument type. Closureless operations (alt, compact, etc.) dispatch based on
container ownership instead. This means a single map function handles both
map(|x: i32| x + 1, Some(5)) (owned, dispatches to Functor::map) and
map(|x: &i32| *x + 1, &v) (borrowed, dispatches to RefFunctor::ref_map).
See Val/Ref Dispatch.
Core operations use uncurried semantics with impl Fn for static dispatch and zero heap
allocation. Dynamic dispatch (dyn Fn) is reserved for cases where functions must be
stored as data (e.g., Semiapplicative::apply, Lazy thunks, Endofunction).
See Zero-Cost Abstractions.
The library provides a comprehensive set of type classes. Blanket implementations
automatically derive composite traits (Applicative, Monad, Comonad, Alternative,
MonadPlus) from their components. For rationale behind the hierarchy design, see
Architecture & Design.
---
config:
layout: elk
---
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
Contravariant
Contravariant is the dual of Functor: it maps functions contravariantly
(Fn(B) -> A instead of Fn(A) -> B). It has no supertrait relationship with Functor
in the trait hierarchy, but the two are connected through Profunctor: a profunctor with
its second parameter fixed (ProfunctorSecondAppliedBrand) implements Contravariant,
while a profunctor with its first parameter fixed (ProfunctorFirstAppliedBrand) implements Functor.
---
config:
layout: elk
---
graph TD
Bifunctor --> Bitraversable
Bifoldable --> Bitraversable
---
config:
layout: elk
---
graph TD
Profunctor --> Strong --> Wander
Profunctor --> Choice --> Wander
Profunctor --> Closed
Profunctor --> Costrong
Profunctor --> Cochoice
Category --> Arrow
Strong --> Arrow
---
config:
layout: elk
---
graph TD
Semigroup --> Monoid
Semigroupoid --> Category
Other: NaturalTransformation (polymorphic function F a -> G a between type
constructors). Pipe (left-to-right function application via .pipe() method, blanket
impl on all Sized types).
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.
By-reference hierarchy: A full by-ref type class stack for memoized types and by-reference iteration over collections:
RefFunctor,RefPointed,RefLift,RefSemiapplicative,RefSemimonad,RefApplicative,RefMonad,RefApplyFirst,RefApplySecondRefFoldable,RefTraversable,RefFilterable,RefWitherableRefFunctorWithIndex,RefFoldableWithIndex,RefFilterableWithIndex,RefTraversableWithIndex
Thread-safe by-reference: SendRefFunctor, SendRefPointed, SendRefLift,
SendRefSemiapplicative, SendRefSemimonad, SendRefApplicative, SendRefMonad,
SendRefFoldable, SendRefFoldableWithIndex, SendRefFunctorWithIndex,
SendRefApplyFirst, SendRefApplySecond.
Parallel by-reference: ParRefFunctor, ParRefFoldable, ParRefFilterable,
ParRefFunctorWithIndex, ParRefFoldableWithIndex, ParRefFilterableWithIndex.
Laziness and effects: Deferrable, SendDeferrable for lazy construction.
LazyConfig for memoization strategy abstraction.
Semiring, Ring, CommutativeRing, EuclideanRing, DivisionRing, Field,
HeytingAlgebra.
A parallel trait hierarchy (ParFunctor, ParFoldable, etc.) mirrors the sequential one
with Send + Sync bounds. When the rayon crate feature is enabled, par_* functions
use true parallel execution; without it, they fall back to sequential equivalents.
See Thread Safety and Parallelism.
Standard library instances: Option, Result, Vec, String implement relevant
type classes.
Lazy evaluation and stack safety (see Lazy Evaluation):
| 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 (see Coyoneda Implementations):
| 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) |
Free family:
| Type | Family | Clone | Send | 'a payloads |
Bind cost |
|---|---|---|---|---|---|
Free |
Erased | No | No | No | O(1) |
RcFree |
Erased | Yes | No | No | O(1) |
ArcFree |
Erased | Yes | Yes | No | O(1) |
FreeExplicit |
Explicit | No | Conditional | Yes | O(N) |
RcFreeExplicit |
Explicit | Yes | No | Yes | O(N) |
ArcFreeExplicit |
Explicit | Yes | Yes | Yes | O(N) |
The Erased family uses type-erased continuation queues for stack-safe O(1)
bind, which requires 'static payloads. The Explicit family keeps the
recursive structure typed so borrowed payloads can participate, at the cost of
walking the spine for bind. WrapDrop is the public trait that lets these
substrates dismantle suspended functor layers without stack-overflowing during
drop.
Containers: Identity, Pair, CatList (O(1) append/uncons catenable list).
Function wrappers: Endofunction (dynamically composed a -> a), Endomorphism
(monoidally composed a -> a).
Pointer abstraction: Independent pointer traits (Pointer, RefCountedPointer,
SendRefCountedPointer) and coercion traits (ToDynFn, ToDynCloneFn, ToDynSendFn)
abstract over Box/Rc/Arc via FnBrand<P>, enabling generic code that works with
any pointer type. CloneFn/SendCloneFn provide cloneable closure wrappers for
applicative contexts. Arrow provides composable callable wrappers for the optics system.
See Pointer Abstraction.
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. See Optics Comparison.
The Run subsystem (requires the effects crate feature; experimental, with
an API that may change between releases; see Run Effects)
represents effectful programs as data. A Run value is
a Free-monad-backed program carrying two type-level effect rows: a first-order
operation row R and a scoped (around-action) effect row S. Effects are
injected into the rows as operations, and explicit handler lists interpret each
operation as an interpreter steps the program to its result.
There are six wrappers, across the Erased and Explicit substrate families:
| Type | Family | Reusable | Thread-safe |
|---|---|---|---|
Run<R, S, A> |
Erased | No | No |
RcRun<R, S, A> |
Erased | Yes | No |
ArcRun<R, S, A> |
Erased | Yes | Yes |
RunExplicit<'a, R, S, A> |
Explicit | No | No |
RcRunExplicit<'a, R, S, A> |
Explicit | Yes | No |
ArcRunExplicit<'a, R, S, A> |
Explicit | Yes | Yes |
First-order effects include State, Reader, Except, Writer, Choose,
Empty, and the Await future base-lift effect. Scoped effects include
Catch, Local / RefLocal, Bracket / RefBracket, Span, and Writer
censor / listen. Erased wrappers can be converted into their Explicit
siblings through the standard From / Into conversion traits.
The default Run family can interpret programs asynchronously through the
Await effect: Run::await_future embeds a Future, and Run::run_async
drives the program as a runtime-agnostic future, awaiting each embedded future
via a direct async driver loop. See Run Effects.
Additive, Multiplicative, Conjunctive, Disjunctive, First, Last, Dual
for selecting Semigroup/Monoid instances.
compose, constant, flip, identity, on, pipe.