fp-library 0.1.1

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

fp-library

crates.io docs.rs GitHub License

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

Features

  • Higher-Kinded Types (HKT): Implemented using lightweight higher-kinded polymorphism (defunctionalization/brands).
  • Type Classes: A comprehensive collection of standard type classes including:
    • Functor, Applicative, Monad
    • Semigroup, Monoid
    • Foldable, Traversable
    • Category, Semigroupoid
    • Pointed, Lift, Defer, Once
    • ApplyFirst, ApplySecond, Semiapplicative, Semimonad
  • Data Types: Implementations for standard and custom types:
    • Option, Result, Vec, String
    • Identity, Lazy, Pair
    • Endofunction, Endomorphism
    • RcFn, ArcFn
    • OnceCell, OnceLock

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.

How it Works

Higher-Kinded Types (HKT)

Since Rust doesn't support HKTs directly (e.g., trait Functor<F<_>>), this library uses Lightweight Higher-Kinded Polymorphism (also known as the "Brand" pattern or 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.

// Simplified example
pub struct OptionBrand;

impl Kind1L1T for OptionBrand {
    type Output<'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.

Usage

Add fp-library to your Cargo.toml:

[dependencies]
fp-library = "0.1.0"

Example: Using Functor with Option

use fp_library::classes::functor::map;
use fp_library::brands::OptionBrand;

fn main() {
    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));
}

Contributing

We welcome contributions! Please feel free to submit a Pull Request.

Development Environment

This project uses Nix to manage the development environment.

  1. Install Nix Package Manager.
  2. Install nix-direnv (recommended) for automatic environment loading.

To set up the environment:

# If using direnv
direnv allow

# Or manually enter the shell
nix develop

This will provide a shell with the correct Rust version and dependencies.

Project Structure

  • fp-library/src/classes: Contains the definitions of type classes (traits).
  • fp-library/src/types: Contains implementations of type classes for various data types.
  • fp-library/src/hkt: Contains the machinery for higher-kinded types.
  • fp-library/src/brands: Contains type brands used for HKT encoding.
  • fp-library/src/functions: Contains general helper functions.

License

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

References