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 type-level defunctionalization.
• Type class hierarchy inspired by PureScript / Haskell (Functor, Monad, Foldable, etc.).
• 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 core operations (map, bind, fold, etc.) via static dispatch.
• 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.

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, which can be viewed as a functor over either its Ok or Err type), use the explicit variant to select the brand:

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

fn main() {
	// ResultErrAppliedBrand fixes the error type, so map operates on the Ok value.
	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.17"

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.17", features = ["rayon"] }

# Multiple features
fp-library = { version = "0.17", 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.

Dispatch System: Free functions like map and bind infer the brand from the container type and route to by-value or by-reference trait methods automatically, so most call sites need no turbofish. For details, see Brand Inference, Val/Ref Dispatch, and Brand Dispatch Traits.

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: User guide for turbofish-free dispatch and multi-brand inference.
• Val/Ref Dispatch: User guide for unified by-value and by-reference function dispatch.
• Brand Dispatch Traits: Implementer reference for trait shapes, Marker invariant, and inference resolution.
• 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.
• References: Papers, libraries, and resources that informed this project.

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

See References for papers, libraries, and other resources that informed this project.