fp-library

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

At a Glance

• HKT emulation in stable Rust via the Brand pattern.
• Type class hierarchy inspired by Haskell / PureScript.
• Brand inference: map(|x| x + 1, Some(5)) with no turbofish needed.
• Val/Ref dispatch: one function handles both owned and borrowed containers.
• Zero-cost abstractions (no runtime overhead).
• Works with std types (Option, Result, Vec, etc.).
• Advanced features: optics, lazy evaluation, parallel traits.

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:

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

Examples

Using Functor with Option

The brand is inferred automatically from the container type:

use fp_library::functions::*;

fn main() {
	// Brand inferred from Option<i32>
	let y = map(|i: i32| i * 2, Some(5));
	assert_eq!(y, Some(10));

	// Brand inferred from &Vec<i32> (by-reference dispatch)
	let v = vec![1, 2, 3];
	let y = map(|i: &i32| *i + 10, &v);
	assert_eq!(y, vec![11, 12, 13]);
}

For types with multiple brands (e.g., Result), use the explicit variant:

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

fn main() {
	let y = map::<ResultErrAppliedBrand<&str>, _, _, _, _>(|i| i * 2, Ok::<i32, &str>(5));
	assert_eq!(y, Ok(10));
}

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::*, m_do};

fn main() {
	// Inferred mode: brand inferred from container types
	let result = m_do!({
		x <- Some(5);
		y <- Some(x + 1);
		let z = x * y;
		Some(z)
	});
	assert_eq!(result, Some(30));

	// Explicit mode: for ambiguous types or when pure() is needed
	let result = m_do!(VecBrand {
		x <- vec![1, 2];
		y <- vec![10, 20];
		pure(x + y)
	});
	assert_eq!(result, vec![11, 21, 12, 22]);
}

Usage

Add fp-library to your Cargo.toml:

[dependencies]
fp-library = "0.16"

Features

For a detailed breakdown of all features, type class hierarchies (with Mermaid diagrams), data types, and macros, see the Features documentation.

Crate Features

The library offers optional features that can be enabled in your Cargo.toml:

• 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.

To enable features:

[dependencies]
# Single feature
fp-library = { version = "0.16", features = ["rayon"] }

# Multiple features
fp-library = { version = "0.16", features = ["rayon", "serde"] }

How it Works

Higher-Kinded Types: The library encodes HKTs using lightweight higher-kinded polymorphism (the "Brand" pattern). Each type constructor has a zero-sized brand type (e.g., OptionBrand) that implements Kind traits mapping brands back to concrete types. See Higher-Kinded Types.

Brand Inference: InferableBrand traits provide the reverse mapping (concrete type -> brand), letting the compiler infer brands automatically. trait_kind! and impl_kind! generate both mappings. See Brand Inference.

Val/Ref Dispatch: Each free function routes to either a by-value or by-reference trait method based on the closure's argument type (or container ownership for closureless operations). Dispatch and brand inference compose through the shared FA type parameter. See Val/Ref Dispatch.

Zero-Cost Abstractions: 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. See Zero-Cost Abstractions.

Lazy Evaluation: A granular hierarchy of lazy types (Thunk, Trampoline, Lazy) lets you choose trade-offs between stack safety, memoization, lifetimes, and thread safety. Each has a fallible Try* counterpart. See Lazy Evaluation.

Thread Safety & Parallelism: A parallel trait hierarchy (ParFunctor, ParFoldable, etc.) mirrors the sequential one. When the rayon feature is enabled, par_* functions use true parallel execution. See Thread Safety and Parallelism.

Documentation

• API Documentation: The complete API reference on docs.rs.
• Features & Type Class Hierarchy: Full feature list with hierarchy diagrams.
• Higher-Kinded Types: The Brand pattern and HKT encoding.
• Brand Inference: How InferableBrand eliminates turbofish for common types.
• Val/Ref Dispatch: How unified free functions route to by-value or by-reference trait methods.
• Zero-Cost Abstractions: Uncurried semantics and static dispatch.
• Pointer Abstraction: Pointer hierarchy, FnBrand<P>, and shared memoization.
• Lazy Evaluation: Guide to the lazy evaluation and memoization types.
• Coyoneda Implementations: Trade-offs between the four free functor variants.
• Thread Safety & Parallelism: Parallel trait hierarchy and rayon support.
• Limitations and Workarounds: Rust type system constraints and how the library addresses them.
• Project Structure: Module layout and dependency graph.
• Architecture & Design: Design decisions and documentation conventions.
• Optics Analysis: Optics coverage comparison with PureScript.
• Profunctor Analysis: Profunctor class hierarchy comparison with PureScript.
• Std Library Coverage: Type class coverage for standard library types.
• Benchmarks: Performance results, graphs, and benchmark coverage.

Contributing

We welcome contributions!

To get started:

• Check out our Contributing Guide for environment setup and development workflows.
• Read the documentation files to get a high-level understanding of the project.
• Join the conversation in GitHub Issues.

Please ensure all PRs pass just verify before submission.

License

This project is licensed under the Blue Oak Model License 1.0.0.

References

• Lightweight higher-kinded polymorphism
• Typeclassopedia
• Lean Mathlib Prelude
• PureScript Pursuit
• Haskell base package Prelude
• PureScript Typeclass Hierarchy
• Where to find theoretical background (i.e., resources) behind PureScript classes?
• Counterexamples of Type Classes
• Haskell semigroupoids package
  • Class names
• Why not Pointed?
• Pluggable lifetimes
• Scala Cats
• haskell_bits