Introduction

Karpal is a Higher-Kinded Type (HKT) library for the Industrial Algebra ecosystem. It provides:

• HKT encoding via GATs (trait HKT { type Of<T>; })
• A complete functor hierarchy (Functor → Applicative → Monad, plus Alt, Plus, Foldable, Traversable, and more)
• Algebraic typeclasses (Semigroup, Monoid, Group, Ring, Field, Lattice, Module, VectorSpace, HeytingAlgebra)
• Profunctor optics (Lens, Prism, Traversal, Fold, Iso, and more)
• Category/Arrow hierarchy with FnA, KleisliF, CokleisliF
• Free constructions (Free Monad, Cofree Comonad, Coyoneda, Day Convolution, Kan extensions)
• Recursion schemes (cata, ana, hylo, para, apo, histo, futu, zygo, chrono)
• Adjunctions and advanced category theory (ends, coends, dinatural transformations)
• Monad transformers (ExceptT, WriterT, ReaderT, StateT)
• Algebraic law witnesses and proof-carrying code
• External verification (SMT-LIB2, Lean 4, Kani, GPU obligations)
• String diagrams and monoidal category theory
• Schubert intersection type system
• 2-categories, enriched categories, and bicategories

All with no_std support and property-based law verification.

Why Karpal?

Rust has Option::map, Result::and_then, and Iterator::collect. They work great — but they're ad-hoc. Every container re-invents the same patterns with slightly different names, and there's no way to write a function that's generic over "any container that supports mapping" or "any container that supports sequencing effects."

Karpal gives those patterns names and laws, so you can abstract over them.

What does this buy you that standard Rust doesn't?

Generic traversals. traverse works over any Traversable + Applicative pair. You write validate_batch once and it works for Vec→Result, HashMap→Option, or any other combination:

#![allow(unused)]
fn main() {
// Works for any Traversable container and any Applicative effect
fn validate_all<C: Traversable, F: Applicative>(items: C::Of<Raw>) -> F::Of<C::Item>
}

Composable lenses. Instead of hand-writing nested struct accessors, you compose lenses like functions and pass them around as first-class values:

#![allow(unused)]
fn main() {
let street_lens = address_lens.compose(street_name_lens);
let updated = street_lens.over(company, |s| format!("{} (HQ)", s));
}

Law-guaranteed abstractions. Every Monad instance is property-tested for left identity, right identity, and associativity. If you implement Monad for your type and get it wrong, the test suite catches it — before your users do.

Honest limitations

The GAT-based HKT encoding has real constraints:

• No higher-kinded type inference — you must spell out type constructor markers (OptionF, VecF)
• Cannot abstract over type constructors with different kind signatures
• Requires nightly Rust (edition 2024 features)
• Static Land style (OptionF::fmap(...)) rather than method chaining (some.fmap(...))

These are inherent to encoding HKT in a language without native HKT support. Karpal chooses the GAT encoding because it's zero-dependency, stable since Rust 1.65, and doesn't require proc-macro magic.

License

Apache-2.0 + CLA. See CONTRIBUTING.md for details.

Karpal

Higher-Kinded Types and algebraic structures for Rust

Get Started | Browse Reference | GitHub

Features

Type-Safe Abstractions

HKT encoding via GATs lets you write functions generic over Option, Result, Vec, and any container that supports mapping, sequencing, or folding.

Complete Hierarchy

Functor through Monad, Alt through Alternative, Foldable, Traversable, Comonad, and contravariant duals — all with property-based law verification.

Profunctor Optics

Lens, Prism, and composition powered by the profunctor hierarchy. Build reusable, first-class field accessors and pattern matchers.

Ergonomic Macros

do_! flattens nested .and_then() chains. ado_! combines independent computations. Both work with any Monad or Applicative.

Proof & Verification

karpal-proof provides law witnesses and refinement types, while karpal-verify exports obligations to SMT and Lean with explicit trust boundaries.

Quick Example

Flatten nested error handling with do_!:

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Without do_! — rightward drift with every step
fn process(input: &str) -> Option<String> {
    parse_id(input).and_then(|id| {
        lookup_user(id).and_then(|user| {
            check_permissions(&user).and_then(|role| {
                Some(format!("{} logged in as {:?}", user.name, role))
            })
        })
    })
}

// With do_! — reads top-to-bottom
fn process(input: &str) -> Option<String> {
    do_! { OptionF;
        id = parse_id(input);
        user = lookup_user(id);
        role = check_permissions(&user);
        Some(format!("{} logged in as {:?}", user.name, role))
    }
}
}

Workspace

karpal-core, karpal-profunctor, karpal-arrow, karpal-free, karpal-recursion, karpal-algebra, karpal-effect, karpal-proof, and the modeling/export portions of karpal-verify are no_std compatible with optional std/alloc feature gates.

Documentation Map

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Getting Started

This guide walks you through adding Karpal to your Rust project, understanding its HKT encoding, and using the core abstractions: Functor, Monad, and the ergonomic do_! and ado_! macros.

1. Installation

The easiest way to use Karpal is through the karpal-std crate, which re-exports everything from the other workspace crates in a single prelude.

Add it to your Cargo.toml:

#![allow(unused)]
fn main() {
[dependencies]
karpal-std = "0.7"
}

Then import the prelude at the top of any module that uses Karpal types and traits:

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;
}

This single import brings in all type constructors (OptionF, VecF, ResultF, etc.), all traits (Functor, Applicative, Monad, Foldable, etc.), and the do_! and ado_! macros.

Toolchain requirements

Karpal requires nightly Rust because it uses edition 2024 features. The repository includes a rust-toolchain.toml that pins the exact nightly version, so if you are working within the Karpal workspace, Cargo and rustup will select the correct toolchain automatically.

If you are consuming Karpal as a dependency in your own project, make sure your project also uses a nightly toolchain. You can create a rust-toolchain.toml in your project root:

#![allow(unused)]
fn main() {
[toolchain]
channel = "nightly"
}

2. Your First HKT

Higher-Kinded Types (HKTs) let you abstract over type constructors — not just concrete types like Option<i32>, but the Option constructor itself. Rust does not natively support HKTs, but Karpal encodes them using Generic Associated Types (GATs), which have been stable since Rust 1.65.

The core trait is:

#![allow(unused)]
fn main() {
trait HKT {
    type Of<T>;
}
}

A type that implements HKT is a type constructor — a marker type that, given a parameter T, produces a concrete type. Karpal provides several built-in constructors:

So <OptionF as HKT>::Of<i32> is simply Option<i32>. Nothing new at the value level — the magic is at the type level. You can now write functions that are generic over the shape of the container, not just its contents:

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

/// Wraps a value in any container that supports `Applicative::pure`.
fn wrap<F: Applicative>(value: i32) -> F::Of<i32> {
    F::pure(value)
}

let opt: Option<i32> = wrap::<OptionF>(42);   // Some(42)
let vec: Vec<i32>    = wrap::<VecF>(42);      // vec![42]
}

The caller chooses the container by supplying a type constructor as a generic parameter. The function body stays the same regardless of which container is selected.

3. Your First Functor

A Functor is any type constructor that supports mapping a function over its contents. If you have used Option::map or Iterator::map, you already know the idea — Karpal just gives it a uniform interface.

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = OptionF::fmap(Some(2), |x| x * 3);
assert_eq!(result, Some(6));

let result = VecF::fmap(vec![1, 2, 3], |x| x + 10);
assert_eq!(result, vec![11, 12, 13]);
}

This looks similar to calling .map() directly, and at the concrete level it behaves identically. The difference is that Functor::fmap is a trait method on the type constructor, which means you can write functions that work with any functor:

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

fn double_inner<F: Functor>(fa: F::Of<i32>) -> F::Of<i32> {
    F::fmap(fa, |x| x * 2)
}

// Works with Option
assert_eq!(double_inner::<OptionF>(Some(5)), Some(10));
assert_eq!(double_inner::<OptionF>(None), None);

// Works with Vec
assert_eq!(double_inner::<VecF>(vec![1, 2, 3]), vec![2, 4, 6]);
}

One function, multiple container types, zero code duplication.

Functor laws

Every Functor implementation must satisfy two laws. Karpal verifies these with property-based tests, but they are worth knowing informally:

• Identity: mapping the identity function changes nothing. F::fmap(fa, |x| x) == fa
• Composition: mapping f then g is the same as mapping |x| g(f(x)). F::fmap(F::fmap(fa, f), g) == F::fmap(fa, |x| g(f(x)))

These laws guarantee that fmap only transforms values — it never adds, removes, or reorders elements in the container.

4. Monadic Notation with do_!

Monadic computations in Rust quickly turn into deeply nested .and_then() chains. Each step that depends on the previous value adds another level of indentation:

#![allow(unused)]
fn main() {
// The nesting problem: every step pushes the code further right
fn fetch_dashboard(user_id: &str) -> Option<Dashboard> {
    lookup_user(user_id).and_then(|user| {
        load_preferences(&user).and_then(|prefs| {
            fetch_activity(&user).and_then(|activity| {
                build_dashboard(&user, &prefs, &activity)
            })
        })
    })
}
}

With three steps this is manageable; with six or seven it becomes painful to read. The do_! macro flattens this into a top-to-bottom sequence of bindings:

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

fn fetch_dashboard(user_id: &str) -> Option<Dashboard> {
    do_! { OptionF;
        user     = lookup_user(user_id);
        prefs    = load_preferences(&user);
        activity = fetch_activity(&user);
        build_dashboard(&user, &prefs, &activity)
    }
}
}

Each name = expr line binds the unwrapped value from the monadic expression on the right. If any step returns None (or Err for ResultF), the entire block short-circuits immediately. The final expression (without a binding) is the return value of the block.

Syntax reference

#![allow(unused)]
fn main() {
do_! { TypeConstructor;
    binding1 = monadic_expr1;
    binding2 = monadic_expr2;
    // ... more bindings ...
    final_monadic_expr
}
}

• The first token is the type constructor (OptionF, VecF, ResultF<E>, etc.), followed by a semicolon.
• Each binding uses =, not <-. Rust edition 2024 reserves <- as a token, so the arrow syntax is not available.
• The final line must be an expression of type F::Of<T> — it is the value returned by the whole do_! block.
• Bindings can reference earlier bindings — each step has access to all names bound above it.

A concrete example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

fn safe_divide(a: f64, b: f64) -> Option<f64> {
    if b == 0.0 { None } else { Some(a / b) }
}

let result = do_! { OptionF;
    x = safe_divide(100.0, 4.0);   // Some(25.0)
    y = safe_divide(x, 5.0);       // Some(5.0)
    z = safe_divide(y, 2.0);       // Some(2.5)
    Some(z + 1.0)                   // Some(3.5)
};

assert_eq!(result, Some(3.5));
}

5. Applicative Notation with ado_!

When your computations are independent — none of them need the result of a previous step — you do not need the full power of do_!. The ado_! macro expresses this pattern and makes the independence explicit:

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

fn load_host() -> Option<&'static str> { Some("localhost") }
fn load_port() -> Option<u16>           { Some(8080) }
fn load_workers() -> Option<usize>      { Some(4) }

let config = ado_! { OptionF;
    host    = load_host();
    port    = load_port();
    workers = load_workers();
    yield format!("{}:{} ({} workers)", host, port, workers)
};

assert_eq!(config, Some("localhost:8080 (4 workers)".to_string()));
}

The yield line combines all the bound values into a final result. Unlike do_!, the bindings in ado_! cannot reference each other — they are all evaluated independently, and the results are combined at the end.

Syntax reference

#![allow(unused)]
fn main() {
ado_! { TypeConstructor;
    binding1 = applicative_expr1;
    binding2 = applicative_expr2;
    // ... more bindings ...
    yield combining_expression
}
}

• Same first-token convention as do_!: the type constructor, then a semicolon.
• Each binding uses =. Bindings are independent and must not reference each other.
• The yield line combines all bound values into the final result. The expression after yield is a pure function of the bound names — it is automatically lifted into the applicative context.
• If any binding evaluates to None (or Err), the whole block short-circuits.

When to use ado_! vs do_!

In practice, ado_! documents intent: it tells the reader that the computations have no data dependencies. For types where order does not matter (like Option), the runtime behavior is identical, but the semantic clarity is valuable.

6. Proof and External Verification

Once you are comfortable with Karpal's core abstractions, the next layer is reasoning about laws explicitly.

karpal-proof gives you Rust-native evidence types like Proven<P, T>, refinement wrappers like NonEmpty<T> and Positive<T>, and derive helpers that generate algebraic law tests.

karpal-verify takes the next step outward: it lets you model proof obligations, export them to SMT-LIB2 or Lean 4, write artifacts, execute verification runs, and collect JSON / Markdown reports suitable for CI. Imported certificates remain explicit and do not silently become Rust proof witnesses.

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let sig = AlgebraicSignature::monoid(Sort::Int, "combine", "e");
let bundle = ObligationBundle::monoid(
    "sum_monoid",
    Origin::new("karpal-core", "Monoid for Sum<i32>"),
    &sig,
);
let report = verify_bundle(
    &bundle,
    &ArtifactLayout::new("target/karpal-verify"),
    "KarpalVerify",
    &SmtConfig::default(),
    &LeanConfig::default(),
    &DryRunner,
).expect("verification session should succeed");
assert_eq!(report.obligation_count(), 3);
}

See the Proof & Verification reference for the full workflow and trust model, the Verification CI Workflow guide for artifact/report orchestration, and the Verification Schemas page for serialized compatibility details.

7. Next Steps

Now that you can install Karpal, map over containers generically, flatten monadic chains, and understand where proofs fit into the ecosystem, here is where to go next:

• Architecture — understand the full functor hierarchy, from Functor through Monad, and the Alt/Alternative branch. See how the traits relate and which type constructors implement each one.
• Functor Family reference — detailed documentation for Functor, Apply, Applicative, Chain, and Monad, including all method signatures and implementation notes.
• Macros reference — the full syntax and edge cases for do_! and ado_!, including usage with ResultF and VecF.
• Optics — profunctor-based Lens and Prism for composable, first-class field access and pattern matching.
• Proof & Verification reference — law witnesses, derive-based checks, Lean/SMT obligation export, project-aware Lean execution, diagnostics mapping, trust boundaries, and CI-oriented verification reports.
• Verification CI Workflow — artifact layout, report writing, backend policies, Lean manifest/sidecar generation, and CI integration guidance for karpal-verify.
• Verification Schemas — schema-versioned report, manifest, and diagnostics formats plus compatibility guidance for consumers.
• Config Pipeline example — a realistic end-to-end example combining Functor, Applicative, and monadic chaining to build a configuration loader.
• Data Transformation example — using Foldable, Traversable, and FunctorFilter to process collections generically.
• Verification Workflow example — a full karpal-verify walkthrough from obligation bundle to CI report files and explicit certificate import.
• Verified Domain API example — how karpal-proof Proven<...>-based APIs and karpal-verify Certified<...> imports fit together at a domain boundary.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Mathematical Foundation

Karpal is built on category theory — the mathematics of structure and composition.

HKT Encoding

Higher-Kinded Types (HKTs) are types that take other types as parameters: F<A> rather than just A. Rust doesn't natively support HKTs, but GATs (Generic Associated Types, stable since Rust 1.65) provide a zero-dependency encoding:

#![allow(unused)]
fn main() {
pub trait HKT {
    type Of<T>;
}
}

A marker type like OptionF implements HKT with type Of<T> = Option<T>. This lets us write traits that are generic over the "shape" of a container.

The Functor Hierarchy

The core abstraction is the functor hierarchy:

Functor → Apply → Applicative
                 ↓
          Chain → Monad

Each level adds capabilities:

• Functor: map over a container (fmap)
• Apply: combine two containers (ap)
• Applicative: create a pure value (pure)
• Chain: sequence operations (chain / bind)
• Monad: full sequential computation

Algebraic Structure

Beyond the functor hierarchy, Karpal provides algebraic typeclasses:

• Semigroup / Monoid: associative combine + identity
• Group / AbelianGroup: monoid + inverse
• Semiring / Ring / Field: two operations with distributivity
• Lattice / BoundedLattice: join + meet (poset with all suprema/infima)
• HeytingAlgebra: bounded lattice with implication (intuitionistic logic)

The Heyting algebra is the foundation for structured emptiness — the idea that "why something is empty" carries information.

Structured Emptiness

The Problem

Standard libraries treat emptiness as a single concept: None, Err, 0, empty(). The reason for emptiness is lost.

In geometric computation — and many other domains — there are fundamentally different kinds of emptiness:

The Lattice Ω

Karpal replaces boolean truth values with a richer lattice:

Denied < Granted(0) < Granted(1) < ... < Granted(∞)

This is a Heyting algebra — a bounded lattice with implication where the law of excluded middle does not hold (¬¬a ≠ a in general).

Implementation

The concrete realization is via Schubert calculus on Grassmannians. Given two Schubert classes σ_λ and σ_μ in Gr(k, n):

• Their intersection product is computed via Littlewood-Richardson coefficients
• The result is classified as StructuralZero, GeometricZero, Positive, or Underdetermined
• Composition of intersections uses the lattice meet (worst-case propagation)

#![allow(unused)]
fn main() {
use karpal_schubert_types::{check_intersection, IntersectionKind, SchubertType};

let s1 = SchubertType::new(vec![1], (2, 4)).unwrap();
let s22 = SchubertType::new(vec![2, 2], (2, 4)).unwrap();

assert_eq!(check_intersection(&s1, &s1).kind(), IntersectionKind::Positive);
assert_eq!(check_intersection(&s22, &s22).kind(), IntersectionKind::StructuralZero);
}

The Deeper Claim

The reason a computation yields no result is as important as the result itself. Zero is not a single value — it is a space of values, and the geometry of that space carries information.

See the design document for the full mathematical treatment.

Installation

Requirements

• Nightly Rust (for GAT-based HKT encoding)
• Rust 2024 edition

rustup default nightly

Adding Karpal to Your Project

Full Prelude

[dependencies]
karpal-std = "0.7"

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;
}

Individual Crates

[dependencies]
karpal-core = "0.7"      # HKT, Functor hierarchy, Semigroup, Monoid
karpal-optics = "0.7"     # Lens, Prism, Traversal, Fold
karpal-proof = "0.7"      # Proven<P,T>, Rewrite witnesses
karpal-verify = "0.7"     # SMT-LIB2, Lean 4, Kani verification
karpal-diagram = "0.7"    # Monoidal categories, string diagrams
karpal-higher = "0.7"     # 2-categories, enriched categories
karpal-schubert-types = "0.7"  # Schubert intersection types

no_std Support

Most crates are no_std compatible with optional std/alloc feature gates:

[dependencies]
karpal-core = { version = "0.7", default-features = false, features = ["alloc"] }

Feature Flags

Each crate supports std and alloc feature gates for no_std compatibility.

Default Features

By default, all crates enable std:

karpal-core = "0.7"  # enables std by default

no_std with alloc

karpal-core = { version = "0.7", default-features = false, features = ["alloc"] }

no_std without alloc

Core traits work without any allocator:

karpal-core = { version = "0.7", default-features = false }

Special Features

Exceptions

• karpal-schubert-types is std-only (depends on amari-enumerative)
• karpal-index is a binary crate (not published to crates.io)

Per-Crate no_std Status

CI verifies this via cargo build --no-default-features -p karpal-core -p karpal-profunctor on every push.

Discovery with the karpal Binary

karpal-discovery is the agent-first discovery runtime of Phase 19 — the second Lonis vertical. Its karpal binary is both a human CLI and a conforming Lonis SubprocessProvider: AI-agent harnesses discover and invoke it through one uniform protocol, and humans use the same commands directly.

Where karpal-index string-scans source files, karpal-discovery builds a typed, deterministic catalog with a real syn AST parse, layers a curated mathematical overlay (83 concepts with problem shapes and relationships) over it, and answers questions at the level agents actually ask them: "I need to sequence dependent effectful steps" → monad.

Installation

The binary is built with the lonis feature:

cargo install --path karpal-discovery --features lonis --bin karpal

The library itself is usable without the feature (the CLI and the Lonis output layer are optional):

[dependencies]
karpal-discovery = "0.9"

The Lonis Provider Protocol

karpal speaks the ADR-0006 v0 provider surface — the same protocol lonis itself speaks, so any Lonis host can use it without bespoke glue:

$ karpal --mode json manifest
{"name":"karpal","version":"0.9.0","provider_type":"external-executable",
 "protocol_version":"0","tools":["karpal.search","karpal.detail",...],
 "display_name":"Karpal Discovery"}

$ karpal --mode json tools list
$ karpal --mode json tools describe karpal.recommend
{"name":"karpal:recommend","description":"Recall and Pareto-rank curated concepts...",
 "determinism":"deterministic","side_effects":"read-only","cost":"low"}

Invocation is ADR-0003: JSON on stdin, a block array on stdout, structured ToolError on stderr. In-process hosts use lonis_core::SubprocessProvider; the binary is equally usable from a shell:

$ echo '{"workspace": ".", "query": "Functor"}' | karpal call karpal.search

Every tool is deterministic, read-only, and low-cost — stated in each tool's contract.

The Nine Tools

karpal.search — catalog items

{"workspace": ".", "query": "Functor"}

Case-insensitive substring search over every public item name (traits, functions, structs, enums, type aliases, macros, consts) in the workspace catalog.

karpal.detail — one item, fully joined

{"workspace": ".", "item": "Functor", "crate": "karpal-core"}

Returns the item with its docs, its implementors (from the trait implementation graph), and the overlay concepts anchored to it. For Functor:

{
  "item": {"name": "Functor", "crate_name": "karpal-core",
           "module_path": "karpal_core::functor", "kind": "trait"},
  "docs": "Covariant functor: lifts a function `A -> B` into `F<A> -> F<B>`.",
  "implementors": ["CofreeF", "ComposeF", "EnvF", "FixF", "FreeF",
                   "IdentityF", "NonEmptyVecF", "OptionF", "ResultF", "VecF"],
  "concepts": [{"id": "functor", "stability": "stable", ...}]
}

karpal.concepts — browse the overlay

{"query": "sheaf"}

Searches curated concepts across ids, names, aliases, mathematical concepts, and problem shapes. An empty query lists all 83.

karpal.imports — what a project actually uses

{"workspace": "."}

Analyzes a workspace's use statements against its own catalog: resolved symbols (with per-file counts), unresolved imports (the drift signal — stale references to removed or renamed items), and the curated concepts in use.

karpal.recommend — recall and rank for a goal

{"goal": "sequence dependent effectful steps"}

The planner's recall layer: direct matches seed candidates and the relation graph expands them; ranking is Pareto dominance over (relevance, weight). Ask for the problem, get the concept — monad, ranked first, with evidence:

{
  "concept_id": "monad",
  "stability": "stable",
  "relevance": 14,
  "evidence": ["match: problem shape",
               "relation: composes_with free-monad ↔ monad",
               "relation: dual_of comonad ↔ monad"]
}

karpal.plan — orient, explore, verify

{"goal": "monad"}

A candidate plan for the goal: orient on it, explore the top-ranked concepts (bounded to three), verify the drift gate. Plans are built as a Free monad and normalized (adjacent duplicate steps collapse).

karpal.probe_list / karpal.probe_describe / karpal.probe_run — algebraic probes

{"id": "schubert-intersection"}

Five probes, each running real library code: functor/monad laws on Option, the karpal-proof law checkers, Schubert intersections (the structured-emptiness thesis live — Positive vs StructuralZero), recursion-scheme agreement (hylo ≡ cata ∘ ana), and Mac Lane coherence witnesses. karpal.probe_run reports each check it demonstrated.

karpal-index Compatibility

Legacy karpal-index invocations keep working through the compat mode:

$ karpal --index-compat search Functor --json
$ karpal --index-compat hierarchy Monad --json

The JSON shapes are the legacy ones (ApiItem, Hierarchy, null for not-found) over the new catalog. Divergences are documented in the crate README: path carries the module path (no line numbers), and subtraits is empty — as it always was.

Next

• Discovery Runtime Reference — architecture, the library API, and how the planner dogfoods Karpal's own typeclasses.
• karpal-index guide — the legacy binary this succeeds.

Type Discovery with karpal-index

Successor available: the karpal binary (from karpal-discovery, Phase 19) supersedes karpal-index — same commands available via karpal --index-compat, plus catalog search, concept browsing, the planner, and probes. See Discovery with karpal. karpal-index remains published for compatibility.

karpal-index is a CLI binary that lets AI agents (and humans) discover Karpal's types and operations through progressive drill-down.

Commands

Search

$ karpal-index search Functor
Functor                        trait           Covariant functor: lifts a function A->B into F<A>->F<B>
FunctorFilter                  trait           FunctorFilter: a Functor that can filter elements

Detail

$ karpal-index detail Functor
Functor [trait]
  crate: karpal-core
  supertraits: HKT
  methods:
    - fn fmap<A, B>(fa: Self::Of<A>, f: impl Fn(A) -> B) -> Self::Of<B>;
  implementors:
    - OptionF
    - VecF
    - IdentityF

Hierarchy

$ karpal-index hierarchy Semigroup
Semigroup [trait]
  subtraits:
    - Monoid
  implementors:
    - String

JSON Output

All commands support --json for programmatic consumption:

$ karpal-index search Functor --json
[{"name":"Functor","kind":"trait","crate_name":"karpal-core",...}]

Usage

cargo run --bin karpal-index -- search Functor
# or install:
cargo install --path . --bin karpal-index
karpal-index search Functor

The binary reads the workspace source tree at runtime — no pre-built index needed.

Architecture

Design Principles

• GAT-based HKT encoding: trait HKT { type Of<T>; } — clean, zero-dependency
• Static Land over Fantasy Land: traits with associated functions (not methods on values)
• Law verification built in: every trait ships with proptest-based law tests
• no_std first: core and profunctor crates work without an allocator
• Composition over completeness: each phase delivers a usable layer before the next begins
• Structured emptiness: zeros carry provenance — why something is empty matters

Phase Completion

License

Apache-2.0 + CLA. See CONTRIBUTING.md.

Home > Architecture

Architecture

This page explains the core design decisions behind Karpal: how it encodes higher-kinded types in Rust, the full trait hierarchy, and the Static Land pattern that makes it all work within Rust's type system.

HKT Encoding

The problem

Rust has no native higher-kinded types. You cannot write a trait that is generic over a type constructor like Option or Vec — only over concrete types like Option<i32>. This means there is no built-in way to express "for any container F, give me an fmap that works on F<A>."

The GAT solution

Karpal encodes type constructors as marker types that implement a trait with a Generic Associated Type (GAT). The HKT trait acts as a type-level function: given a type T, it produces Self::Of<T>.

#![allow(unused)]
fn main() {
/// Higher-Kinded Type encoding via GATs.
///
/// A type implementing `HKT` acts as a type-level function:
/// given a type `T`, it produces `Self::Of<T>`.
pub trait HKT {
    type Of<T>;
}
}

Each standard container gets a zero-sized marker type that maps Of<T> to the real type:

#![allow(unused)]
fn main() {
/// Type constructor for `Option<T>`.
pub struct OptionF;

impl HKT for OptionF {
    type Of<T> = Option<T>;
}

/// Type constructor for `Result<T, E>` (fixed error type `E`).
pub struct ResultF<E> {
    _marker: PhantomData<E>,
}

impl<E> HKT for ResultF<E> {
    type Of<T> = Result<T, E>;
}

/// Type constructor for `Vec<T>` (alloc-gated).
#[cfg(any(feature = "std", feature = "alloc"))]
pub struct VecF;

#[cfg(any(feature = "std", feature = "alloc"))]
impl HKT for VecF {
    type Of<T> = Vec<T>;
}
}

Two-parameter HKT

For types with two type parameters — bifunctors and profunctors — Karpal provides HKT2:

#![allow(unused)]
fn main() {
/// Two-parameter type constructor (HKT for bifunctors / profunctors).
pub trait HKT2 {
    type P<A, B>;
}

/// Result as a bifunctor (both parameters vary).
pub struct ResultBF;

impl HKT2 for ResultBF {
    type P<A, B> = Result<B, A>;
}

/// Tuple as a bifunctor.
pub struct TupleF;

impl HKT2 for TupleF {
    type P<A, B> = (A, B);
}
}

Tradeoffs

Trait Hierarchy

The diagram below shows the full trait hierarchy implemented in karpal-core, karpal-profunctor, and karpal-arrow. Arrows point from supertrait to subtrait. Dashed borders indicate blanket implementations (no manual impl needed).

Key: Solid borders are standard traits. Dashed borders indicate blanket implementations — Monad is automatically derived for any type that implements both Applicative and Chain, and Alternative for Applicative + Plus.

The Static Land Pattern

Karpal uses associated functions on marker types, not methods on values. Instead of calling some_value.fmap(f), you write:

#![allow(unused)]
fn main() {
// Karpal's Static Land style
let result = OptionF::fmap(Some(42), |x| x + 1);

// NOT the method-on-value style (not possible in Karpal)
// let result = Some(42).fmap(|x| x + 1);
}

Why this approach?

Rust's trait coherence rules (the orphan rule) prevent you from implementing a foreign trait on a foreign type. Since Option is defined in std and Functor is defined in Karpal, you cannot write impl Functor for Option<T> directly.

The marker-type approach sidesteps this entirely. OptionF is owned by Karpal, so Karpal can freely implement any trait on it. The HKT GAT bridges the gap back to the actual container type via the Of<T> associated type.

Comparison with other ecosystems

Design Decisions

no_std first

karpal-core, karpal-profunctor, and karpal-arrow compile without std. Types that require heap allocation — VecF, NonEmptyVecF, PredicateF, StoreF, TracedF — are gated behind the alloc or std feature flags. This makes Karpal usable in embedded and no_std environments.

Nightly edition 2024

The toolchain is pinned to nightly via rust-toolchain.toml. While GATs themselves stabilized in Rust 1.65, Karpal also relies on use<> precise-capture syntax (edition 2024) and the alloc feature gate for no_std builds. The nightly pin ensures all contributors use the same compiler.

fn pointers in optics

The Lens struct stores plain function pointers rather than closures:

#![allow(unused)]
fn main() {
pub struct Lens<S, T, A, B> {
    getter: fn(&S) -> A,
    setter: fn(S, B) -> T,
}
}

This keeps Lens Copy-able and avoids lifetime complications. When lenses are composed via Lens::then(), the result is a ComposedLens that uses Box<dyn Fn> closures instead, since closure composition cannot produce fn pointers.

'static bounds on Box<dyn Fn>

Types whose inner representation is a boxed closure — PredicateF, FnP, FnA, KleisliF, CokleisliF, StoreF, TracedF — require 'static bounds. This is an inherent limitation of Box<dyn Fn> in Rust. As a consequence, StoreF and TracedF cannot implement the generic Functor trait (whose signature does not carry a 'static bound); they provide their own fmap through the Extend/Comonad implementation instead.

Blanket implementations

Where the theory permits, Karpal uses blanket impls to eliminate boilerplate:

#![allow(unused)]
fn main() {
/// Monad: Applicative + Chain with no extra methods (blanket impl).
pub trait Monad: Applicative + Chain {}

impl<F: Applicative + Chain> Monad for F {}
}

Any marker type that implements both Applicative and Chain is automatically a Monad. The same pattern applies to Alternative (= Applicative + Plus). Implementors only need to provide the primitive operations; the composed abstractions come for free.

Property-based law testing

Every algebraic trait in Karpal has proptest-based law tests that verify the required algebraic identities hold. For example, the Functor laws:

#![allow(unused)]
fn main() {
proptest! {
    #[test]
    fn option_identity(x in any::<Option<i32>>()) {
        // Identity law: fmap(id, fa) == fa
        let result = OptionF::fmap(x.clone(), |a| a);
        prop_assert_eq!(result, x);
    }

    #[test]
    fn option_composition(x in any::<Option<i32>>()) {
        // Composition law: fmap(g . f, fa) == fmap(g, fmap(f, fa))
        let f = |a: i32| a.wrapping_add(1);
        let g = |a: i32| a.wrapping_mul(2);
        let left = OptionF::fmap(x.clone(), |a| g(f(a)));
        let right = OptionF::fmap(OptionF::fmap(x, f), g);
        prop_assert_eq!(left, right);
    }
}
}

This approach catches subtle bugs that unit tests miss — such as associativity violations in Semigroup implementations or distributivity failures in Alternative.

Proof and Verification Layering

karpal-proof and karpal-verify extend this architecture above the trait hierarchy with two distinct reasoning layers.

Why two layers?

karpal-proof and karpal-verify intentionally solve different problems. The first lets Rust code carry structured evidence after local checks, trait-derived witnesses, or audited assumptions. The second lets Karpal talk to external provers without pretending that a solver result is the same thing as compiler-checked evidence.

karpal-verify pipeline

The external verification layer is organized as a pipeline:

1. Model a goal as an Obligation or ObligationBundle.
2. Export the bundle to SMT-LIB2 scripts or a Lean module.
3. Attach structured Lean metadata such as theorem identities, declaration spans, imports, aliases, and package/project scaffold data.
4. Write artifacts and build InvocationPlan values.
5. Execute those plans through a VerifierRunner, including project-aware lake env lean or lake build flows when desired.
6. Parse solver or Lean output, including Lean diagnostics and theorem-aware failure mapping.
7. Interpret success through an explicit VerificationPolicy per backend.
8. Aggregate results into a VerificationReport, Lean manifest, and diagnostics sidecar, all suitable for CI serialization.
9. Import successful evidence as Certified<B, P, T>, not directly as Proven<P, T>.

Trust boundary

This separation is deliberate. External evidence crosses a visible boundary through Certified<...> and only becomes Proven<...> via an explicit unsafe conversion. That keeps imported trust searchable in code review and avoids conflating theorem prover output with Rust-native guarantees.

For API details, see the Proof & Verification reference. For CI-specific execution/reporting guidance, see Verification CI Workflow. For serialized artifact compatibility, see Verification Schemas. For a walkthrough example, see Verification Workflow. For a domain-boundary example that combines karpal-proof and karpal-verify, see Verified Domain API. For the design note focused on imported trust, see Trust Model.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Roadmap

Completed (0.7.0)

• Phases 1–11: Core functor hierarchy, comonads, arrows, free constructions, recursion schemes, optics, abstract algebra, adjunctions, effect system, proof system
• Phase 12: External verification (SMT-LIB2, Lean 4, Kani, GPU obligations)
• Phase 13: Monoidal categories and string diagrams with coherence witnesses
• Phase 14 A–D: Schubert intersection type system with LR-enriched category
• Phase 15: 2-categories, enriched categories, bicategories, FFunctor/FMonad
• Phase 16A: Heyting algebra (foundation for structured emptiness)
• RichCat: Contentful 2-morphisms with provenance tracking
• karpal-index: AI-agent library discovery CLI with JSON output

Near-term

• Phase 16B–D: Presheaves, sieves, subobject classifier, Grothendieck topologies, sheaves
• Phase 17: End-to-end validation harness across all crates
• Phase 18: Ecosystem verification integrations (Schubert, Borsalino, ShaperOS)

Research Direction

• Structured emptiness as a position paper
• ∞-category encoding feasibility
• Topos-theoretic grounding for Schubert intersection

Full roadmap: ROADMAP.md

Semigroup & Monoid

Algebraic typeclasses for combining values.

Semigroup and Monoid are the foundational algebraic abstractions in Karpal. A Semigroup provides an associative binary operation for combining two values of the same type. A Monoid extends Semigroup with an identity element, enabling operations like folding an empty collection to a default value.

Semigroup

A type with an associative binary operation.

Signature

#![allow(unused)]
fn main() {
/// A type with an associative binary operation.
pub trait Semigroup {
    fn combine(self, other: Self) -> Self;
}
}

The combine method takes ownership of both values and produces a new value of the same type. Because it consumes self, there is no hidden aliasing -- the implementation is free to reuse allocations (and Karpal's String and Vec implementations do exactly that).

Laws

Associativity

For all a, b, c of type T: Semigroup:

#![allow(unused)]
fn main() {
a.combine(b).combine(c) == a.combine(b.combine(c))
}

The grouping of operations does not matter. This is the only law a Semigroup must satisfy.

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::semigroup::Semigroup;

// Numeric addition
assert_eq!(3i32.combine(4), 7);

// String concatenation
assert_eq!(
    "hello ".to_string().combine("world".to_string()),
    "hello world"
);

// Vec concatenation
assert_eq!(vec![1, 2].combine(vec![3, 4]), vec![1, 2, 3, 4]);

// Option lifts the inner Semigroup
assert_eq!(Some(3i32).combine(Some(4)), Some(7));
assert_eq!(Some(3i32).combine(None), Some(3));
assert_eq!(None::<i32>.combine(Some(4)), Some(4));
}

Monoid

A Semigroup with an identity element.

Signature

#![allow(unused)]
fn main() {
use crate::semigroup::Semigroup;

/// A `Semigroup` with an identity element.
pub trait Monoid: Semigroup {
    fn empty() -> Self;
}
}

The empty method returns the identity element for the type's combine operation. Combining any value with empty() (on either side) must return that value unchanged.

Laws

Left Identity

For all a of type T: Monoid:

#![allow(unused)]
fn main() {
T::empty().combine(a) == a
}

Right Identity

For all a of type T: Monoid:

#![allow(unused)]
fn main() {
a.combine(T::empty()) == a
}

Together with the Semigroup associativity law, these two laws make (T, combine, empty) a monoid in the algebraic sense.

Instances

Note that NonEmptyVec<T> implements Semigroup but not Monoid -- by definition it always contains at least one element, so there is no valid identity value.

Examples

#![allow(unused)]
fn main() {
use karpal_core::semigroup::Semigroup;
use karpal_core::monoid::Monoid;

// Numeric identity
assert_eq!(i32::empty(), 0);
assert_eq!(i32::empty().combine(42), 42);
assert_eq!(42i32.combine(i32::empty()), 42);

// String identity
assert_eq!(String::empty(), "");

// Vec identity
assert_eq!(Vec::<i32>::empty(), Vec::<i32>::new());

// Option identity
assert_eq!(Option::<i32>::empty(), None);
}

Foldable and Monoid

The Monoid trait plays a central role in the Foldable typeclass. Foldable defines fold_map, which maps each element of a structure through a function that returns a Monoid, then combines all the results using combine and empty:

#![allow(unused)]
fn main() {
pub trait Foldable: HKT {
    fn fold_right<A, B>(fa: Self::Of<A>, init: B, f: impl Fn(A, B) -> B) -> B;

    fn fold_map<A, M: Monoid>(fa: Self::Of<A>, f: impl Fn(A) -> M) -> M {
        Self::fold_right(fa, M::empty(), |a, acc| f(a).combine(acc))
    }
}
}

The default implementation of fold_map starts with M::empty() as the initial accumulator and folds right, combining each mapped element with the accumulator. Because Monoid guarantees associativity and identity, the result is well-defined regardless of the folding direction.

Example: summing a collection

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

// fold_map with the identity function sums the elements,
// because i32's Semigroup instance uses addition.
let total = VecF::fold_map(vec![1, 2, 3], |a: i32| a);
assert_eq!(total, 6);
}

Example: collecting strings

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

// Map each number to its string representation, then combine.
// String's Semigroup concatenates, and its Monoid starts from "".
let result = VecF::fold_map(vec![1, 2, 3], |a: i32| a.to_string());
assert_eq!(result, "123".to_string());
}

This pattern -- map then combine -- is the essence of fold_map and is the reason Monoid is so important in functional programming. Any time you need to reduce a collection to a single summary value, Monoid provides the structure to do it generically.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Functor Family

The covariant functor hierarchy: Functor through Monad.

Hierarchy

The Functor family forms a linear chain of increasingly powerful abstractions. Each trait extends the one above it:

#![allow(unused)]
fn main() {
Functor           // fmap: lift A -> B into F<A> -> F<B>
  |
  v
Apply             // ap: apply F<A -> B> to F<A>, producing F<B>
  |
  v
Applicative       // pure: lift a value A into F<A>
  |
  +--- Chain      // chain: monadic bind (flatMap)
  |      |
  v      v
  Monad           // Applicative + Chain (blanket impl, no extra methods)
}

Monad is provided as a blanket implementation: any type that implements both Applicative and Chain automatically implements Monad. There is no need to write an explicit impl Monad for ... block.

Functor

Covariant functor: lifts a function A -> B into F<A> -> F<B>.

Signature

#![allow(unused)]
fn main() {
pub trait Functor: HKT {
    fn fmap<A, B>(fa: Self::Of<A>, f: impl Fn(A) -> B) -> Self::Of<B>;
}
}

Laws

Identity: Mapping the identity function is a no-op.
F::fmap(fa, |x| x) == fa

Composition: Mapping two functions sequentially is the same as mapping their composition.
F::fmap(F::fmap(fa, f), g) == F::fmap(fa, |x| g(f(x)))

Instances

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Concrete usage
let doubled = OptionF::fmap(Some(5), |x| x * 2);
assert_eq!(doubled, Some(10));

let lengths = VecF::fmap(vec!["hello", "world"], |s| s.len());
assert_eq!(lengths, vec![5, 5]);

// Generic over any Functor
fn increment<F: Functor>(fa: F::Of<i32>) -> F::Of<i32> {
    F::fmap(fa, |x| x + 1)
}

assert_eq!(increment::<OptionF>(Some(9)), Some(10));
assert_eq!(increment::<VecF>(vec![1, 2]), vec![2, 3]);
}

Apply

A Functor that can apply a wrapped function to a wrapped value.

Signature

#![allow(unused)]
fn main() {
pub trait Apply: Functor {
    fn ap<A, B, F>(ff: Self::Of<F>, fa: Self::Of<A>) -> Self::Of<B>
    where
        A: Clone,
        F: Fn(A) -> B;
}
}

The A: Clone bound is required because some instances (such as VecF) apply multiple functions to each value, consuming the value more than once.

Laws

Associative composition: Applying composed functions is the same as composing applications.
ap(ap(fmap(compose, f), g), x) == ap(f, ap(g, x))

Instances

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Apply a wrapped function to a wrapped value
let f: Option<fn(i32) -> i32> = Some(|x| x * 2);
let result = OptionF::ap(f, Some(21));
assert_eq!(result, Some(42));

// Vec: cartesian product of functions and values
let fs: Vec<fn(i32) -> i32> = vec![|x| x + 1, |x| x * 10];
let result = VecF::ap(fs, vec![1, 2, 3]);
assert_eq!(result, vec![2, 3, 4, 10, 20, 30]);
}

Applicative

An Apply that can lift a pure value into the functor.

Signature

#![allow(unused)]
fn main() {
pub trait Applicative: Apply {
    fn pure<A>(a: A) -> Self::Of<A>;
}
}

Laws

Identity: Applying a pure identity function is a no-op.
ap(pure(id), v) == v

Homomorphism: Lifting a function and a value, then applying, is the same as lifting the result directly.
ap(pure(f), pure(x)) == pure(f(x))

Interchange: The order of lifting does not matter when the value is pure.
ap(u, pure(y)) == ap(pure(|f| f(y)), u)

Instances

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Lift a value into any Applicative context
let opt: Option<i32> = OptionF::pure(42);
assert_eq!(opt, Some(42));

let v: Vec<i32> = VecF::pure(42);
assert_eq!(v, vec![42]);

// Generic lifting
fn wrap<F: Applicative>(x: i32) -> F::Of<i32> {
    F::pure(x)
}

assert_eq!(wrap::<OptionF>(7), Some(7));
assert_eq!(wrap::<VecF>(7), vec![7]);
}

Chain

An Apply with monadic bind (flatMap). Enables sequential computations where each step depends on the previous result.

Signature

#![allow(unused)]
fn main() {
pub trait Chain: Apply {
    fn chain<A, B>(fa: Self::Of<A>, f: impl Fn(A) -> Self::Of<B>) -> Self::Of<B>;
}
}

Note that the function f returns Self::Of<B>, not just B. This is what distinguishes chain from fmap: the callback itself produces a wrapped value, and chain flattens the result.

Laws

Associativity: Chaining is associative -- nesting does not matter.
chain(chain(m, f), g) == chain(m, |x| chain(f(x), g))

Instances

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Option: short-circuits on None
fn safe_sqrt(x: f64) -> Option<f64> {
    if x >= 0.0 { Some(x.sqrt()) } else { None }
}

let result = OptionF::chain(Some(16.0), safe_sqrt);
assert_eq!(result, Some(4.0));

let result = OptionF::chain(Some(-1.0), safe_sqrt);
assert_eq!(result, None);

// Vec: flatMap (each element expands into a list)
let result = VecF::chain(vec![1, 2, 3], |x| vec![x, x * 10]);
assert_eq!(result, vec![1, 10, 2, 20, 3, 30]);
}

Monad

Applicative + Chain. A blanket implementation with no extra methods.

Signature

#![allow(unused)]
fn main() {
pub trait Monad: Applicative + Chain {}

impl<F: Applicative + Chain> Monad for F {}
}

Monad is a marker trait. It adds no new methods; it simply certifies that a type implements both Applicative (for pure) and Chain (for chain). The blanket impl means you never write impl Monad for MyType -- just implement Applicative and Chain, and Monad comes for free.

Laws

In addition to the Applicative and Chain laws, a Monad must satisfy:

Left identity: Lifting a value with pure then chaining is the same as calling the function directly.
chain(pure(a), f) == f(a)

Right identity: Chaining with pure is a no-op.
chain(m, pure) == m

Instances

Every type that implements both Applicative and Chain is automatically a Monad:

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Use Monad as a trait bound to require both pure and chain
fn bind_and_wrap<M: Monad>(x: i32) -> M::Of<String>
where
    M::Of<i32>: Clone,
{
    M::chain(M::pure(x), |n| M::pure(format!("value: {}", n)))
}

assert_eq!(bind_and_wrap::<OptionF>(42), Some("value: 42".to_string()));

// The do_! macro desugars into chain calls, so it requires Monad
let result = do_! { OptionF;
    x = Some(10);
    y = Some(x + 20);
    Some(x + y)
};
assert_eq!(result, Some(40));
}

See Also

• Alt Family -- the Alt / Plus / Alternative branch, which extends Functor in a different direction (choice and failure).
• Macros -- the do_! and ado_! macros that provide ergonomic syntax for Chain and Applicative computations.
• Foldable & Traversable -- folding and traversing structures, which combine naturally with Applicative.
• Getting Started -- a tutorial introduction to HKTs, Functor, and monadic notation.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Alt Family

Fallback and choice combinators: Alt, Plus, Alternative.

Hierarchy

Functor → Alt → Plus → (+ Applicative) → Alternative (blanket)

The Alt branch of the functor hierarchy provides combinators for expressing fallback and choice. Alt gives an associative choice operation, Plus adds an identity element (zero/empty), and Alternative combines Plus with Applicative via a blanket impl.

Alt

Alt

A Functor with an associative choice operation.

Signature

#![allow(unused)]
fn main() {
pub trait Alt: Functor {
    fn alt<A>(fa1: Self::Of<A>, fa2: Self::Of<A>) -> Self::Of<A>;
}
}

alt takes two values of the same functor type and returns one, preferring the first when both are "successful." The exact semantics depend on the instance: for OptionF it is .or(), for VecF it is concatenation.

Laws

Associativity

alt(alt(a, b), c) == alt(a, alt(b, c))

Distributivity

fmap(f, alt(a, b)) == alt(fmap(f, a), fmap(f, b))

Instances

VecF and NonEmptyVecF require the alloc or std feature.

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Fallback: try the first source, fall back to the second
let primary: Option<i32> = None;
let fallback: Option<i32> = Some(42);

let result = OptionF::alt(primary, fallback);
assert_eq!(result, Some(42));

// When both are present, the first wins
let result = OptionF::alt(Some(1), Some(2));
assert_eq!(result, Some(1));

// Vec: concatenation
let combined = VecF::alt(vec![1, 2], vec![3, 4]);
assert_eq!(combined, vec![1, 2, 3, 4]);
}

Plus

Plus

An Alt with a zero/empty element.

Signature

#![allow(unused)]
fn main() {
pub trait Plus: Alt {
    fn zero<A>() -> Self::Of<A>;
}
}

zero produces the identity element for alt. Combined with the Alt laws, this gives a monoid structure over the functor type.

Laws

Left identity

alt(zero(), a) == a

Right identity

alt(a, zero()) == a

Annihilation

fmap(f, zero()) == zero()

Instances

ResultF<E> does not implement Plus because there is no way to produce a Result<A, E> without an E value. NonEmptyVecF also lacks an instance because a non-empty vector cannot be empty by definition.

VecF requires the alloc or std feature.

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// zero() for Option is None
let empty: Option<i32> = OptionF::zero();
assert_eq!(empty, None);

// zero() for Vec is an empty vector
let empty_vec: Vec<i32> = VecF::zero();
assert_eq!(empty_vec, Vec::<i32>::new());

// Left identity: alt(zero(), a) == a
let a = Some(10);
assert_eq!(OptionF::alt(OptionF::zero(), a), a);

// Right identity: alt(a, zero()) == a
assert_eq!(OptionF::alt(a, OptionF::zero()), a);
}

Alternative

Alternative

Applicative + Plus with no extra methods (blanket impl).

Signature

#![allow(unused)]
fn main() {
pub trait Alternative: Applicative + Plus {}

impl<F: Applicative + Plus> Alternative for F {}
}

Alternative is a marker trait that combines Applicative and Plus. It introduces no new methods — any type that implements both Applicative and Plus automatically implements Alternative via the blanket impl.

Laws

Alternative inherits all laws from Alt, Plus, and Applicative, and adds two of its own:

Distributivity

ap(alt(f, g), x) == alt(ap(f, x), ap(g, x))

Annihilation

ap(zero(), x) == zero()

Instances

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Alternative lets you combine choice (Alt/Plus) with
// applicative computation (Applicative).

// Distributivity: ap(alt(f, g), x) == alt(ap(f, x), ap(g, x))
let f: Option<fn(i32) -> i32> = Some(|a| a + 1);
let g: Option<fn(i32) -> i32> = Some(|a| a * 2);
let x = Some(10);

let left  = OptionF::ap(OptionF::alt(f, g), x);
let right = OptionF::alt(OptionF::ap(f, x), OptionF::ap(g, x));
assert_eq!(left, right);  // Both are Some(11)

// Annihilation: ap(zero(), x) == zero()
let no_fn: Option<fn(i32) -> i32> = OptionF::zero();
let result = OptionF::ap(no_fn, Some(5));
assert_eq!(result, None);
}

See Also

• Functor Family — the Functor → Apply → Applicative → Chain → Monad branch that Alt builds upon.
• Semigroup & Monoid — the value-level analogue: Semigroup provides an associative combine, Monoid adds an empty identity, mirroring the Alt/Plus relationship at the functor level.
• Foldable & Traversable — traits for collapsing and sequencing containers, which compose naturally with Alt and Plus.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Foldable & Traversable

Summarize and sequence container contents.

Foldable

Foldable

A structure that can be folded to a summary value.

Signature

#![allow(unused)]
fn main() {
pub trait Foldable: HKT {
    fn fold_right<A, B>(fa: Self::Of<A>, init: B, f: impl Fn(A, B) -> B) -> B;

    fn fold_map<A, M: Monoid>(fa: Self::Of<A>, f: impl Fn(A) -> M) -> M {
        Self::fold_right(fa, M::empty(), |a, acc| f(a).combine(acc))
    }
}
}

fold_right is the required method. It processes elements right-to-left, threading an accumulator through each step. fold_map is provided as a default: it maps each element into a Monoid and combines them.

Laws

fold_map consistency

fold_map(fa, f) == fold_right(fa, M::empty(), |a, acc| f(a).combine(acc))

Any override of the default fold_map must agree with the right fold formulation above.

Instances

Example: summing with fold_map

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// fold_map maps each element into a Monoid and combines them.
// For i32, the Monoid instance uses addition with identity 0.

let sum = VecF::fold_map(vec![1, 2, 3], |a: i32| a);
assert_eq!(sum, 6); // 1 + 2 + 3

let sum = OptionF::fold_map(Some(42), |a: i32| a);
assert_eq!(sum, 42);

let sum = OptionF::fold_map(None::<i32>, |a: i32| a);
assert_eq!(sum, 0); // Monoid::empty() for i32
}

Example: fold_right

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// fold_right processes elements right-to-left.
// With subtraction, the associativity matters:
// fold_right([1, 2, 3], 0, |a, b| a - b)
//   = 1 - (2 - (3 - 0))
//   = 1 - (2 - 3)
//   = 1 - (-1)
//   = 2
let result = VecF::fold_right(vec![1, 2, 3], 0, |a, b| a - b);
assert_eq!(result, 2);
}

Traversable

Traversable

A Functor + Foldable that can be traversed with an effectful function.

Signature

#![allow(unused)]
fn main() {
pub trait Traversable: Functor + Foldable {
    fn traverse<G, A, B, F>(fa: Self::Of<A>, f: F) -> G::Of<Self::Of<B>>
    where
        G: Applicative,
        F: Fn(A) -> G::Of<B>,
        B: Clone;
}
}

traverse applies an effectful function f to every element in the structure, collecting the results inside the effect G. If any application of f produces a "failure" (e.g. None for OptionF), the entire traversal short-circuits.

Laws

Identity

traverse::<IdentityF, _, _, _>(fa, pure) == pure(fa)

Composition

traverse::<Compose<F, G>, _, _, _>(fa, |a| Compose(F::fmap(f(a), g)))
== Compose(F::fmap(traverse::<F, _, _, _>(fa, f), |fb| traverse::<G, _, _, _>(fb, g)))

Naturality

t(traverse::<F, _, _, _>(fa, f)) == traverse::<G, _, _, _>(fa, |a| t(f(a)))
for any applicative natural transformation t: F ~> G

Karpal verifies the Identity law with property-based tests using OptionF as the effect.

Instances

Example: traverse with Option

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Parse a list of strings into integers, failing if any parse fails.
fn parse(s: &str) -> Option<i32> {
    s.parse().ok()
}

// All elements parse successfully:
let result = VecF::traverse::<OptionF, _, _, _>(
    vec!["1", "2", "3"],
    parse,
);
assert_eq!(result, Some(vec![1, 2, 3]));

// One element fails, so the whole traversal returns None:
let result = VecF::traverse::<OptionF, _, _, _>(
    vec!["1", "oops", "3"],
    parse,
);
assert_eq!(result, None);
}

Example: traverse over Option

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Traverse an Option with an effectful function:
let result = OptionF::traverse::<OptionF, _, _, _>(
    Some(3),
    |x| Some(x * 2),
);
assert_eq!(result, Some(Some(6)));

// If the inner effect fails:
let result = OptionF::traverse::<OptionF, _, _, _>(
    Some(3),
    |_x| None::<i32>,
);
assert_eq!(result, None);

// Traversing None always succeeds:
let result = OptionF::traverse::<OptionF, i32, i32, _>(
    None,
    |x| Some(x * 2),
);
assert_eq!(result, Some(None));
}

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

FunctorFilter & Selective

Filtering and conditional execution within functorial contexts.

FunctorFilter

FunctorFilter

A Functor that can filter elements during mapping. filter_map applies a function that may return None to discard elements, combining mapping and filtering in a single pass.

Signature

#![allow(unused)]
fn main() {
pub trait FunctorFilter: Functor {
    fn filter_map<A, B>(fa: Self::Of<A>, f: impl Fn(A) -> Option<B>) -> Self::Of<B>;

    fn filter<A: Clone>(fa: Self::Of<A>, pred: impl Fn(&A) -> bool) -> Self::Of<A> {
        Self::filter_map(fa, |a| if pred(&a) { Some(a) } else { None })
    }
}
}

Methods

Laws

• Identity: filter_map(fa, Some) == fa — mapping with Some (which never discards) is a no-op.
• Composition: filter_map(filter_map(fa, f), g) == filter_map(fa, |a| f(a).and_then(g)) — two successive filter-maps can be fused into one.

Instances

ResultF<E> does not implement FunctorFilter because filtering a Result would require a default error value (E: Default), which is too restrictive.

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// filter_map: keep only positive values, doubled
let nums = vec![1, -2, 3, -4, 5];
let result = VecF::filter_map(nums, |x| {
    if x > 0 { Some(x * 2) } else { None }
});
assert_eq!(result, vec![2, 6, 10]);

// filter: keep only even numbers
let nums = vec![1, 2, 3, 4, 5, 6];
let evens = VecF::filter(nums, |x| x % 2 == 0);
assert_eq!(evens, vec![2, 4, 6]);

// With OptionF: filter_map acts like and_then
let value = OptionF::filter_map(Some(10), |x| {
    if x > 5 { Some(x * 3) } else { None }
});
assert_eq!(value, Some(30));

let rejected = OptionF::filter_map(Some(2), |x| {
    if x > 5 { Some(x * 3) } else { None }
});
assert_eq!(rejected, None);
}

Selective

Selective

An Applicative that can conditionally apply effects. Selective sits between Applicative and Monad in expressive power: it can branch on a value inside the functor without requiring full monadic bind. The branching is encoded using Result<A, B> where Ok(a) means "needs the function applied" and Err(b) means "already resolved."

Signature

#![allow(unused)]
fn main() {
pub trait Selective: Applicative {
    fn select<A, B, F>(fab: Self::Of<Result<A, B>>, ff: Self::Of<F>) -> Self::Of<B>
    where
        A: Clone,
        F: Fn(A) -> B;
}
}

Methods

Laws

• Identity: select(fmap(Err, x), _) == x — when every value is already resolved (wrapped in Err), the function argument is never used and the original values pass through unchanged.

Instances

Branching semantics

The Result inside the first argument encodes a choice:

Example

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

// Ok branch: the function is applied
let result = OptionF::select(
    Some(Ok(3i32)),
    Some(|x: i32| x * 2),
);
assert_eq!(result, Some(6));

// Err branch: already resolved, function is ignored
let result = OptionF::select(
    Some(Err(42i32)),
    Some(|_x: i32| 0),
);
assert_eq!(result, Some(42));

// None propagation: no value means no result
let result = OptionF::select(
    None::<Result<i32, i32>>,
    Some(|x: i32| x * 2),
);
assert_eq!(result, None);

// Ok branch but no function available
let result = OptionF::select(
    Some(Ok(3i32)),
    None::<fn(i32) -> i32>,
);
assert_eq!(result, None);
}

When to use Selective

Selective is useful when you need conditional logic inside a functorial pipeline but do not need the full power of Monad. Because the branching is encoded in the type (Result<A, B>) rather than in arbitrary closures, selective computations can be analyzed statically — making them suitable for scenarios like build systems or task schedulers where you want to inspect the structure of a computation before running it.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Macros

Monadic and applicative notation macros.

Karpal provides two macros that flatten nested monadic and applicative computations into a readable, top-to-bottom sequence of bindings. Both macros use = for binding (not <-, which is reserved in Rust edition 2024).

do_!

Monadic do-notation. Desugars sequential bindings into nested Chain::chain calls.

Syntax

#![allow(unused)]
fn main() {
do_! { F;
    x = monadic_expr_1;
    y = monadic_expr_2;   // can reference x
    // ... more bindings ...
    final_monadic_expr     // bare expression, no binding
}
}

• The first token F is the type constructor (OptionF, VecF, ResultF<E>, etc.), followed by a semicolon.
• Each binding uses =. Later bindings can reference names bound earlier -- the steps are sequential.
• The final line is a bare expression of type F::Of<T>. It is the value returned by the whole do_! block.
• If any step produces a short-circuiting value (None, Err(_)), the entire block short-circuits immediately.

Expansion

Each x = expr; binding desugars into a Chain::chain call. The macro expands recursively:

#![allow(unused)]
fn main() {
// This:
do_! { F;
    x = expr_a;
    y = expr_b;
    expr_c
}

// Expands to:
<F as Chain>::chain(expr_a, |x| {
    <F as Chain>::chain(expr_b, |y| {
        expr_c
    })
})
}

A single bare expression (no bindings) is returned as-is:

#![allow(unused)]
fn main() {
do_! { F; some_expr }
// Expands to:
some_expr
}

Requirements

The type constructor F must implement Chain (and therefore Apply and Functor). In practice, any type that implements Monad satisfies this requirement, since Monad is a blanket trait over Applicative + Chain.

Examples

OptionF -- sequential computation with short-circuiting

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = do_! { OptionF;
    x = Some(1);
    y = Some(x + 1);       // y depends on x
    OptionF::pure(x + y)   // final expression wraps in Some
};
assert_eq!(result, Some(3));
}

OptionF -- short-circuiting on None

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result: Option<i32> = do_! { OptionF;
    x = Some(1);
    _y = None::<i32>;     // short-circuits here
    OptionF::pure(x)       // never reached
};
assert_eq!(result, None);
}

OptionF -- single expression (no bindings)

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = do_! { OptionF;
    Some(42)
};
assert_eq!(result, Some(42));
}

ResultF -- chaining fallible operations

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

fn parse_port(s: &str) -> Result<u16, String> {
    s.parse::<u16>().map_err(|e| e.to_string())
}

let result = do_! { ResultF<String>;
    port = parse_port("8080");
    validated = if port > 0 { Ok(port) } else { Err("invalid".into()) };
    Ok(format!("port={}", validated))
};
assert_eq!(result, Ok("port=8080".to_string()));
}

VecF -- list comprehension (cartesian product)

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = do_! { VecF;
    x = vec![1, 2];
    y = vec![10, 20];
    VecF::pure(x + y)
};
assert_eq!(result, vec![11, 21, 12, 22]);
}

ado_!

Applicative do-notation. Collects independent bindings and combines them with Apply::ap and Functor::fmap.

Syntax

#![allow(unused)]
fn main() {
ado_! { F;
    x = applicative_expr_1;
    y = applicative_expr_2;
    // ... up to 4 bindings ...
    yield combining_expression
}
}

• Same first-token convention as do_!: the type constructor, then a semicolon.
• Each binding uses =. Bindings are independent and must not reference each other.
• The yield keyword introduces the combining expression. This expression is a pure function of the bound names -- it is automatically lifted into the applicative context.
• Supports 1 to 4 bindings.
• If any binding evaluates to a short-circuiting value (None, Err(_)), the whole block short-circuits.

Expansion

The expansion depends on the number of bindings. With one binding, the macro uses Functor::fmap. With two or more, it builds a curried closure and applies it with Apply::ap:

1 binding

#![allow(unused)]
fn main() {
// This:
ado_! { F; x = expr; yield body }

// Expands to:
<F as Functor>::fmap(expr, |x| body)
}

2 bindings

#![allow(unused)]
fn main() {
// This:
ado_! { F; x = e1; y = e2; yield body }

// Expands to:
<F as Apply>::ap(
    <F as Functor>::fmap(e1, |x| move |y| body),
    e2,
)
}

3 bindings

#![allow(unused)]
fn main() {
// This:
ado_! { F; x = e1; y = e2; z = e3; yield body }

// Expands to:
<F as Apply>::ap(
    <F as Apply>::ap(
        <F as Functor>::fmap(e1, |x| move |y| move |z| body),
        e2,
    ),
    e3,
)
}

4 bindings

#![allow(unused)]
fn main() {
// This:
ado_! { F; a = e1; b = e2; c = e3; d = e4; yield body }

// Expands to:
<F as Apply>::ap(
    <F as Apply>::ap(
        <F as Apply>::ap(
            <F as Functor>::fmap(e1, |a| move |b| move |c| move |d| body),
            e2,
        ),
        e3,
    ),
    e4,
)
}

Requirements

The type constructor F must implement Applicative (and therefore Apply and Functor). Unlike do_!, it does not require Chain -- applicative computations are strictly less powerful than monadic ones, which is the point: they express the absence of sequential dependencies.

Examples

OptionF -- single binding (fmap)

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { OptionF;
    x = Some(5);
    yield x * 2
};
assert_eq!(result, Some(10));
}

OptionF -- combining two independent values

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { OptionF;
    x = Some(1);
    y = Some(2);
    yield x + y
};
assert_eq!(result, Some(3));
}

OptionF -- short-circuiting on None

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { OptionF;
    x = Some(1);
    y = None::<i32>;
    yield x + y
};
assert_eq!(result, None);
}

OptionF -- combining three values

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { OptionF;
    x = Some(1);
    y = Some(2);
    z = Some(3);
    yield x + y + z
};
assert_eq!(result, Some(6));
}

OptionF -- combining four values

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { OptionF;
    a = Some(1);
    b = Some(2);
    c = Some(3);
    d = Some(4);
    yield a + b + c + d
};
assert_eq!(result, Some(10));
}

VecF -- cartesian product with applicative

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { VecF;
    x = vec![1, 2];
    y = vec![10, 20];
    yield x + y
};
assert_eq!(result, vec![11, 21, 12, 22]);
}

ResultF -- combining independent fallible lookups

#![allow(unused)]
fn main() {
use karpal_std::prelude::*;

let result = ado_! { ResultF<String>;
    host = Ok::<&str, String>("localhost");
    port = Ok::<u16, String>(3000);
    yield format!("{}:{}", host, port)
};
assert_eq!(result, Ok("localhost:3000".to_string()));
}

Choosing Between do_! and ado_!

Why = Instead of <-?

Languages like Haskell and PureScript use <- for monadic bindings. Karpal uses = instead because Rust edition 2024 reserves the <- token, making it unavailable inside macros. The = syntax integrates naturally with Rust's existing patterns and avoids any conflict with reserved tokens.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Comonad Family

Dual of the monad hierarchy: comonadic context and extraction.

Where a Monad lets you inject values into a context and sequence context-producing computations, a Comonad lets you extract values from a context and extend context-consuming functions across an entire structure. The comonad family in Karpal consists of five traits arranged in a linear hierarchy with three specialized branches.

Hierarchy

Functor → Extend → Comonad → ComonadEnv
Functor → Extend → Comonad → ComonadStore *
Functor → Extend → Comonad → ComonadTraced *

* Design note: ComonadStore and ComonadTraced require HKT (not Comonad) as their supertrait. This is because StoreF and TracedF use Box<dyn Fn> internally, which imposes 'static bounds that are incompatible with the generic Functor signature. Since Functor is a supertrait of Extend and Comonad, these types cannot implement the full comonad chain. Instead, they provide their own extract method directly on the trait, defined as a default method in terms of peek/trace.

Extend

Extend

The dual of Chain. Enables cooperative, context-aware computation.

Signature

#![allow(unused)]
fn main() {
pub trait Extend: Functor {
    fn extend<A, B>(wa: Self::Of<A>, f: impl Fn(&Self::Of<A>) -> B) -> Self::Of<B>
    where
        A: Clone;

    fn duplicate<A>(wa: Self::Of<A>) -> Self::Of<Self::Of<A>>
    where
        A: Clone,
        Self::Of<A>: Clone;
}
}

Given a value in context W<A> and a function &W<A> -> B that can inspect the full context, extend applies that function at every "position" in the structure, producing W<B>. The duplicate method has a default implementation: Self::extend(wa, |w| w.clone()).

Laws

Associativity

extend(f, extend(g, w)) == extend(|w| f(&extend(g, w.clone())), w)

Instances

Example

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

// NonEmptyVec extend: apply a summary function to each suffix
let nev = NonEmptyVec::new(1, vec![2, 3]);
let sums = NonEmptyVecF::extend(nev, |w| w.iter().sum::<i32>());
// Suffixes: [1,2,3], [2,3], [3]  =>  Sums: 6, 5, 3
assert_eq!(sums, NonEmptyVec::new(6, vec![5, 3]));

// Option extend
let doubled = OptionF::extend(Some(3), |opt| match opt {
    Some(x) => x * 2,
    None => 0,
});
assert_eq!(doubled, Some(6));

// duplicate: embed the structure inside itself
let nested = OptionF::duplicate(Some(42));
assert_eq!(nested, Some(Some(42)));
}

Comonad

Comonad

The categorical dual of Monad. Extract a value from context.

Signature

#![allow(unused)]
fn main() {
pub trait Comonad: Extend {
    fn extract<A: Clone>(wa: &Self::Of<A>) -> A;
}
}

A Comonad can extract a value from a context and extend a context-aware function over the entire structure. Where Monad::pure injects a value into a minimal context, Comonad::extract pulls a value out of an existing context.

Laws

Left identity

extract(&extend(w, f)) == f(&w)

Right identity

extend(w, |w| extract(w)) == w

Associativity is inherited from Extend.

Instances

Example

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

// Extract from NonEmptyVec: always returns the head
let nev = NonEmptyVec::new(10, vec![20, 30]);
assert_eq!(NonEmptyVecF::extract(&nev), 10);

// Extract from Env: discards the environment, keeps the value
assert_eq!(EnvF::<&str>::extract(&("config", 42)), 42);

// Left identity law in action:
let f = |w: &NonEmptyVec<i32>| w.head + 1;
let extended = NonEmptyVecF::extend(nev.clone(), f);
assert_eq!(NonEmptyVecF::extract(&extended), f(&nev));
}

ComonadEnv

ComonadEnv<E>

A Comonad with access to an environment value. Dual of Reader/MonadReader.

Signature

#![allow(unused)]
fn main() {
pub trait ComonadEnv<E>: Comonad {
    fn ask<A>(wa: &Self::Of<A>) -> E;
    fn local<A>(wa: Self::Of<A>, f: impl Fn(E) -> E) -> Self::Of<A>;
}
}

ask retrieves the environment from the comonadic value. local transforms the environment while leaving the focus value unchanged.

Laws

Local preserves extract

extract(local(wa, f)) == extract(wa)

Instances

Example

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

let w = ("hello", 42);

// ask: retrieve the environment
assert_eq!(EnvF::<&str>::ask(&w), "hello");

// local: transform the environment, keep the value
let w2 = (10i32, "value");
let result = EnvF::<i32>::local(w2, |e| e * 2);
assert_eq!(result, (20, "value"));

// Law: local does not change the extracted value
assert_eq!(
    EnvF::<i32>::extract(&EnvF::<i32>::local((5, 99), |e| e + 1)),
    EnvF::<i32>::extract(&(5, 99))
);
}

ComonadStore

ComonadStore<S>

A comonad with a notion of position and peeking. Dual of State.

Signature

#![allow(unused)]
fn main() {
pub trait ComonadStore<S>: HKT {
    fn pos<A>(wa: &Self::Of<A>) -> S;
    fn peek<A>(s: S, wa: &Self::Of<A>) -> A;

    /// Extract the focused value (equivalent to `peek(pos(wa), wa)`).
    fn extract<A>(wa: &Self::Of<A>) -> A
    where
        S: Clone;
}
}

pos returns the current position (index, key, cursor) within the store. peek retrieves the value at an arbitrary position. The default extract method is defined as peek(pos(wa), wa).

Design note: ComonadStore requires HKT rather than Comonad as its supertrait. StoreF<S> is represented as (Box<dyn Fn(S) -> A>, S), which requires 'static bounds on S. The generic Functor trait does not carry this bound, so StoreF cannot implement Functor and therefore cannot implement Extend or Comonad. The extract method is provided directly on this trait instead.

Laws

Peek-pos identity

peek(pos(wa), wa) == extract(wa)

Instances

Example

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

// A Store is a pair of (lookup function, current position)
let store: (Box<dyn Fn(i32) -> String>, i32) =
    (Box::new(|s| format!("value_{}", s)), 42);

// pos: get the current position
assert_eq!(StoreF::<i32>::pos(&store), 42);

// peek: look up the value at any position
assert_eq!(StoreF::<i32>::peek(10, &store), "value_10");

// extract: peek at the current position
assert_eq!(StoreF::<i32>::extract(&store), "value_42");
}

ComonadTraced

ComonadTraced<M: Monoid>

A comonad with a monoidal trace/accumulator. Dual of Writer.

Signature

#![allow(unused)]
fn main() {
pub trait ComonadTraced<M: Monoid>: HKT {
    fn trace<A>(m: M, wa: &Self::Of<A>) -> A;

    /// Extract the focused value (equivalent to `trace(M::empty(), wa)`).
    fn extract<A>(wa: &Self::Of<A>) -> A;
}
}

trace queries the comonadic value with a monoidal input. The default extract method traces with the monoidal identity (M::empty()), yielding the "current" value without any accumulated trace.

Design note: Like ComonadStore, this trait requires HKT rather than Comonad as its supertrait. TracedF<M> is represented as Box<dyn Fn(M) -> A>, which imposes 'static bounds incompatible with the generic Functor signature.

Laws

Identity trace

trace(M::empty(), wa) == extract(wa)

Instances

Example

#![allow(unused)]
fn main() {
use karpal_core::prelude::*;

// A Traced comonad is a function from a monoid to a value
let w: Box<dyn Fn(i32) -> String> = Box::new(|m| format!("traced_{}", m));

// trace: query with a specific monoidal value
assert_eq!(TracedF::<i32>::trace(5, &w), "traced_5");

// extract: trace with the monoidal identity (i32::empty() == 0)
assert_eq!(TracedF::<i32>::extract(&w), "traced_0");
}

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Contravariant Family

Contravariant functors and their combinators: the duals of the covariant hierarchy.

Where a covariant Functor consumes a function A -> B to transform F<A> into F<B>, a Contravariant functor consumes a function going the other way -- B -> A -- to transform F<A> into F<B>. The canonical example is a predicate: if you have a predicate on integers and a function that extracts an integer from a string, you can build a predicate on strings.

The contravariant family splits into two branches that mirror the covariant hierarchy:

• Product side: Contravariant → Divide → Divisible
• Sum side: Contravariant → Decide → Conclude

All contravariant types in Karpal are alloc-gated -- they require the std or alloc feature because they use Box<dyn Fn> internally.

Duality with the Covariant Hierarchy

Each contravariant trait is the dual of a corresponding covariant trait. The relationship is systematic: where the covariant side produces values, the contravariant side consumes them.

Contravariant

A functor that maps over inputs rather than outputs.

Signature

#![allow(unused)]
fn main() {
/// Contravariant functor: lifts a function `B -> A` into `F<A> -> F<B>`.
pub trait Contravariant: HKT {
    fn contramap<A: 'static, B>(
        fa: Self::Of<A>,
        f: impl Fn(B) -> A + 'static,
    ) -> Self::Of<B>;
}
}

Given a value of type F<A> and a function B -> A, contramap produces a value of type F<B>. The function goes in the opposite direction compared to Functor::fmap. The 'static bounds are required because PredicateF stores the function inside a Box<dyn Fn>.

Laws

Identity

Contramapping the identity function changes nothing:

#![allow(unused)]
fn main() {
Contravariant::contramap(fa, |x| x) == fa
}

Composition

Contramapping a composed function is the same as contramapping each function in sequence (note the reversed order):

#![allow(unused)]
fn main() {
contramap(f . g, fa) == contramap(g, contramap(f, fa))
}

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::contravariant::{Contravariant, PredicateF};

// A predicate on integers
let is_positive: Box<dyn Fn(i32) -> bool> = Box::new(|x| x > 0);

// Adapt it to work on strings by extracting the length
let str_len_positive = PredicateF::contramap(is_positive, |s: &str| s.len() as i32);

assert!(str_len_positive("hello"));  // len 5 > 0
assert!(!str_len_positive(""));      // len 0, not > 0
}

Divide

The contravariant analogue of Apply -- split an input into parts and handle each independently.

Signature

#![allow(unused)]
fn main() {
/// Divide: the contravariant analogue of Apply.
///
/// Given a way to split `C` into `(A, B)`, and contravariant functors over
/// `A` and `B`, produce a contravariant functor over `C`.
pub trait Divide: Contravariant {
    fn divide<A: 'static, B: 'static, C: 'static>(
        f: impl Fn(C) -> (A, B) + 'static,
        fa: Self::Of<A>,
        fb: Self::Of<B>,
    ) -> Self::Of<C>;
}
}

Where Apply combines two containers of outputs, Divide combines two consumers of inputs. The splitting function f decomposes the input C into a pair (A, B), then each part is handled by its respective consumer.

For PredicateF, divide produces a predicate that splits the input and returns true only if both sub-predicates accept their respective parts.

Laws

Associativity

Nesting divide on the left or right produces equivalent results, as long as the splitting functions decompose the input consistently:

#![allow(unused)]
fn main() {
divide(f, divide(g, a, b), c) == divide(h, a, divide(i, b, c))
}

Where f, g, h, and i are appropriate splitting functions that distribute the components equivalently.

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::contravariant::PredicateF;
use karpal_core::divide::Divide;

let is_positive: Box<dyn Fn(i32) -> bool> = Box::new(|x| x > 0);
let is_even: Box<dyn Fn(i32) -> bool> = Box::new(|x| x % 2 == 0);

// Split a tuple into its components, check both predicates
let both: Box<dyn Fn((i32, i32)) -> bool> =
    PredicateF::divide(|pair: (i32, i32)| pair, is_positive, is_even);

assert!(both((3, 4)));   // 3 > 0 AND 4 is even
assert!(!both((-1, 4))); // -1 is not > 0
assert!(!both((3, 3)));  // 3 is not even
}

Divisible

The contravariant analogue of Applicative -- adds an identity element for Divide.

Signature

#![allow(unused)]
fn main() {
/// Divisible: the contravariant analogue of Applicative.
///
/// Adds a `conquer` operation (the identity for `divide`), analogous to `pure`.
pub trait Divisible: Divide {
    fn conquer<A: 'static>() -> Self::Of<A>;
}
}

The conquer method produces a consumer that accepts any input and always succeeds. It is the identity element for divide -- dividing against a conquer() value has no effect on the result.

For PredicateF, conquer returns a predicate that is always true.

Laws

Left Identity

Dividing with conquer() on the left is equivalent to contramapping the second projection:

#![allow(unused)]
fn main() {
divide(f, conquer(), fa) == contramap(snd . f, fa)
}

Right Identity

Dividing with conquer() on the right is equivalent to contramapping the first projection:

#![allow(unused)]
fn main() {
divide(f, fa, conquer()) == contramap(fst . f, fa)
}

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::contravariant::PredicateF;
use karpal_core::divisible::Divisible;

// conquer() produces a predicate that accepts everything
let p: Box<dyn Fn(i32) -> bool> = PredicateF::conquer();
assert!(p(42));
assert!(p(-1));
assert!(p(0));
}

#![allow(unused)]
fn main() {
use karpal_core::contravariant::PredicateF;
use karpal_core::divide::Divide;
use karpal_core::divisible::Divisible;

// Left identity: divide with conquer() on the left has no effect
let fa: Box<dyn Fn(i32) -> bool> = Box::new(|a| a > 0);
let result = PredicateF::divide(
    |a: i32| ((), a),
    PredicateF::conquer::<()>(),
    fa,
);
assert!(result(5));   // equivalent to the original predicate
assert!(!result(-3));
}

Decide

The contravariant analogue of Alt -- route an input to one of two handlers.

Signature

#![allow(unused)]
fn main() {
/// Decide: the contravariant analogue of Alt.
///
/// Given a way to split `C` into either `A` or `B`, and contravariant
/// functors over `A` and `B`, produce a contravariant functor over `C`.
pub trait Decide: Contravariant {
    fn choose<A: 'static, B: 'static, C: 'static>(
        f: impl Fn(C) -> Result<A, B> + 'static,
        fa: Self::Of<A>,
        fb: Self::Of<B>,
    ) -> Self::Of<C>;
}
}

Where Divide handles the product case (split into both parts), Decide handles the sum case (route to one handler). The classification function f returns Result<A, B>, which serves as Karpal's encoding of Either: Ok(a) routes to fa, and Err(b) routes to fb.

For PredicateF, choose classifies the input and delegates to whichever predicate matches.

Laws

Associativity

Nesting choose on the left or right produces equivalent results, as long as the routing functions classify consistently:

#![allow(unused)]
fn main() {
choose(f, choose(g, a, b), c) == choose(h, a, choose(i, b, c))
}

Where f, g, h, and i are appropriate routing functions that distribute the cases equivalently.

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::contravariant::PredicateF;
use karpal_core::decide::Decide;

let is_positive: Box<dyn Fn(i32) -> bool> = Box::new(|x| x > 0);
let is_short: Box<dyn Fn(String) -> bool> = Box::new(|s| s.len() < 5);

// Classify input: integers go to Ok, strings go to Err
let classifier = PredicateF::choose(
    |input: Result<i32, String>| input,
    is_positive,
    is_short,
);

assert!(classifier(Ok(5)));                          // 5 > 0
assert!(!classifier(Ok(-1)));                        // -1 not > 0
assert!(classifier(Err("hi".to_string())));          // len 2 < 5
assert!(!classifier(Err("hello world".to_string()))); // len 11, not < 5
}

Conclude

The contravariant analogue of Plus -- the identity element for Decide.

Signature

#![allow(unused)]
fn main() {
/// Conclude: the contravariant analogue of Plus.
///
/// Adds a `conclude` operation (the identity for `choose`).
/// `conclude` takes a function `A -> Infallible`, witnessing that `A` is
/// uninhabited -- so the resulting predicate is vacuously true.
pub trait Conclude: Decide {
    fn conclude<A: 'static>(
        f: impl Fn(A) -> core::convert::Infallible + 'static,
    ) -> Self::Of<A>;
}
}

The conclude method takes a function from A to Infallible. If such a function exists, it witnesses that A is uninhabited -- no value of type A can ever be constructed. The resulting consumer is vacuously valid: it will never be called with a real input.

Rust uses core::convert::Infallible as its bottom type (the equivalent of Haskell's Void). For inhabited types, the function body typically uses unreachable!() since it can never actually execute in well-typed code.

For PredicateF, conclude returns a predicate that is always true.

Laws

Left Identity

Choosing with conclude(absurd) on the left is equivalent to contramapping the right projection:

#![allow(unused)]
fn main() {
choose(f, conclude(absurd), fa) == contramap(from_right . f, fa)
}

Right Identity

Choosing with conclude(absurd) on the right is equivalent to contramapping the left projection:

#![allow(unused)]
fn main() {
choose(f, fa, conclude(absurd)) == contramap(from_left . f, fa)
}

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::contravariant::PredicateF;
use karpal_core::conclude::Conclude;

// conclude with an unreachable function -- the predicate is vacuously true
let p: Box<dyn Fn(i32) -> bool> = PredicateF::conclude(|_: i32| unreachable!());
assert!(p(42));
assert!(p(-1));
}

#![allow(unused)]
fn main() {
use karpal_core::contravariant::PredicateF;
use karpal_core::decide::Decide;
use karpal_core::conclude::Conclude;

// Right identity: choosing with conclude on the right has no effect
let fa: Box<dyn Fn(i32) -> bool> = Box::new(|a| a > 0);
let result = PredicateF::choose(
    |a: i32| -> Result<i32, core::convert::Infallible> { Ok(a) },
    fa,
    PredicateF::conclude(|i: core::convert::Infallible| -> core::convert::Infallible { i }),
);
assert!(result(5));   // equivalent to the original predicate
assert!(!result(-3));
}

Combining Both Branches

In practice, Divide and Decide complement each other. Divide handles product types (structs, tuples) by splitting into fields, while Decide handles sum types (enums) by routing to the matching variant. Together they let you build validators and predicates for complex data structures compositionally:

#![allow(unused)]
fn main() {
use karpal_core::contravariant::{Contravariant, PredicateF};
use karpal_core::divide::Divide;
use karpal_core::decide::Decide;

// Field-level predicates
let name_valid: Box<dyn Fn(String) -> bool> = Box::new(|s| !s.is_empty());
let age_valid: Box<dyn Fn(i32) -> bool> = Box::new(|a| a >= 0 && a <= 150);

// Combine with Divide: validate a (name, age) pair
let person_valid: Box<dyn Fn((String, i32)) -> bool> =
    PredicateF::divide(|p: (String, i32)| p, name_valid, age_valid);

assert!(person_valid(("Alice".to_string(), 30)));
assert!(!person_valid(("".to_string(), 30)));       // empty name
assert!(!person_valid(("Alice".to_string(), -1)));   // negative age

// Sum-type routing with Decide: handle either a string or an integer
let str_check: Box<dyn Fn(String) -> bool> = Box::new(|s| s.len() < 10);
let int_check: Box<dyn Fn(i32) -> bool> = Box::new(|n| n > 0);

let either_check = PredicateF::choose(
    |input: Result<String, i32>| input,
    str_check,
    int_check,
);

assert!(either_check(Ok("short".to_string())));
assert!(!either_check(Err(-5)));
}

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Invariant

Invariant functors: mapping that requires both directions.

An Invariant functor generalizes both covariant (Functor) and contravariant (Contravariant) functors. Where a Functor only needs a forward function A -> B to transform its contents, and a Contravariant only needs a backward function B -> A, an Invariant functor requires both directions. This makes it the most general of the three -- any type that is either covariant or contravariant is automatically invariant as well.

Invariant

A functor that maps with both a covariant and contravariant function.

Signature

#![allow(unused)]
fn main() {
/// Invariant functor: maps with both a covariant and contravariant function.
///
/// Every covariant Functor is trivially Invariant (ignoring `g`).
/// Every Contravariant is also Invariant (ignoring `f`).
///
/// Laws:
/// - Identity: `invmap(fa, id, id) == fa`
/// - Composition: `invmap(fa, g1 . f1, f2 . g2) == invmap(invmap(fa, f1, f2), g1, g2)`
pub trait Invariant: HKT {
    fn invmap<A, B>(
        fa: Self::Of<A>,
        f: impl Fn(A) -> B,
        g: impl Fn(B) -> A,
    ) -> Self::Of<B>;
}
}

The invmap method takes a value in the functor (fa), a forward function f: A -> B, and a backward function g: B -> A, and produces a new value of type Self::Of<B>. The forward function f is used to transform values going out, and the backward function g is available for types that need to transform values going in.

Laws

Identity

Mapping with two identity functions changes nothing:

#![allow(unused)]
fn main() {
F::invmap(fa, |a| a, |a| a) == fa
}

If neither direction transforms the value, the structure is unchanged.

Composition

Composing two invmap calls is the same as composing the functions and calling invmap once:

#![allow(unused)]
fn main() {
F::invmap(fa, |a| g1(f1(a)), |a| f2(g2(a)))
    == F::invmap(F::invmap(fa, f1, f2), g1, g2)
}

The forward functions compose left-to-right (g1 . f1), while the backward functions compose right-to-left (f2 . g2). This mirrors how covariant and contravariant mappings compose in opposite directions.

Instances

All of the instances listed above are covariant functors, so they only use the forward function f and ignore the backward function g. A truly invariant type -- one that is neither covariant nor contravariant -- would need both functions. Such types arise in practice with bidirectional codecs, serializers/deserializers, and isomorphisms.

Examples

#![allow(unused)]
fn main() {
use karpal_core::hkt::{OptionF, VecF, IdentityF, EnvF, ResultF};
use karpal_core::invariant::Invariant;

// Option: maps Some values, passes through None
let doubled = OptionF::invmap(Some(3), |x| x * 2, |x| x / 2);
assert_eq!(doubled, Some(6));

let nothing = OptionF::invmap(None::<i32>, |x| x * 2, |x| x / 2);
assert_eq!(nothing, None);

// Result: maps Ok values, leaves Err unchanged
let ok = ResultF::<&str>::invmap(Ok(5), |x| x + 1, |x| x - 1);
assert_eq!(ok, Ok(6));

// Vec: maps each element
let scaled = VecF::invmap(vec![1, 2, 3], |x| x * 2, |x| x / 2);
assert_eq!(scaled, vec![2, 4, 6]);

// Identity: applies the function directly
let result = IdentityF::invmap(42, |x| x + 1, |x| x - 1);
assert_eq!(result, 43);

// Env: maps the value, keeps the environment
let env = EnvF::<&str>::invmap(("hello", 42), |x| x + 1, |x| x - 1);
assert_eq!(env, ("hello", 43));
}

Relationship to Functor and Contravariant

Invariant sits at the top of the variance hierarchy. Every Functor (covariant functor) is trivially Invariant: just ignore the backward function g and use f alone. Likewise, every Contravariant functor is trivially Invariant: just ignore the forward function f and use g alone.

#![allow(unused)]
fn main() {
// A Functor can implement Invariant by ignoring g:
//   fn invmap(fa, f, _g) { F::fmap(fa, f) }
//
// A Contravariant can implement Invariant by ignoring f:
//   fn invmap(fa, _f, g) { C::contramap(fa, g) }
}

This means Invariant captures the most general notion of "mappability" for a type constructor. It is useful when you need to abstract over types that may be covariant, contravariant, or neither -- for example, when building generic codec or serialization frameworks where values flow in both directions.

In Karpal, all provided instances happen to be covariant (they are all Functors), so they ignore g. However, the Invariant trait is available for user-defined types that genuinely require both directions.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Bifunctor & NaturalTransformation

Two-parameter functors and structure-preserving transformations.

These two abstractions sit alongside the main Functor hierarchy but address different concerns. Bifunctor generalizes mapping over type constructors with two type parameters (using HKT2), while NaturalTransformation provides a way to convert between two single-parameter type constructors without inspecting the contained values.

Bifunctor

Maps over both type parameters of a two-parameter type constructor.

Signature

#![allow(unused)]
fn main() {
/// Bifunctor: maps over both type parameters of a two-parameter type constructor.
///
/// Laws:
/// - Identity: `bimap(id, id, fab) == fab`
/// - Composition: `bimap(f . g, h . i, fab) == bimap(f, h, bimap(g, i, fab))`
pub trait Bifunctor: HKT2 {
    fn bimap<A, B, C, D>(
        fab: Self::P<A, B>,
        f: impl Fn(A) -> C,
        g: impl Fn(B) -> D,
    ) -> Self::P<C, D>;

    fn first<A, B, C>(fab: Self::P<A, B>, f: impl Fn(A) -> C) -> Self::P<C, B> {
        Self::bimap(fab, f, |b| b)
    }

    fn second<A, B, D>(fab: Self::P<A, B>, g: impl Fn(B) -> D) -> Self::P<A, D> {
        Self::bimap(fab, |a| a, g)
    }
}
}

The bimap method applies two functions simultaneously -- one to each type parameter. The first and second methods are convenience shortcuts that map over only one parameter, leaving the other unchanged. Both have default implementations in terms of bimap.

Note that Bifunctor extends HKT2, the two-parameter higher-kinded type trait. Where HKT has type Of<T>, HKT2 has type P<A, B>, reflecting the two type parameters.

Laws

Identity

Mapping two identity functions over a value must return it unchanged:

#![allow(unused)]
fn main() {
F::bimap(fab, |a| a, |b| b) == fab
}

Composition

Mapping composed functions must equal mapping in two steps:

#![allow(unused)]
fn main() {
F::bimap(fab, |a| f(g(a)), |b| h(i(b)))
    == F::bimap(F::bimap(fab, g, i), f, h)
}

Instances

Note that ResultBF places the first type parameter in the Err position and the second in the Ok position (P<A, B> = Result<B, A>). This is consistent with the Bifunctor convention where the second parameter is the "main" one, matching how ResultF<E> treats the Ok value as the functor target.

Examples

#![allow(unused)]
fn main() {
use karpal_core::bifunctor::Bifunctor;
use karpal_core::hkt::{ResultBF, TupleF};

// bimap over a Result: transform both Ok and Err sides
let r: Result<i32, &str> = Ok(5);
let result = ResultBF::bimap(r, |s| s.len(), |n| n * 2);
assert_eq!(result, Ok(10));

let r: Result<i32, &str> = Err("hello");
let result = ResultBF::bimap(r, |s| s.len(), |n| n * 2);
assert_eq!(result, Err(5));

// bimap over a tuple: transform both elements
assert_eq!(TupleF::bimap((1, "hi"), |x| x + 1, |s| s.len()), (2, 2));

// first and second: map over one side only
assert_eq!(TupleF::first((1, "hi"), |x| x * 2), (2, "hi"));
assert_eq!(TupleF::second((1, "hi"), |s| s.len()), (1, 2));

// first on Result maps the Err side
let r: Result<i32, &str> = Err("hi");
assert_eq!(ResultBF::first(r, |s| s.len()), Err(2));

// second on Result maps the Ok side
let r: Result<i32, &str> = Ok(5);
assert_eq!(ResultBF::second(r, |n| n * 3), Ok(15));
}

NaturalTransformation

A structure-preserving mapping between two type constructors.

Signature

#![allow(unused)]
fn main() {
/// Natural transformation: a mapping between two functors that preserves structure.
///
/// Laws:
/// - Naturality: `fmap_G(f, transform(fa)) == transform(fmap_F(f, fa))`
pub trait NaturalTransformation<F: HKT, G: HKT> {
    fn transform<A>(fa: F::Of<A>) -> G::Of<A>;
}
}

A NaturalTransformation converts a value from one type constructor into another without knowing or caring about the contained type A. The trait is parameterized by two HKT type constructors, F (source) and G (target), and the implementing struct serves as a named witness for the transformation.

Because the transform method is generic over A, it cannot inspect or modify the contained values -- it can only restructure the container. This is the key property that the naturality law captures.

Laws

Naturality

Mapping a function f over the result of transform must equal transforming after mapping f over the original:

#![allow(unused)]
fn main() {
G::fmap(NT::transform(fa), f) == NT::transform(F::fmap(fa, f))
}

In other words, it does not matter whether you map first and then transform, or transform first and then map. The diagram commutes.

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_core::natural::{NaturalTransformation, OptionToVec, VecHeadToOption};

// OptionToVec: convert Option into a zero-or-one-element Vec
assert_eq!(OptionToVec::transform(Some(42)), vec![42]);
assert_eq!(OptionToVec::transform(None::<i32>), Vec::<i32>::new());

// VecHeadToOption: extract the first element as an Option
assert_eq!(VecHeadToOption::transform(vec![1, 2, 3]), Some(1));
assert_eq!(VecHeadToOption::transform(Vec::<i32>::new()), None);
}

Verifying the naturality law

The naturality law can be checked for any function f. Here is a concrete example with OptionToVec:

#![allow(unused)]
fn main() {
use karpal_core::functor::Functor;
use karpal_core::hkt::{OptionF, VecF};
use karpal_core::natural::{NaturalTransformation, OptionToVec};

let x: Option<i32> = Some(5);
let f = |a: i32| a + 1;

// Map then transform
let left = OptionToVec::transform(OptionF::fmap(x, f));

// Transform then map
let right = VecF::fmap(OptionToVec::transform(x), f);

assert_eq!(left, right); // both are vec![6]
}

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Profunctor Family

Profunctors: contravariant in the first argument, covariant in the second.

The profunctor family lives in the karpal-profunctor crate and provides the abstract machinery behind Karpal's profunctor optics. Where a Functor transforms values inside a single type parameter, a Profunctor transforms values flowing through a two-parameter type -- think of it as a pipe with an input end and an output end. You can pre-process the input (contravariantly) and post-process the output (covariantly) without opening the pipe.

Hierarchy

The profunctor hierarchy branches into subclasses, each enabling a different family of optics:

#![allow(unused)]
fn main() {
HKT2
  |
Profunctor          -- dimap, lmap, rmap            (Iso)
  |         \
Strong     Choice                                   (Lens / Prism)
  |           |
  +-----------+
        |
    Traversing      -- wander                       (Traversal)
}

• Profunctor -- the base trait. Provides dimap for simultaneous pre- and post-processing. Powers Iso.
• Strong -- lifts a profunctor through product types (tuples). Powers Lens.
• Choice -- lifts a profunctor through sum types (Result). Powers Prism.
• Traversing -- extends Strong + Choice to handle multiple foci. Powers Traversal.

All three traits require the HKT2 encoding from karpal-core:

#![allow(unused)]
fn main() {
pub trait HKT2 {
    type P<A, B>;
}
}

A type implementing HKT2 is a two-parameter type constructor. Given types A and B, it produces a concrete type P<A, B>.

Profunctor

A type that is contravariant in its first argument and covariant in its second.

Signature

#![allow(unused)]
fn main() {
/// A profunctor is contravariant in its first argument and covariant in its second.
pub trait Profunctor: HKT2 {
    fn dimap<A: 'static, B: 'static, C, D>(
        f: impl Fn(C) -> A + 'static,
        g: impl Fn(B) -> D + 'static,
        pab: Self::P<A, B>,
    ) -> Self::P<C, D>;

    fn lmap<A: 'static, B: 'static, C>(
        f: impl Fn(C) -> A + 'static,
        pab: Self::P<A, B>,
    ) -> Self::P<C, B> { ... }

    fn rmap<A: 'static, B: 'static, D>(
        g: impl Fn(B) -> D + 'static,
        pab: Self::P<A, B>,
    ) -> Self::P<A, D> { ... }
}
}

dimap is the fundamental operation. It takes a function f: C -> A that pre-processes the input (contravariant -- note the reversed direction) and a function g: B -> D that post-processes the output (covariant), then adapts the profunctor P<A, B> into P<C, D>.

The convenience methods lmap and rmap have default implementations in terms of dimap:

• lmap(f, pab) -- pre-process the input only. Equivalent to dimap(f, |b| b, pab).
• rmap(g, pab) -- post-process the output only. Equivalent to dimap(|a| a, g, pab).

Laws

Identity

Dimapping with identity functions on both sides changes nothing:

#![allow(unused)]
fn main() {
P::dimap(|a| a, |b| b, pab) == pab
}

Composition

Dimapping with composed functions is the same as dimapping twice:

#![allow(unused)]
fn main() {
P::dimap(|a| f(g(a)), |b| h(i(b)), pab)
    == P::dimap(g, h, P::dimap(f, i, pab))
}

Note the order reversal on the contravariant (left) side: f then g becomes |a| f(g(a)), because contravariance reverses composition.

Instances

Examples

#![allow(unused)]
fn main() {
use karpal_profunctor::{Profunctor, FnP};

// A simple doubling function as a profunctor value
let double: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);

// dimap: parse a string to i32 on the input side,
//        format the i32 result to a string on the output side
let f = FnP::dimap(
    |s: &str| s.len() as i32,  // contravariant: &str -> i32
    |n: i32| n.to_string(),     // covariant: i32 -> String
    double,
);
assert_eq!(f("hello"), "10"); // len("hello") = 5, doubled = 10

// lmap: only pre-process the input
let negate: Box<dyn Fn(i32) -> i32> = Box::new(|x| -x);
let neg_len = FnP::lmap(|s: &str| s.len() as i32, negate);
assert_eq!(neg_len("hi"), -2);

// rmap: only post-process the output
let add_one: Box<dyn Fn(i32) -> i32> = Box::new(|x| x + 1);
let as_string = FnP::rmap(|n: i32| format!("result: {}", n), add_one);
assert_eq!(as_string(9), "result: 10");
}

Strong

A profunctor that can be lifted through product types (tuples).

Signature

#![allow(unused)]
fn main() {
pub trait Strong: Profunctor {
    fn first<A, B, C>(pab: Self::P<A, B>) -> Self::P<(A, C), (B, C)>
    where
        A: 'static,
        B: 'static,
        C: 'static;

    fn second<A, B, C>(pab: Self::P<A, B>) -> Self::P<(C, A), (C, B)>
    where
        A: 'static,
        B: 'static,
        C: 'static;
}
}

first takes a profunctor P<A, B> and lifts it to operate on the first component of a tuple, passing the second component C through unchanged. second does the mirror image -- it operates on the second component and passes the first through.

Laws

First-Dimap Coherence

Lifting through first and then dimapping with tuple projections is consistent:

#![allow(unused)]
fn main() {
P::lmap(|(a, _)| a, P::first(pab))
    == P::rmap(|b| (b, ()), pab)  // up to isomorphism with unit
}

First-First Coherence

Nesting first twice is equivalent to first once with a tuple reassociation:

#![allow(unused)]
fn main() {
P::first(P::first(pab))
    == P::dimap(
        |((a, c1), c2)| (a, (c1, c2)),  // reassociate in
        |(b, (c1, c2))| ((b, c1), c2),  // reassociate out
        P::first(pab),
    )
}

Instances

TaggedF is deliberately not Strong. This enforces at the type level that write-only optics (like Review) cannot be used for reading -- Strong requires producing a (B, C) from a B, but TaggedF has no way to produce the C.

Connection to Lens

A Lens is defined as a function that works for all profunctors that are Strong. The lens transform method takes a P<A, B> and returns a P<S, T> by using Strong::first (or second) together with Profunctor::dimap to focus on a part of a structure:

#![allow(unused)]
fn main() {
// Conceptually, a lens from S to A (with update types T and B) is:
//   for all P: Strong, P<A, B> -> P<S, T>
//
// Implemented as:
//   dimap(getter_and_context, setter, first(pab))
//
// where:
//   getter_and_context: S -> (A, Context)
//   setter: (B, Context) -> T
}

Strong::first lifts the profunctor to work on a tuple (A, Context), and dimap adapts the outer structure S/T to and from that tuple. This is how profunctor optics achieve composability -- lens composition is just function composition of these transforms.

Examples

#![allow(unused)]
fn main() {
use karpal_profunctor::{Strong, FnP};

let double: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);

// first: apply to the first element of a tuple
let f = FnP::first::<i32, i32, &str>(double);
assert_eq!(f((5, "hi")), (10, "hi"));

// second: apply to the second element of a tuple
let triple: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 3);
let g = FnP::second::<i32, i32, &str>(triple);
assert_eq!(g(("hi", 5)), ("hi", 15));
}

Choice

A profunctor that can be lifted through sum types (Result).

Signature

#![allow(unused)]
fn main() {
pub trait Choice: Profunctor {
    fn left<A, B, C>(pab: Self::P<A, B>) -> Self::P<Result<A, C>, Result<B, C>>
    where
        A: 'static,
        B: 'static,
        C: 'static;

    fn right<A, B, C>(pab: Self::P<A, B>) -> Self::P<Result<C, A>, Result<C, B>>
    where
        A: 'static,
        B: 'static,
        C: 'static;
}
}

Karpal uses Result<L, R> as the sum type rather than a custom Either -- this is idiomatic Rust and avoids an unnecessary new type. left lifts a profunctor to operate on the Ok branch of a Result, passing the Err branch through unchanged. right does the mirror image, operating on the Err branch.

Laws

Left-Dimap Coherence

Lifting through left and then extracting the Ok branch is consistent:

#![allow(unused)]
fn main() {
P::lmap(|a| Ok(a), P::left(pab))
    == P::rmap(|b| Ok(b), pab)
}

Left-Left Coherence

Nesting left twice is equivalent to left once with a Result reassociation:

#![allow(unused)]
fn main() {
P::left(P::left(pab))
    == P::dimap(
        |r| match r {                       // reassociate in
            Ok(Ok(a))  => Ok(a),
            Ok(Err(c)) => Err(Ok(c)),
            Err(d)     => Err(Err(d)),
        },
        |r| match r {                       // reassociate out
            Ok(b)      => Ok(Ok(b)),
            Err(Ok(c)) => Ok(Err(c)),
            Err(Err(d)) => Err(d),
        },
        P::left(pab),
    )
}

Instances

ForgetF's Choice impl requires R: Monoid because the miss case needs a default value (R::empty()). Its Strong impl has no such restriction -- products always have the focus available.

Connection to Prism

A Prism is defined as a function that works for all profunctors that are Choice. The prism transform method takes a P<A, B> and returns a P<S, T> by using Choice::right together with Profunctor::dimap to focus on one variant of a sum type:

#![allow(unused)]
fn main() {
// Conceptually, a prism from S to A (with update types T and B) is:
//   for all P: Choice, P<A, B> -> P<S, T>
//
// Implemented as:
//   dimap(match_, merge, right(pab))
//
// where:
//   match_: S -> Result<T, A>   (try to extract A, or return T unchanged)
//   merge:  Result<T, B> -> T   (re-inject the modified value)
}

When the match_ function successfully extracts an A, the profunctor processes it into a B; otherwise the original T passes through untouched. Choice::right ensures that only the matched branch is transformed. This is the dual of how Strong powers lenses: lenses focus through products, prisms focus through sums.

Examples

#![allow(unused)]
fn main() {
use karpal_profunctor::{Choice, FnP};

let double: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);

// left: apply to the Ok branch
let f = FnP::left::<i32, i32, &str>(double);
assert_eq!(f(Ok(5)), Ok(10));
assert_eq!(f(Err("nope")), Err("nope"));

// right: apply to the Err branch
let triple: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 3);
let g = FnP::right::<i32, i32, &str>(triple);
assert_eq!(g(Err(5)), Err(15));
assert_eq!(g(Ok("yep")), Ok("yep"));
}

FnP (Function Profunctor)

Marker type whose P<A, B> is Box<dyn Fn(A) -> B> -- the canonical profunctor instance.

Definition

#![allow(unused)]
fn main() {
pub struct FnP;

impl HKT2 for FnP {
    type P<A, B> = Box<dyn Fn(A) -> B>;
}
}

FnP is a zero-sized marker type. It has no fields and no runtime cost -- it exists solely to carry the HKT2 type-level association between the marker and the concrete type Box<dyn Fn(A) -> B>.

This is the function arrow profunctor (sometimes written (->) in Haskell). It is the most natural profunctor: a function from A to B can be pre-composed with a function C -> A (contravariant input) and post-composed with a function B -> D (covariant output) to yield a function C -> D.

Feature gate

FnP requires the alloc feature because Box<dyn Fn> requires heap allocation. It is not available in no_std environments without an allocator. The Profunctor, Strong, and Choice traits themselves are no_std-compatible -- only the FnP instance needs alloc.

Implemented traits

Role in optics

FnP is the profunctor that optics use at the value level. When you call lens.set() or lens.over(), Karpal internally constructs a Box<dyn Fn(A) -> B> and passes it through the lens's transform method, which threads it through Strong::first and Profunctor::dimap. The result is a Box<dyn Fn(S) -> T> that performs the focused update on the whole structure. The same mechanism applies to prisms via Choice.

Because all the profunctor operations compose (they are just function wrapping), lens composition and prism composition are both achieved by chaining transform calls -- no special composition machinery is needed.

Example: building a pipeline with dimap

#![allow(unused)]
fn main() {
use karpal_profunctor::{Profunctor, FnP};

// Start with a base function: parse a number and add 1
let inc: Box<dyn Fn(i32) -> i32> = Box::new(|x| x + 1);

// Adapt it: input is a string (parse it), output is a string (format it)
let pipeline = FnP::dimap(
    |s: &str| s.parse::<i32>().unwrap_or(0),
    |n: i32| format!("result = {}", n),
    inc,
);

assert_eq!(pipeline("41"), "result = 42");
assert_eq!(pipeline("not a number"), "result = 1");
}

Traversing

A profunctor that can operate over multiple foci simultaneously.

Signature

#![allow(unused)]
fn main() {
pub trait Traversing: Strong + Choice {
    fn wander<S, T, A, B>(
        get_all: impl Fn(&S) -> Vec<A> + 'static,
        modify_all: impl Fn(S, &dyn Fn(A) -> B) -> T + 'static,
        pab: Self::P<A, B>,
    ) -> Self::P<S, T>
    where
        S: 'static, T: 'static, A: 'static, B: 'static;
}
}

Traversing extends Strong + Choice with the ability to handle multiple foci. The wander method takes two functions instead of a single polymorphic traversal function, because Rust lacks rank-2 types:

• get_all -- extracts all foci (used by read-only profunctors like ForgetF)
• modify_all -- applies a function to every focus in-place (used by read-write profunctors like FnP)

Instances

Connection to Traversal

A Traversal is defined as a function that works for all profunctors that are Traversing. The traversal's transform method calls P::wander(get_all, modify_all, pab) -- each profunctor instance decides how to interpret the traversal.

Example

#![allow(unused)]
fn main() {
use karpal_profunctor::{Traversing, FnP, ForgetF};

// wander with FnP: modify each element
let double: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);
let f = FnP::wander(
    |v: &Vec<i32>| v.clone(),
    |v: Vec<i32>, f: &dyn Fn(i32) -> i32| v.into_iter().map(f).collect(),
    double,
);
assert_eq!(f(vec![1, 2, 3]), vec![2, 4, 6]);

// wander with ForgetF: accumulate with Monoid
let to_str: Box<dyn Fn(i32) -> String> = Box::new(|x| x.to_string());
let g = <ForgetF<String> as Traversing>::wander(
    |v: &Vec<i32>| v.clone(),
    |v: Vec<i32>, f: &dyn Fn(i32) -> String| { let _ = v; let _ = f; String::new() },
    to_str,
);
assert_eq!(g(vec![1, 2, 3]), "123"); // String Monoid concatenates
}

ForgetF<R> (Forget Profunctor)

Marker type whose P<A, B> is Box<dyn Fn(A) -> R> -- a read-only profunctor that extracts a summary value.

Definition

#![allow(unused)]
fn main() {
pub struct ForgetF<R>(PhantomData<R>);

impl<R: 'static> HKT2 for ForgetF<R> {
    type P<A, B> = Box<dyn Fn(A) -> R>;
}
}

ForgetF<R> "forgets" the output type B entirely -- the second type parameter is phantom. A ForgetF<R>::P<A, B> is just a function from A to R, regardless of what B is. This makes it ideal for read-only operations that extract or summarize data.

Implemented traits

Feature gate

Requires alloc (uses Box<dyn Fn> and Vec).

Role in optics

ForgetF is the profunctor behind read-only optics. When you use a Traversal with ForgetF<R>, you get a function S -> R that extracts and combines data from all foci using a Monoid. This is how Fold's fold_map works conceptually.

#![allow(unused)]
fn main() {
use karpal_profunctor::ForgetF;

// ForgetF ignores the B parameter completely
let extract: Box<dyn Fn(i32) -> String> = Box::new(|x| format!("got {x}"));

// B can be anything -- it's never used
let _: <ForgetF<String> as HKT2>::P<i32, Vec<u8>> = extract;
}

TaggedF (Tagged Profunctor)

Marker type whose P<A, B> is just B -- a write-only profunctor for construction.

Definition

#![allow(unused)]
fn main() {
pub struct TaggedF;

impl HKT2 for TaggedF {
    type P<A, B> = B;
}
}

TaggedF "forgets" the input type A entirely -- the first type parameter is phantom. A TaggedF::P<A, B> is just B, regardless of what A is. This makes it ideal for construction-only operations.

Implemented traits

TaggedF is deliberately not Strong and not Traversing. This is a deliberate design decision: Strong::first would need to produce a (B, C) from just a B, which is impossible without access to C. By not implementing Strong, the type system enforces that write-only optics like Review cannot be used for reading.

Feature gate

None -- TaggedF is no_std-compatible with no allocator requirement.

Role in optics

TaggedF is the profunctor behind write-only optics. A Review conceptually transforms a TaggedF::P<A, B> (which is just B) into a TaggedF::P<S, T> (which is just T) -- construction from a value.

Why 'static bounds?

You will notice that the type parameters on dimap, first, left, and so on require 'static bounds. This is a consequence of FnP's implementation: Box<dyn Fn(A) -> B> requires that the captured closures (and the types they close over) are 'static. Without this bound, the compiler cannot guarantee that the boxed closures outlive the scope in which they were created.

In practice, this means profunctor operations work with owned types and 'static references, but not with short-lived borrows. This is the same trade-off that Box<dyn Fn> imposes anywhere in Rust -- the profunctor abstraction does not add any additional restrictions beyond what the underlying representation requires.

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Arrow Family

Arrows generalize functions to computations with structured inputs and outputs. They extend the Profunctor idea -- a two-parameter type constructor with composition -- into a full algebra of composable pipelines with product routing, sum routing, application, looping, and failure.

The arrow family lives in the karpal-arrow crate and builds on the HKT2 encoding from karpal-core.

Trait Hierarchy

#![allow(unused)]
fn main() {
HKT2
 +-> Semigroupoid          compose(f, g)
     +-> Category           id()
         +-> Arrow           arr(f), first, second, split, fanout
              |-> ArrowChoice    left, right, splat, fanin
              |-> ArrowApply     app  (~ Monad)
              |-> ArrowLoop      loop_arrow  (D: Default)
              +-> ArrowZero      zero_arrow
                   +-> ArrowPlus  plus(f, g)
}

• Semigroupoid -- composable morphisms (associative composition).
• Category -- adds an identity morphism.
• Arrow -- lifts pure functions and routes through products (tuples).
• ArrowChoice -- routes through sum types (Result).
• ArrowApply -- first-class arrow application, equivalent in power to Monad.
• ArrowLoop -- feedback/fixpoint combinator using D: Default for strict evaluation.
• ArrowZero -- a failing/empty arrow.
• ArrowPlus -- associative choice between arrows.

Traits

Semigroupoid

Morphisms that can be composed associatively.

Signature

#![allow(unused)]
fn main() {
/// Semigroupoid: morphisms that can be composed.
///
/// Laws:
/// - Associativity: compose(f, compose(g, h)) == compose(compose(f, g), h)
pub trait Semigroupoid: HKT2 {
    fn compose<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        f: Self::P<B, C>,
        g: Self::P<A, B>,
    ) -> Self::P<A, C>;
}
}

compose chains two morphisms: given g: A -> B and f: B -> C, produce f . g: A -> C. Note the argument order -- f comes first, matching mathematical convention (f after g).

Laws

Associativity

Composition is associative:

#![allow(unused)]
fn main() {
P::compose(f, P::compose(g, h)) == P::compose(P::compose(f, g), h)
}

Category

A Semigroupoid with an identity morphism.

Signature

#![allow(unused)]
fn main() {
/// Category: a Semigroupoid with an identity morphism.
///
/// Laws:
/// - Left identity:  compose(id(), f) == f
/// - Right identity: compose(f, id()) == f
pub trait Category: Semigroupoid {
    fn id<A: Clone + 'static>() -> Self::P<A, A>;
}
}

id produces the identity morphism that, when composed with any other morphism, yields that morphism unchanged.

Laws

Left Identity

#![allow(unused)]
fn main() {
P::compose(P::id(), f) == f
}

Right Identity

#![allow(unused)]
fn main() {
P::compose(f, P::id()) == f
}

Arrow

A Category that can lift pure functions and operate on products (tuples).

Signature

#![allow(unused)]
fn main() {
/// Arrow: a Category that can lift pure functions and operate on products.
///
/// Laws:
/// - arr(id) == id()
/// - arr(|a| g(f(a))) == compose(arr(g), arr(f))
/// - first(arr(f)) == arr(|(a, c)| (f(a), c))
/// - first(compose(f, g)) == compose(first(f), first(g))
pub trait Arrow: Category {
    /// Lift a pure function into an arrow.
    fn arr<A: Clone + 'static, B: Clone + 'static>(
        f: impl Fn(A) -> B + 'static,
    ) -> Self::P<A, B>;

    /// Apply an arrow to the first component of a pair, passing the second through.
    fn first<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        pab: Self::P<A, B>,
    ) -> Self::P<(A, C), (B, C)>;

    /// Apply an arrow to the second component of a pair.
    fn second<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        pab: Self::P<A, B>,
    ) -> Self::P<(C, A), (C, B)> { ... }

    /// `***`: apply two arrows in parallel on a product.
    fn split<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static, D: Clone + 'static>(
        f: Self::P<A, B>,
        g: Self::P<C, D>,
    ) -> Self::P<(A, C), (B, D)> { ... }

    /// `&&&`: feed input to two arrows and collect results as a pair.
    fn fanout<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        f: Self::P<A, B>,
        g: Self::P<A, C>,
    ) -> Self::P<A, (B, C)> { ... }
}
}

arr lifts any pure function into the arrow. first applies an arrow to the first component of a tuple, passing the second through unchanged. second, split, and fanout have default implementations built from first, compose, and arr.

Laws

arr preserves identity

#![allow(unused)]
fn main() {
P::arr(|a| a) == P::id()
}

arr preserves composition

#![allow(unused)]
fn main() {
P::arr(|a| g(f(a))) == P::compose(P::arr(g), P::arr(f))
}

first/arr coherence

#![allow(unused)]
fn main() {
P::first(P::arr(f)) == P::arr(|(a, c)| (f(a), c))
}

first distributes over compose

#![allow(unused)]
fn main() {
P::first(P::compose(f, g)) == P::compose(P::first(f), P::first(g))
}

Derived Operations

• second(pab) -- default implementation swaps the tuple components, applies first, and swaps back.
• split(f, g) -- Haskell's *** operator. Applies f to the first component and g to the second: compose(second(g), first(f)).
• fanout(f, g) -- Haskell's &&& operator. Duplicates the input and applies f and g in parallel: compose(split(f, g), arr(|a| (a.clone(), a))).

ArrowChoice

An Arrow that can route through sum types (Result).

Signature

#![allow(unused)]
fn main() {
/// ArrowChoice: an Arrow that can route through sum types.
///
/// Uses `Result<L, R>` as the sum type, consistent with karpal-profunctor's Choice.
///
/// Laws:
/// - left(arr(f)) == arr(|r| r.map(f))
/// - left(compose(f, g)) == compose(left(f), left(g))
/// - compose(arr(Ok), f) == compose(left(f), arr(Ok))
pub trait ArrowChoice: Arrow {
    /// Route the Ok branch through the arrow, passing Err through.
    fn left<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        pab: Self::P<A, B>,
    ) -> Self::P<Result<A, C>, Result<B, C>>;

    /// Route the Err branch through the arrow, passing Ok through.
    fn right<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        pab: Self::P<A, B>,
    ) -> Self::P<Result<C, A>, Result<C, B>> { ... }

    /// `+++`: apply f on Ok, g on Err.
    fn splat<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static, D: Clone + 'static>(
        f: Self::P<A, B>,
        g: Self::P<C, D>,
    ) -> Self::P<Result<A, C>, Result<B, D>> { ... }

    /// `|||`: merge two arrows, one for each branch of Result.
    fn fanin<A: Clone + 'static, B: Clone + 'static, C: Clone + 'static>(
        f: Self::P<A, C>,
        g: Self::P<B, C>,
    ) -> Self::P<Result<A, B>, C> { ... }
}
}

left routes the Ok branch through the arrow, passing the Err branch through unchanged. right, splat, and fanin have default implementations. Karpal uses Result<L, R> as the sum type, consistent with Choice in karpal-profunctor.

Laws

left/arr coherence

#![allow(unused)]
fn main() {
P::left(P::arr(f)) == P::arr(|r| r.map(f))
}

left distributes over compose

#![allow(unused)]
fn main() {
P::left(P::compose(f, g)) == P::compose(P::left(f), P::left(g))
}

Derived Operations

• right(pab) -- mirrors the Result, applies left, and mirrors back.
• splat(f, g) -- Haskell's +++ operator. Applies f to Ok and g to Err: compose(right(g), left(f)).
• fanin(f, g) -- Haskell's ||| operator. Merges both branches into a single output: compose(merge, splat(f, g)).

ArrowApply

An Arrow that can apply arrows from within the computation. Equivalent in power to Monad.

Signature

#![allow(unused)]
fn main() {
/// ArrowApply: an Arrow that can apply arrows from within the computation.
///
/// Equivalent in power to Monad (ArrowApply ~ Monad via Kleisli).
pub trait ArrowApply: Arrow {
    fn app<A: Clone + 'static, B: Clone + 'static>()
        -> Self::P<(Self::P<A, B>, A), B>;
}
}

app takes a pair of an arrow and an input value, and applies the arrow to the value. This gives arrows the ability to choose which arrow to run at runtime, making ArrowApply equivalent in power to Monad (via the Kleisli correspondence).

ArrowLoop

An Arrow with a loop/fixpoint combinator.

Signature

#![allow(unused)]
fn main() {
/// ArrowLoop: an Arrow with a loop/fixpoint combinator.
///
/// Takes an arrow from `(A, D)` to `(B, D)` and produces an arrow from `A` to `B`,
/// where `D` is the "feedback" type threaded through the loop.
///
/// In Haskell, `loop` relies on laziness to tie the knot. Rust is strict, so
/// `D: Default` provides the initial feedback seed and the implementation uses
/// single-pass evaluation.
pub trait ArrowLoop: Arrow {
    fn loop_arrow<A: Clone + 'static, B: Clone + 'static, D: Default + Clone + 'static>(
        f: Self::P<(A, D), (B, D)>,
    ) -> Self::P<A, B>;
}
}

loop_arrow takes an arrow from (A, D) to (B, D) and produces an arrow from A to B, where D is the feedback type. In Haskell, loop relies on laziness to tie the knot. Since Rust is strict, the D: Default bound provides the initial feedback seed and the implementation uses single-pass evaluation.

ArrowZero

An Arrow with a zero (failing/empty) morphism.

Signature

#![allow(unused)]
fn main() {
/// ArrowZero: an Arrow with a zero (failing/empty) morphism.
///
/// Laws:
/// - compose(zero_arrow(), f) == zero_arrow()  (left absorption)
pub trait ArrowZero: Arrow {
    fn zero_arrow<A: Clone + 'static, B: Clone + 'static>() -> Self::P<A, B>;
}
}

zero_arrow produces an arrow that always fails or returns empty. It absorbs any composition from the left: composing anything after a zero_arrow still yields zero_arrow.

Laws

Left Absorption

#![allow(unused)]
fn main() {
P::compose(P::zero_arrow(), f) == P::zero_arrow()
}

ArrowPlus

An ArrowZero with an associative choice operation.

Signature

#![allow(unused)]
fn main() {
/// ArrowPlus: an ArrowZero with an associative choice operation.
///
/// Laws:
/// - Associativity: plus(plus(f, g), h) == plus(f, plus(g, h))
/// - Left identity:  plus(zero_arrow(), f) == f
/// - Right identity: plus(f, zero_arrow()) == f
pub trait ArrowPlus: ArrowZero {
    fn plus<A: Clone + 'static, B: Clone + 'static>(
        f: Self::P<A, B>,
        g: Self::P<A, B>,
    ) -> Self::P<A, B>;
}
}

plus combines two arrows: if the first succeeds, use its result; otherwise fall back to the second. Together with zero_arrow, this forms a monoid over arrows.

Laws

Associativity

#![allow(unused)]
fn main() {
P::plus(P::plus(f, g), h) == P::plus(f, P::plus(g, h))
}

Left Identity

#![allow(unused)]
fn main() {
P::plus(P::zero_arrow(), f) == f
}

Right Identity

#![allow(unused)]
fn main() {
P::plus(f, P::zero_arrow()) == f
}

Concrete Implementations

FnA (Function Arrow)

Marker type whose P<A, B> is Box<dyn Fn(A) -> B> -- the canonical function arrow.

Definition

#![allow(unused)]
fn main() {
pub struct FnA;

impl HKT2 for FnA {
    type P<A, B> = Box<dyn Fn(A) -> B>;
}
}

FnA is a zero-sized marker type equivalent to FnP in karpal-profunctor but independent (no cross-crate dependency). It is the most natural arrow: a boxed function from A to B.

Implemented traits

FnA does not implement ArrowZero or ArrowPlus because a plain function A -> B has no notion of failure or empty result.

Feature gate

FnA requires the alloc feature because Box<dyn Fn> requires heap allocation.

Example

#![allow(unused)]
fn main() {
use karpal_arrow::{Arrow, ArrowChoice, Category, Semigroupoid, FnA};

// Lift pure functions into arrows
let double = FnA::arr(|x: i32| x * 2);
let add_one = FnA::arr(|x: i32| x + 1);

// Compose: (x * 2) then (+ 1)
let pipeline = FnA::compose(add_one, double);
assert_eq!(pipeline(5), 11); // (5 * 2) + 1

// fanout: feed the same input to two arrows
let double = FnA::arr(|x: i32| x * 2);
let negate = FnA::arr(|x: i32| -x);
let both = FnA::fanout(double, negate);
assert_eq!(both(5), (10, -5));

// split: apply two arrows in parallel on a tuple
let to_str = FnA::arr(|x: i32| x.to_string());
let double = FnA::arr(|x: i32| x * 2);
let par = FnA::split(to_str, double);
assert_eq!(par((42, 5)), ("42".to_string(), 10));

// ArrowChoice: route through Result branches
let double: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);
let routed = FnA::left::<i32, i32, &str>(double);
assert_eq!(routed(Ok(5)), Ok(10));
assert_eq!(routed(Err("nope")), Err("nope"));
}

KleisliF<M> (Kleisli Arrow)

Kleisli arrow for a Monad M: P<A, B> = Box<dyn Fn(A) -> M::Of<B>>.

Definition

#![allow(unused)]
fn main() {
pub struct KleisliF<M: HKT>(PhantomData<M>);

impl<M: HKT> HKT2 for KleisliF<M> {
    type P<A, B> = Box<dyn Fn(A) -> M::Of<B>>;
}
}

KleisliF<M> wraps effectful functions A -> M<B> as arrows. It implements the full Arrow hierarchy when M: Chain + Applicative + Functor, and additionally implements ArrowZero and ArrowPlus when M: Plus.

Implemented traits

Example

#![allow(unused)]
fn main() {
use karpal_arrow::{Arrow, ArrowZero, ArrowPlus, Semigroupoid, KleisliF};
use karpal_core::hkt::OptionF;

type KOpt = KleisliF<OptionF>;

// Kleisli arrows: functions returning Option
let safe_double: Box<dyn Fn(i32) -> Option<i32>> = Box::new(|x| Some(x * 2));
let safe_add_one: Box<dyn Fn(i32) -> Option<i32>> = Box::new(|x| Some(x + 1));

// Compose: chains through the monad (short-circuits on None)
let pipeline = KOpt::compose(safe_add_one, safe_double);
assert_eq!(pipeline(5), Some(11)); // Some(10) -> Some(11)

// Short-circuit on failure
let fail: Box<dyn Fn(i32) -> Option<i32>> = Box::new(|_| None);
let after_fail = KOpt::compose(safe_add_one, fail);
assert_eq!(after_fail(5), None);

// ArrowZero: an arrow that always returns None
let z = KOpt::zero_arrow::<i32, i32>();
assert_eq!(z(42), None);

// ArrowPlus: try the first arrow, fall back to the second
let attempt = KOpt::plus(fail, safe_double);
assert_eq!(attempt(5), Some(10)); // first fails, second succeeds
}

CokleisliF<W> (Cokleisli Arrow)

Cokleisli arrow for a Comonad W: P<A, B> = Box<dyn Fn(W::Of<A>) -> B>.

Definition

#![allow(unused)]
fn main() {
pub struct CokleisliF<W: HKT>(PhantomData<W>);

impl<W: HKT> HKT2 for CokleisliF<W> {
    type P<A, B> = Box<dyn Fn(W::Of<A>) -> B>;
}
}

CokleisliF<W> wraps context-consuming functions W<A> -> B as arrows. Composition requires W::Of<A>: Clone, which cannot be expressed generically with GATs. Instead, the impl_cokleisli! macro generates Semigroupoid and Category impls for specific comonads.

The impl_cokleisli! macro

#![allow(unused)]
fn main() {
/// Generate Semigroupoid + Category impls for `CokleisliF<$W>` where
/// `$W::Of<A>` is known to be `Clone` for `A: Clone`.
///
/// Usage: `impl_cokleisli!(IdentityF, OptionF, NonEmptyVecF, EnvF<E>);`
#[macro_export]
macro_rules! impl_cokleisli {
    ($W:ty) => { /* generates Semigroupoid + Category impls */ };
}
}

Pre-generated instances are provided for IdentityF, OptionF, and NonEmptyVecF. A separate impl_cokleisli_env! macro handles EnvF<E> with specific environment types (pre-generated for i32 and String).

Implemented traits

CokleisliF only implements Semigroupoid and Category. It does not implement the full Arrow hierarchy because lifting a pure function A -> B into W<A> -> B would require Comonad::extract in arr, but the product-routing operations (first, second) would need W<(A, C)> to be decomposable, which is not generally possible for all comonads.

Design Notes

Clone + 'static bounds

All type parameters in the arrow hierarchy require Clone + 'static bounds. The 'static bound is necessary because all concrete implementations use Box<dyn Fn>, which requires captured closures (and the types they close over) to be 'static. The Clone bound is needed for operations like fanout (which duplicates the input) and Kleisli composition (which needs to clone values threaded through monadic binds).

ArrowLoop and D: Default

In Haskell, ArrowLoop's loop relies on laziness to "tie the knot" -- the feedback value d is defined in terms of itself. Rust is strict, so this is not possible. Instead, Karpal's loop_arrow requires D: Default to provide an initial seed for the feedback channel. The implementation performs a single pass: it feeds (a, D::default()) into the arrow and returns the B component of the output, discarding the feedback.

CokleisliF and impl_cokleisli!

The challenge with CokleisliF<W> is that composition requires W::Of<A>: Clone, but this bound cannot be expressed generically with GATs -- you cannot write where W::Of<A>: Clone in a blanket impl because the compiler cannot verify this for all possible W. The impl_cokleisli! macro solves this by generating implementations for each specific comonad where the Clone bound is known to hold.

Operator naming

Haskell uses symbolic operators for several arrow combinators. Since Rust does not support custom operators, Karpal uses descriptive names:

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Free Constructions

Free constructions generate algebraic structure "for free" from a type constructor. They live in the karpal-free crate and build on the HKT encoding and typeclass hierarchy from karpal-core.

Overview

Types

Coyoneda<F, A, B>

The free functor -- makes any type constructor into a Functor by deferring fmap as function composition.

Definition

#![allow(unused)]
fn main() {
pub struct Coyoneda<F: HKT, A, B> {
    f: Box<dyn Fn(B) -> A>,   // accumulated transform
    fb: F::Of<B>,              // the original value
    _marker: PhantomData<F>,
}

pub struct CoyonedaF<F: HKT>(PhantomData<F>);
}

Coyoneda<F, A, B> stores an F<B> together with a function B → A. The type parameter B is the original "base" type from lift. Calling fmap composes onto the stored function (changing A but keeping B fixed). Only lower() applies the composed function via a single F::fmap.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT, A: 'static> Coyoneda<F, A, A> {
    /// Lift F<A> into Coyoneda. No Functor bound needed.
    pub fn lift(fa: F::Of<A>) -> Self;
}

impl<F: HKT, A: 'static, B: 'static> Coyoneda<F, A, B> {
    /// Map without Functor bound -- composes onto stored function.
    pub fn fmap<C: 'static>(self, g: impl Fn(A) -> C + 'static) -> Coyoneda<F, C, B>;

    /// Apply the stored function via F::fmap, producing F<A>.
    /// This is the only operation that requires F: Functor.
    pub fn lower(self) -> F::Of<A> where F: Functor;
}
}

Example

#![allow(unused)]
fn main() {
use karpal_free::{Coyoneda, CoyonedaF};
use karpal_core::hkt::OptionF;

// Chain multiple fmaps -- no Functor needed yet
let co = Coyoneda::<OptionF, _, _>::lift(Some(1))
    .fmap(|x| x + 1)
    .fmap(|x| x * 10)
    .fmap(|x| x + 5);

// Only lower() needs Functor -- applies all maps at once
let result = co.lower();
assert_eq!(result, Some(25)); // (1+1)*10+5
}

Yoneda<F, A>

The Yoneda lemma as a data type -- O(1) map composition via CPS.

Definition

#![allow(unused)]
fn main() {
pub struct Yoneda<F: HKT + Functor + 'static, A: 'static> {
    inner: Box<dyn YonedaLower<F, A>>,
}

pub struct YonedaF<F: HKT + Functor + 'static>(PhantomData<F>);
}

Yoneda<F, A> is similar to Coyoneda, but lift requires F: Functor. The benefit is map fusion: chaining N fmap calls composes the functions before applying them to F, so lower() makes only one pass through the structure.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT + Functor + 'static, A: Clone + 'static> Yoneda<F, A> {
    /// Lift F<A> into Yoneda. Requires F: Functor (unlike Coyoneda).
    pub fn lift(fa: F::Of<A>) -> Self;
}

impl<F: HKT + Functor + 'static, A: 'static> Yoneda<F, A> {
    /// Lower back to F<A> by applying accumulated transformations.
    pub fn lower(self) -> F::Of<A>;

    /// Map a function -- composed into the CPS, deferred until lower().
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> Yoneda<F, B>;
}
}

Coyoneda vs Yoneda

Example

#![allow(unused)]
fn main() {
use karpal_free::{Yoneda, YonedaF};
use karpal_core::hkt::OptionF;

// Yoneda fuses multiple fmaps into a single pass
let result = Yoneda::<OptionF, i32>::lift(Some(42))
    .fmap(|x| x * 2)
    .fmap(|x| format!("val={}", x))
    .lower();
assert_eq!(result, Some("val=84".to_string()));
}

Free<F, A>

The Free Monad -- build monadic computations as data structures, then interpret them.

Definition

#![allow(unused)]
fn main() {
/// Pure(a)             -- a finished computation returning a
/// Roll(F<Free<F, A>>) -- one layer of effect wrapping a continuation
pub enum Free<F: HKT, A> {
    Pure(A),
    Roll(Box<F::Of<Free<F, A>>>),
}

/// HKT marker -- implements HKT + Functor
pub struct FreeF<F: HKT>(PhantomData<F>);
}

Free<F, A> represents a program where F describes the available effects and A is the result type. Programs are built with pure and lift_f, composed with chain, and interpreted with fold_map using a natural transformation into any target monad.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT, A> Free<F, A> {
    /// Wrap a pure value.
    pub fn pure(a: A) -> Self;
}

impl<F: HKT + Functor, A> Free<F, A> {
    /// Lift a single effect F<A> into the free monad.
    pub fn lift_f(fa: F::Of<A>) -> Self;

    /// Map a function over the result.
    pub fn fmap<B>(self, f: impl Fn(A) -> B) -> Free<F, B>;

    /// Monadic bind -- sequence with a continuation.
    pub fn chain<B>(self, f: impl Fn(A) -> Free<F, B>) -> Free<F, B>;

    /// Interpret into target monad M via natural transformation NT: F ~> M.
    pub fn fold_map<M, NT>(self) -> M::Of<A>
    where
        M: Applicative + Chain,
        NT: NaturalTransformation<F, M>;
}
}

Trait Implementations

FreeF does not implement Apply, Chain, or Monad. See Design Notes for why.

Laws

Functor Identity

#![allow(unused)]
fn main() {
free.fmap(|a| a) == free
}

Functor Composition

#![allow(unused)]
fn main() {
free.fmap(|a| g(f(a))) == free.fmap(f).fmap(g)
}

Monad Left Identity

#![allow(unused)]
fn main() {
Free::pure(a).chain(f) == f(a)
}

Monad Right Identity

#![allow(unused)]
fn main() {
m.chain(Free::pure) == m
}

Example

#![allow(unused)]
fn main() {
use karpal_free::{Free, FreeF};
use karpal_core::hkt::OptionF;
use karpal_core::natural::NaturalTransformation;

// Define a natural transformation: Option ~> Option (identity)
struct OptionId;
impl NaturalTransformation<OptionF, OptionF> for OptionId {
    fn transform<A>(fa: Option<A>) -> Option<A> { fa }
}

// Build a computation: lift an effect, then chain
let program = Free::<OptionF, i32>::lift_f(Some(3))
    .chain(|x| Free::lift_f(Some(x * 10)));

// Interpret into Option via the natural transformation
let result = program.fold_map::<OptionF, OptionId>();
assert_eq!(result, Some(30));
}

Cofree<F, A>

The Cofree Comonad -- annotated trees/streams where F determines the branching structure.

Definition

#![allow(unused)]
fn main() {
/// Each node carries a value (head) and subtrees (tail).
/// The choice of F determines the shape:
///   OptionF  -> a non-empty list (finite stream)
///   VecF     -> a rose tree
///   IdentityF -> an infinite stream
pub struct Cofree<F: HKT, A> {
    pub head: A,
    pub tail: Box<F::Of<Cofree<F, A>>>,
}

/// HKT marker -- implements HKT + Functor + Extend + Comonad
pub struct CofreeF<F: HKT>(PhantomData<F>);
}

Cofree<F, A> is the dual of the Free Monad. Where Free builds up effects layer by layer, Cofree builds up context -- every node in the tree carries a value and can see its entire subtree.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT, A> Cofree<F, A> {
    /// Create a node with the given head and tail.
    pub fn new(head: A, tail: F::Of<Cofree<F, A>>) -> Self;

    /// Extract the head value.
    pub fn extract(&self) -> A where A: Clone;
}

impl<F: HKT + Functor, A> Cofree<F, A> {
    /// Map a function over all head values.
    pub fn fmap<B>(self, f: impl Fn(A) -> B) -> Cofree<F, B>;

    /// Apply a context-aware function to every position.
    /// f receives the entire sub-cofree rooted at each node.
    pub fn extend<B>(self, f: impl Fn(&Cofree<F, A>) -> B) -> Cofree<F, B>
    where A: Clone;

    /// Build a Cofree from a seed and an unfolding function.
    /// f(seed) returns (head, F<Seed>) -- the value and seeds for subtrees.
    pub fn unfold<Seed>(seed: Seed, f: impl Fn(&Seed) -> (A, F::Of<Seed>)) -> Self;
}
}

Trait Implementations

Laws

Comonad: extract after extend

extract(extend(w, f)) == f(w)

#![allow(unused)]
fn main() {
let extended = CofreeF::<OptionF>::extend(w, f);
CofreeF::<OptionF>::extract(&extended) == f(&w)
}

Comonad: extend with extract

extend(w, extract) == w

#![allow(unused)]
fn main() {
CofreeF::<OptionF>::extend(w, CofreeF::<OptionF>::extract).head == w.head
}

Example

#![allow(unused)]
fn main() {
use karpal_free::{Cofree, CofreeF};
use karpal_core::hkt::OptionF;

// Unfold a countdown stream: 3, 2, 1, 0
let stream = Cofree::<OptionF, i32>::unfold(3, |&seed| {
    if seed <= 0 { (seed, None) }
    else { (seed, Some(seed - 1)) }
});
assert_eq!(stream.head, 3);

// Extend: at each position, sum the current and next head
let sums = stream.extend(|w| {
    let next = w.tail.as_ref().as_ref().map(|c| c.head).unwrap_or(0);
    w.head + next
});
assert_eq!(sums.head, 3 + 2); // 5
}

Freer<F, A>

The Freer Monad -- like Free but requires no F: Functor until interpretation.

Definition

#![allow(unused)]
fn main() {
/// Pure(a)        -- a finished computation
/// Impure(step)   -- an effect step with erased continuation type
pub enum Freer<F: HKT + 'static, A: 'static> {
    Pure(A),
    Impure(Box<dyn FreerStep<F, A>>),
}

pub struct FreerF<F: HKT + 'static>(PhantomData<F>);
}

Freer<F, A> stores computations as a tree of effect steps, each containing ∃B. (F B, B → Freer F A). The intermediate type B is erased via a dyn-safe trait, deferring the Functor requirement to fold_map. Use Freer when F is not a Functor, or when you want to build computations without that constraint.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT + 'static, A: 'static> Freer<F, A> {
    /// Wrap a pure value. No F: Functor required.
    pub fn pure(a: A) -> Self;

    /// Lift a single effect F<A>. No F: Functor required.
    pub fn lift_f(fa: F::Of<A>) -> Self;

    /// Map a function over the result. No F: Functor required.
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> Freer<F, B>;

    /// Monadic bind. No F: Functor required.
    pub fn chain<B: 'static>(self, f: impl Fn(A) -> Freer<F, B> + 'static) -> Freer<F, B>;

    /// Interpret into target monad M via natural transformation NT: F ~> M.
    /// This is the only operation requiring F: Functor.
    pub fn fold_map<M, NT>(self) -> M::Of<A>
    where
        F: Functor,
        M: Applicative + Chain,
        NT: NaturalTransformation<F, M>;
}
}

Free vs Freer

Laws

Monad Left Identity

#![allow(unused)]
fn main() {
Freer::pure(a).chain(f) == f(a)
}

Monad Right Identity

#![allow(unused)]
fn main() {
m.chain(Freer::pure) == m
}

Example

#![allow(unused)]
fn main() {
use karpal_free::Freer;
use karpal_core::hkt::OptionF;
use karpal_core::natural::NaturalTransformation;

struct OptionId;
impl NaturalTransformation<OptionF, OptionF> for OptionId {
    fn transform<A>(fa: Option<A>) -> Option<A> { fa }
}

// Build without Functor constraint
let program = Freer::<OptionF, i32>::lift_f(Some(1))
    .chain(|x| Freer::lift_f(Some(x + 1)))
    .chain(|x| Freer::lift_f(Some(x * 10)));

// Functor only needed at interpretation time
let result = program.fold_map::<OptionF, OptionId>();
assert_eq!(result, Some(20)); // (1+1)*10
}

Lan<G, H, A, B>

Left Kan Extension -- ∃B. (G B → A, H B).

Definition

#![allow(unused)]
fn main() {
pub struct Lan<G: HKT, H: HKT, A, B> {
    extract_fn: Box<dyn Fn(G::Of<B>) -> A>,
    source: H::Of<B>,
    _marker: PhantomData<G>,
}

pub struct LanF<G: HKT, H: HKT, B>(PhantomData<(G, H, B)>);
}

Lan<G, H, A, B> encodes a value H B together with a way to extract A from G B. fmap composes onto the extract function with no bounds on G or H. When G = IdentityF, Lan is isomorphic to Coyoneda.

Key Methods

#![allow(unused)]
fn main() {
impl<G: HKT + 'static, H: HKT + 'static, A: 'static, B: 'static> Lan<G, H, A, B> {
    /// Construct from a source and extract function.
    pub fn new(source: H::Of<B>, f: impl Fn(G::Of<B>) -> A + 'static) -> Self;

    /// Map over the result type. No bounds on G or H required.
    pub fn fmap<C: 'static>(self, f: impl Fn(A) -> C + 'static) -> Lan<G, H, C, B>;

    /// Collapse using a natural transformation NT: H ~> G.
    pub fn lower<NT: NaturalTransformation<H, G>>(self) -> A;
}

/// When G = IdentityF: convert to Coyoneda.
impl<H: HKT + 'static, A: 'static, B: 'static> Lan<IdentityF, H, A, B> {
    pub fn to_coyoneda(self) -> Coyoneda<H, A, B>;
}
}

Example

#![allow(unused)]
fn main() {
use karpal_free::Lan;
use karpal_core::hkt::{IdentityF, OptionF};
use karpal_core::natural::NaturalTransformation;

// Lan<IdentityF, OptionF, String, i32>:
//   source: Option<i32>, extract: i32 -> String
let lan = Lan::<IdentityF, OptionF, String, i32>::new(
    Some(42),
    |x: i32| format!("val={x}"),
);

// Convert to Coyoneda (Lan with G=IdentityF is Coyoneda)
let coy = lan.to_coyoneda();
let result = coy.lower();
assert_eq!(result, Some("val=42".to_string()));
}

Ran (trait)

Right Kan Extension -- ∀R. (A → G R) → H R.

Definition

#![allow(unused)]
fn main() {
/// Ran is a trait because the universal quantifier (forall R)
/// requires a generic method, which cannot be made object-safe.
pub trait Ran<G: HKT, H: HKT> {
    /// The input type (A in forall R. (A -> G R) -> H R).
    type Input;

    /// Run: given a continuation k: A -> G R, produce H R.
    fn run_ran<R>(&self, k: impl Fn(Self::Input) -> G::Of<R>) -> H::Of<R>;
}

/// Map over a Ran's input, producing a new Ran.
pub fn ran_fmap<G, H, A, B, T, F>(ran: T, f: F) -> RanMapped<G, H, A, B, T, F>;
}

Ran is the dual of Lan. Where Lan uses an existential (hidden type), Ran uses a universal (works for all types). In Rust, this means Ran must be a trait rather than a concrete type, since trait objects cannot have generic methods. When G = H = F, Ran specialises to Codensity.

Example

#![allow(unused)]
fn main() {
use karpal_free::{Ran, ran_fmap};
use karpal_core::hkt::OptionF;

struct SimpleRan(i32);

impl Ran<OptionF, OptionF> for SimpleRan {
    type Input = i32;
    fn run_ran<R>(&self, k: impl Fn(i32) -> Option<R>) -> Option<R> {
        k(self.0)
    }
}

// Basic usage
let result = SimpleRan(42).run_ran(|x| Some(x * 2));
assert_eq!(result, Some(84));

// ran_fmap transforms the input
let mapped = ran_fmap(SimpleRan(10), |x| x + 5);
let result = mapped.run_ran(|x| Some(x * 2));
assert_eq!(result, Some(30)); // (10+5)*2
}

Codensity<F, A>

The Codensity Monad -- CPS transform of a type constructor. pure, fmap, chain need no bounds on F.

Definition

#![allow(unused)]
fn main() {
/// Codensity<F, A> = forall R. (A -> F R) -> F R
/// Implemented as a dyn-safe computation tree (Pure/Map/Bind layers).
pub struct Codensity<F: HKT + 'static, A: 'static> {
    inner: Box<dyn CodensityInner<F, A>>,
}

pub struct CodensityF<F: HKT + 'static>(PhantomData<F>);
}

Codensity<F, A> is the right Kan extension of F along itself (Ran F F A), specialised into a concrete type. The key property: pure, fmap, and chain require no bounds on F. Only to_monad needs F: Applicative + Chain. Wrapping a free monad in Codensity can improve asymptotic performance of left-associated binds.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT + 'static, A: 'static> Codensity<F, A> {
    /// Wrap a pure value. No bounds on F.
    pub fn pure(a: A) -> Self;

    /// Map a function. No bounds on F.
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> Codensity<F, B>;

    /// Monadic bind. No bounds on F.
    pub fn chain<B: 'static>(self, f: impl Fn(A) -> Codensity<F, B> + 'static)
        -> Codensity<F, B>;

    /// Collapse to F<A>. Requires F: Applicative + Chain.
    pub fn to_monad(self) -> F::Of<A>
    where F: Applicative + Chain;
}
}

Laws

Monad Left Identity

#![allow(unused)]
fn main() {
Codensity::pure(a).chain(f).to_monad() == f(a).to_monad()
}

Monad Right Identity

#![allow(unused)]
fn main() {
m.chain(Codensity::pure).to_monad() == m.to_monad()
}

Monad Associativity

#![allow(unused)]
fn main() {
(m.chain(f)).chain(g).to_monad()
  == m.chain(|x| f(x).chain(g)).to_monad()
}

Example

#![allow(unused)]
fn main() {
use karpal_free::Codensity;
use karpal_core::hkt::OptionF;

// Build computation -- no bounds on OptionF needed here
let computation = Codensity::<OptionF, i32>::pure(1)
    .chain(|x| Codensity::pure(x + 1))
    .chain(|x| Codensity::pure(x * 10))
    .chain(|x| Codensity::pure(x + 5));

// Only to_monad needs F: Applicative + Chain
let result = computation.to_monad();
assert_eq!(result, Some(25)); // (1+1)*10+5
}

Density<W, A>

The Density Comonad -- CPS dual of Codensity. extract and fmap need no bounds on W.

Definition

#![allow(unused)]
fn main() {
/// Density<W, A> = exists S. (W S -> A, W S)
/// The left Kan extension of W along itself (Lan W W A).
pub struct Density<W: HKT + 'static, A: 'static> {
    inner: Box<dyn DensityDyn<W, A>>,
}

pub struct DensityF<W: HKT + 'static>(PhantomData<W>);
}

Density<W, A> stores a value W S together with a function &W::Of<S> → A. The state type S is existentially hidden via a dyn-safe trait. Both extract and fmap require no bounds on W.

Key Methods

#![allow(unused)]
fn main() {
impl<W: HKT + 'static, A: 'static> Density<W, A> {
    /// Construct from a source and extract function.
    pub fn lift<S: 'static>(
        source: W::Of<S>,
        f: impl Fn(&W::Of<S>) -> A + 'static,
    ) -> Self;

    /// Extract the value. No bounds on W.
    pub fn extract(&self) -> A;

    /// Map a function. No bounds on W.
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> Density<W, B>;
}
}

Laws

Functor Identity

#![allow(unused)]
fn main() {
d.fmap(|a| a).extract() == d.extract()
}

Functor Composition

#![allow(unused)]
fn main() {
d.fmap(|a| g(f(a))).extract() == d.fmap(f).fmap(g).extract()
}

Example

#![allow(unused)]
fn main() {
use karpal_free::Density;
use karpal_core::hkt::OptionF;

// Lift a value with an extract function
let d = Density::<OptionF, i32>::lift(
    Some(42),
    |opt| opt.unwrap(),
);
assert_eq!(d.extract(), 42);

// fmap composes onto extract -- no bounds on OptionF
let mapped = d.fmap(|x| format!("val={x}"));
assert_eq!(mapped.extract(), "val=42");
}

Day<F, G, A, B, C>

Day Convolution -- pairs two functors with a combining function.

Definition

#![allow(unused)]
fn main() {
/// Day f g a ≅ ∃b c. (f b, g c, b → c → a)
/// B and C are exposed as type parameters (Rust lacks existential types).
pub struct Day<F: HKT, G: HKT, A, B, C> {
    f_val: F::Of<B>,
    g_val: G::Of<C>,
    combine: Box<dyn Fn(B, C) -> A>,
    _marker: PhantomData<(F, G)>,
}

pub struct DayF<F: HKT + 'static, G: HKT + 'static>(PhantomData<(F, G)>);
}

Day<F, G, A, B, C> stores an F<B> value, a G<C> value, and a function (B, C) → A. fmap composes onto the combining function with no bounds on F or G. run_day interprets both sides into a target Applicative using two natural transformations.

Key Methods

#![allow(unused)]
fn main() {
impl<F, G, A, B: Clone, C: Clone> Day<F, G, A, B, C> {
    /// Construct from two functor values and a combining function.
    pub fn new(f_val: F::Of<B>, g_val: G::Of<C>,
               combine: impl Fn(B, C) -> A + 'static) -> Self;

    /// Map over the result. No bounds on F or G required.
    pub fn fmap<D: 'static>(self, f: impl Fn(A) -> D + 'static) -> Day<F, G, D, B, C>;

    /// Interpret into target Applicative M using two natural transformations.
    pub fn run_day<M, NF, NG>(self) -> M::Of<A>
    where
        M: Applicative,
        NF: NaturalTransformation<F, M>,
        NG: NaturalTransformation<G, M>;
}
}

Laws

Functor Identity

#![allow(unused)]
fn main() {
day.fmap(|a| a).run_day() == day.run_day()
}

Functor Composition

#![allow(unused)]
fn main() {
day.fmap(|a| g(f(a))).run_day() == day.fmap(f).fmap(g).run_day()
}

Example

#![allow(unused)]
fn main() {
use karpal_free::Day;
use karpal_core::hkt::OptionF;
use karpal_core::natural::NaturalTransformation;

struct OptionId;
impl NaturalTransformation<OptionF, OptionF> for OptionId {
    fn transform<A>(fa: Option<A>) -> Option<A> { fa }
}

// Pair two Option values with multiplication
let day = Day::<OptionF, OptionF, i32, i32, i32>::new(
    Some(3), Some(4), |a, b| a * b,
);
let result = day.run_day::<OptionF, OptionId, OptionId>();
assert_eq!(result, Some(12));

// fmap composes onto the combining function
let day = Day::<OptionF, OptionF, i32, i32, i32>::new(
    Some(2), Some(5), |a, b| a + b,
).fmap(|x| x * 3);
let result = day.run_day::<OptionF, OptionId, OptionId>();
assert_eq!(result, Some(21)); // (2+5)*3
}

FreeAp<F, A>

The Free Applicative -- build applicative computations as data for static analysis before interpretation.

Definition

#![allow(unused)]
fn main() {
/// Pure(a)   -- a finished computation
/// Ap(node)  -- an effect step (existentially quantified)
pub enum FreeAp<F: HKT + 'static, A: 'static> {
    Pure(A),
    Ap(Box<dyn FreeApNode<F, A>>),
}

pub struct FreeApF<F: HKT + 'static>(PhantomData<F>);
}

FreeAp<F, A> stores a computation tree where effects from F can be statically analyzed before interpretation. Unlike Free<F, A> (the free monad), effects in FreeAp do not depend on the results of previous effects -- they form a tree, not a chain.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT + 'static, A: 'static> FreeAp<F, A> {
    /// Wrap a pure value.
    pub fn pure(a: A) -> Self;

    /// Lift a single effect F<A>. Requires A: Clone (for Apply::ap).
    pub fn lift_f(fa: F::Of<A>) -> Self where A: Clone;

    /// Map a function over the result. No bounds on F required.
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> FreeAp<F, B>;

    /// Applicative ap: apply wrapped functions to values.
    pub fn ap<B: 'static>(
        ff: FreeAp<F, Box<dyn Fn(A) -> B>>, fa: FreeAp<F, A>,
    ) -> FreeAp<F, B> where A: Clone;

    /// Collapse into F's own Applicative. Requires F: Applicative.
    pub fn retract(self) -> F::Of<A> where F: Applicative;

    /// Count the number of lift_f effects in this tree.
    pub fn count_effects(&self) -> usize;
}
}

FreeAp vs Free

Laws

Functor Identity

#![allow(unused)]
fn main() {
fa.fmap(|a| a).retract() == fa.retract()
}

Applicative Identity

#![allow(unused)]
fn main() {
FreeAp::ap(FreeAp::pure(Box::new(|x| x)), fa).retract() == fa.retract()
}

Applicative Homomorphism

#![allow(unused)]
fn main() {
FreeAp::ap(FreeAp::pure(f), FreeAp::pure(x)).retract()
  == FreeAp::pure(f(x)).retract()
}

Example

#![allow(unused)]
fn main() {
use karpal_free::FreeAp;
use karpal_core::hkt::OptionF;

// Build a computation tree
let fa = FreeAp::<OptionF, i32>::lift_f(Some(10));
let fb = fa.fmap(|x| x + 5);

// Static analysis: count effects before running
assert_eq!(fb.count_effects(), 1);

// Interpret by collapsing into Option's Applicative
let result = fb.retract();
assert_eq!(result, Some(15));

// Apply wrapped functions
let ff = FreeAp::<OptionF, Box<dyn Fn(i32) -> i32>>::pure(
    Box::new(|x| x * 2) as Box<dyn Fn(i32) -> i32>
);
let fa = FreeAp::<OptionF, i32>::lift_f(Some(21));
let result = FreeAp::ap(ff, fa).retract();
assert_eq!(result, Some(42));
}

FreeAlt<F, A>

The Free Alternative -- choice among zero or more applicative computations.

Definition

#![allow(unused)]
fn main() {
/// FreeAlt f a ≅ [FreeAp f a]
/// An empty list is zero (failure), multiple elements represent choice.
pub struct FreeAlt<F: HKT + 'static, A: 'static> {
    alternatives: Vec<FreeAp<F, A>>,
}

pub struct FreeAltF<F: HKT + 'static>(PhantomData<F>);
}

FreeAlt<F, A> wraps a list of FreeAp<F, A> branches. An empty list represents zero (failure/no alternatives). alt combines two alternatives by concatenating their branches. retract collapses into F's own Alternative by folding branches with F::alt.

Key Methods

#![allow(unused)]
fn main() {
impl<F: HKT + 'static, A: 'static> FreeAlt<F, A> {
    /// Wrap a pure value (single branch).
    pub fn pure(a: A) -> Self;

    /// Lift a single effect (single branch).
    pub fn lift_f(fa: F::Of<A>) -> Self where A: Clone;

    /// The empty alternative (zero / failure).
    pub fn zero() -> Self;

    /// Combine two alternatives (choice).
    pub fn alt(self, other: FreeAlt<F, A>) -> Self;

    /// Map a function over all branches.
    pub fn fmap<B: 'static>(self, f: impl Fn(A) -> B + 'static) -> FreeAlt<F, B>;

    /// Collapse into F's own Alternative.
    pub fn retract(self) -> F::Of<A> where F: Alternative;

    /// Count branches.
    pub fn count_alternatives(&self) -> usize;

    /// Count total effects across all branches.
    pub fn count_effects(&self) -> usize;
}
}

Laws

Alt Associativity

#![allow(unused)]
fn main() {
(a.alt(b)).alt(c).retract() == a.alt(b.alt(c)).retract()
}

Plus Left Identity

#![allow(unused)]
fn main() {
FreeAlt::zero().alt(x).retract() == x.retract()
}

Plus Right Identity

#![allow(unused)]
fn main() {
x.alt(FreeAlt::zero()).retract() == x.retract()
}

Example

#![allow(unused)]
fn main() {
use karpal_free::FreeAlt;
use karpal_core::hkt::OptionF;

// Build alternatives
let a = FreeAlt::<OptionF, i32>::lift_f(None);
let b = FreeAlt::<OptionF, i32>::lift_f(Some(42));
let combined = a.alt(b);

// Inspect before interpreting
assert_eq!(combined.count_alternatives(), 2);
assert_eq!(combined.count_effects(), 2);

// retract: collapses using Option's alt (picks first Some)
let result = combined.retract();
assert_eq!(result, Some(42));

// zero is the identity for alt
let z = FreeAlt::<OptionF, i32>::zero();
assert_eq!(z.retract(), None);
}

Design Notes

Three families of free constructions

Exposed type parameters (Coyoneda, Lan, Day): These types keep type parameters visible (e.g. B in Coyoneda<F, A, B>, or B, C in Day<F, G, A, B, C>) representing the original values inside the functors. This is the simplest encoding and avoids trait objects for the core structure, though fmap closures still require Box<dyn Fn>.

Trait objects with dyn-safe traits (Yoneda, Codensity, Density, Freer, FreeAp): These types erase an internal type parameter via Box<dyn Trait>. This requires F: 'static and A: 'static bounds everywhere. Due to a Rust GAT limitation (you cannot add T: 'static to type Of<T> in a trait impl when the trait definition doesn't have it), marker types like CodensityF, FreerF, FreeApF, and FreeAltF cannot implement the HKT or Functor traits. Use the inherent methods instead.

Recursive enums/structs (Free, Cofree): These use direct recursion (not trait objects), so they avoid the 'static limitation entirely. FreeF implements HKT + Functor; CofreeF implements the full HKT + Functor + Extend + Comonad chain.

Composite wrappers (FreeAlt): Built on top of other free constructions. FreeAlt<F, A> is simply Vec<FreeAp<F, A>>, providing Alternative structure by combining applicative branches.

Kan extension relationships

Several of these types are specialisations of Kan extensions:

Why Free doesn't implement the Monad trait

FreeF implements Functor but not Apply, Chain, or Monad. The problem is Apply::ap: in the Roll case, each child of the function tree needs its own copy of the argument tree. The trait only provides A: Clone, not Free<F, A>: Clone. Adding bounds to an impl that the trait doesn't have is not allowed in Rust. The inherent chain method avoids this issue since it doesn't need to clone its argument.

Why Cofree doesn't implement Clone

A generic Clone impl for Cofree<F, A> would require F::Of<Cofree<F, A>>: Clone, which triggers infinite recursion in the compiler's trait resolution (coinductive reasoning, which Rust doesn't support). For the same reason, Cofree doesn't provide a duplicate method (which would need Clone internally). Use extend directly instead.

The &dyn Fn recursion pattern

Recursive methods like fmap and extend on Free/Cofree pass their closure to child nodes. Naively passing &f causes each recursive level to add a reference layer (&Fn, &&Fn, &&&Fn, ...), hitting the monomorphization recursion limit. The solution: public methods accept impl Fn, then immediately delegate to a private _inner method that takes &dyn Fn. Since the type is erased behind dyn, the recursive calls all use the same concrete type.

#![allow(unused)]
fn main() {
// Public API: accepts impl Fn
pub fn fmap<B>(self, f: impl Fn(A) -> B) -> Cofree<F, B> {
    self.fmap_inner(&f)  // erase to &dyn Fn
}

// Private: fixed type at every recursion level
fn fmap_inner<B>(self, f: &dyn Fn(A) -> B) -> Cofree<F, B> {
    Cofree {
        head: f(self.head),
        tail: Box::new(F::fmap(*self.tail, |child| child.fmap_inner(f))),
    }
}
}

Why FreeAp uses retract instead of fold_map

In Haskell, the primary eliminator for free applicatives is foldMap :: (forall x. f x -> g x) -> Ap f a -> g a, which interprets into any target Applicative via a natural transformation. In Rust, this is impossible through dyn dispatch.

The issue: FreeAp::Ap erases an intermediate type B behind a trait object (Box<dyn FreeApNode<F, A>>). Calling NT::transform<B>(effect) requires compile-time monomorphisation for the specific B, but B has been erased. Rust cannot dispatch a generic function through a type-erased interface.

retract avoids this because it collapses into F itself -- F is already a type parameter of the trait. To interpret into a different Applicative M, apply your natural transformation at each lift_f call site, then retract:

#![allow(unused)]
fn main() {
// fold_map nt ≡ retract . hoist nt
// In practice: apply NT when building, then retract
let free_m: FreeAp<M, A> = FreeAp::lift_f(NT::transform(effect));
let result: M::Of<A> = free_m.retract();
}

Why Ran is a trait, not a struct

Ran encodes a universally quantified function: ∀R. (A → G R) → H R. In Rust, this requires a generic method run_ran<R>, which cannot be made object-safe. Unlike Codensity (which restricts to a single eliminator to_monad), Ran preserves the full generality of ∀R, so it must remain a trait. Use ran_fmap for functor-like mapping over Ran implementations.

See Also

• Functor Family -- the traits that Free/Cofree/FreeAp build on (Functor, Apply, Applicative, Chain, Monad)
• Alt Family -- Alt, Plus, and Alternative, which FreeAlt's retract requires
• Comonad Family -- Extend and Comonad, which Cofree implements
• Bifunctor & Natural -- NaturalTransformation, used by Free::fold_map, Freer::fold_map, Lan::lower, and Day::run_day

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Recursion Schemes

Recursion schemes provide structured, composable patterns for folding and unfolding recursive data. They live in the karpal-recursion crate and depend on karpal-core (HKT, Functor) and karpal-free (Cofree, Free).

Overview

Fixed Points

Fix<F>

The fixed point of a functor. Ties the recursive knot so that Fix<F> ≅ F<Fix<F>>.

Definition

#![allow(unused)]
fn main() {
pub struct Fix<F: HKT>(Rc<F::Of<Fix<F>>>);

// Unconditional Clone via Rc reference counting
impl<F: HKT> Clone for Fix<F> { ... }

pub type Mu<F> = Fix<F>;
}

Key Methods

#![allow(unused)]
fn main() {
// Wrap one layer
Fix::new(f: F::Of<Fix<F>>) -> Fix<F>

// Unwrap one layer (consuming)
fix.unfix() -> F::Of<Fix<F>>  // where F::Of<Fix<F>>: Clone

// Borrow one layer
fix.unfix_ref() -> &F::Of<Fix<F>>
}

Design: Rc vs Box

Fix uses Rc instead of Box for indirection. This makes Fix<F>: Clone unconditional (just a reference count bump), which is essential for paramorphism — it needs to both preserve and consume each subterm. Rust's trait solver cannot prove coinductive Clone bounds like Fix<OptionF>: Clone ↔ Option<Fix<OptionF>>: Clone, so Box would make Clone impossible.

Example: Natural Numbers

#![allow(unused)]
fn main() {
use karpal_recursion::{Fix, cata, ana};
use karpal_core::hkt::OptionF;

// None = Zero, Some(n) = Succ(n)
let three: Fix<OptionF> = Fix::new(Some(Fix::new(Some(Fix::new(None)))));

// Or build with ana:
let five: Fix<OptionF> = ana(
    |n: u32| if n == 0 { None } else { Some(n - 1) },
    5,
);

// Fold with cata:
let count = cata::<OptionF, u32>(
    |layer| match layer {
        None => 0,
        Some(n) => n + 1,
    },
    five,
);
assert_eq!(count, 5);
}

Nu<F, Seed>

Greatest fixed point — a seed paired with a coalgebra for lazy observation.

Definition

#![allow(unused)]
fn main() {
pub struct Nu<F: HKT, Seed> {
    pub seed: Seed,
    pub coalgebra: Box<dyn Fn(&Seed) -> F::Of<Seed>>,
}
}

Key Methods

#![allow(unused)]
fn main() {
Nu::new(seed, coalgebra) -> Nu<F, Seed>
nu.observe() -> F::Of<Seed>   // apply coalgebra once
nu.to_fix() -> Fix<F>         // fully unfold via ana
}

Example

#![allow(unused)]
fn main() {
use karpal_recursion::Nu;
use karpal_core::hkt::OptionF;

let countdown = Nu::<OptionF, u32>::new(3, |&s| {
    if s == 0 { None } else { Some(s - 1) }
});
assert_eq!(countdown.observe(), Some(2));
}

Recursion Schemes

cata — Catamorphism

Fold a recursive structure bottom-up. The fundamental "tear down" operation.

Signature

#![allow(unused)]
fn main() {
pub fn cata<F: HKT + Functor, A>(
    alg: impl Fn(F::Of<A>) -> A,
    fix: Fix<F>,
) -> A
}

Example: Sum Natural Numbers

#![allow(unused)]
fn main() {
let n = ana(|s: u32| if s == 0 { None } else { Some(s - 1) }, 5);
let sum = cata::<OptionF, u32>(
    |layer| match layer {
        None => 0,
        Some(acc) => acc + 1,
    },
    n,
);
assert_eq!(sum, 5);
}

Laws

• cata(Fix::new, x) == x — folding with the constructor is identity

ana — Anamorphism

Unfold a recursive structure top-down from a seed.

Signature

#![allow(unused)]
fn main() {
pub fn ana<F: HKT + Functor, A>(
    coalg: impl Fn(A) -> F::Of<A>,
    seed: A,
) -> Fix<F>
}

Example: Build Natural Numbers

#![allow(unused)]
fn main() {
let three: Fix<OptionF> = ana(
    |n: u32| if n == 0 { None } else { Some(n - 1) },
    3,
);
}

Laws

• cata(alg, ana(coalg, seed)) == hylo(alg, coalg, seed)

hylo — Hylomorphism

Unfold then fold in a single pass — no intermediate Fix is allocated.

Signature

#![allow(unused)]
fn main() {
pub fn hylo<F: HKT + Functor, A, B>(
    alg: impl Fn(F::Of<B>) -> B,
    coalg: impl Fn(A) -> F::Of<A>,
    seed: A,
) -> B
}

Key Property

hylo(alg, coalg, seed) == cata(alg, ana(coalg, seed)) but more efficient — the intermediate data structure is "deforested" away.

para — Paramorphism

Fold with access to original subterms. The algebra receives both the folded result and the original sub-structure.

Signature

#![allow(unused)]
fn main() {
pub fn para<F: HKT + Functor, A>(
    alg: impl Fn(F::Of<(Fix<F>, A)>) -> A,
    fix: Fix<F>,
) -> A
}

Example: Factorial

#![allow(unused)]
fn main() {
let factorial = para::<OptionF, u64>(
    |layer| match layer {
        None => 1,           // 0! = 1
        Some((sub, acc)) => {
            let n = count(&sub) + 1;  // read current number from subterm
            (n as u64) * acc
        }
    },
    nat(5),
);
assert_eq!(factorial, 120);
}

Laws

• When ignoring the Fix<F> subterm, para degenerates to cata

apo — Apomorphism

Unfold with early termination. The coalgebra can short-circuit by injecting a pre-built Fix.

Signature

#![allow(unused)]
fn main() {
pub fn apo<F: HKT + Functor, A>(
    coalg: impl Fn(A) -> F::Of<Either<Fix<F>, A>>,
    seed: A,
) -> Fix<F>
}

Key Idea

Either::Right(seed) continues unfolding, Either::Left(fix) embeds an already-built subtree directly. When always returning Right, apo degenerates to ana.

histo — Histomorphism

Fold with full history via Cofree. At each step, access all previously-computed results.

Signature

#![allow(unused)]
fn main() {
pub fn histo<F: HKT + Functor, A>(
    alg: impl Fn(&F::Of<Cofree<F, A>>) -> A,
    fix: Fix<F>,
) -> A
}

Example: Fibonacci

#![allow(unused)]
fn main() {
let fib = histo::<OptionF, u64>(
    |layer| match layer {
        None => 0,                      // fib(0) = 0
        Some(cofree) => {
            let prev = cofree.head;      // fib(n-1)
            match cofree.tail.as_ref() {
                None => 1,               // fib(1) = 1
                Some(gc) => prev + gc.head,  // fib(n-1) + fib(n-2)
            }
        }
    },
    nat(10),
);
assert_eq!(fib, 55);
}

Design Note

The algebra takes &F::Of<Cofree<F, A>> (a reference) rather than ownership. This avoids needing Clone on the recursive Cofree structure, which Rust's trait solver cannot prove coinductively.

futu — Futumorphism

Multi-step unfold via Free. Generate multiple layers of structure at once.

Signature

#![allow(unused)]
fn main() {
pub fn futu<F: HKT + Functor, A>(
    coalg: impl Fn(A) -> F::Of<Free<F, A>>,
    seed: A,
) -> Fix<F>
}

Key Idea

Free::Pure(seed) continues with one more coalgebra application. Free::Roll(f) injects multiple layers at once. When always returning Pure, futu degenerates to ana.

zygo — Zygomorphism

Fold with an auxiliary fold running in parallel.

Signature

#![allow(unused)]
fn main() {
pub fn zygo<F: HKT + Functor, A, B>(
    aux: impl Fn(F::Of<B>) -> B,
    alg: impl Fn(F::Of<(B, A)>) -> A,
    fix: Fix<F>,
) -> A
where F::Of<(B, A)>: Clone
}

Key Idea

Two algebras run simultaneously: aux computes a helper value B at each layer, and alg has access to both B and the primary result A from sub-structures.

chrono — Chronomorphism

Combines futumorphism and histomorphism in a single pass.

Signature

#![allow(unused)]
fn main() {
pub fn chrono<F: HKT + Functor, A, B>(
    alg: impl Fn(&F::Of<Cofree<F, B>>) -> B,
    coalg: impl Fn(A) -> F::Of<Free<F, A>>,
    seed: A,
) -> B
}

Key Idea

Conceptually chrono = histo . futu — multi-step unfolding with history-aware folding — but computed in a single pass without building an intermediate Fix.

Either<L, R>

Either<L, R>

A simple sum type used by apomorphism for early termination.

Definition

#![allow(unused)]
fn main() {
pub enum Either<L, R> {
    Left(L),
    Right(R),
}

// Methods: either, map_left, map_right
}

Scheme Relationships

The schemes form a lattice of generality:

        cata ────────── hylo ────────── ana
         │                                │
    para (+ subterms)              apo (+ early stop)
         │                                │
   histo (+ full history)         futu (+ multi-step)
         │                                │
         └──────── chrono ────────────────┘
                     │
                zygo (+ aux fold)

Each scheme on the left is the dual of the corresponding scheme on the right. Moving down adds more power (and constraints). hylo sits in the middle as the deforested composition of any fold and unfold.

Implementation Patterns

• &dyn Fn recursion — all inner helper functions use &dyn Fn for the algebra/coalgebra to break monomorphization recursion (same pattern as Free::fmap_inner)
• Rc in Fix — enables Clone without coinductive proofs; essential for para
• Reference algebras — histo and chrono take &F::Of<Cofree<F, A>> to avoid cloning Cofree
• F::Of<Fix<F>>: Clone — required by schemes that call unfix() (cata, para, histo, zygo) for the Rc::try_unwrap fallback path

Optics

Profunctor optics: first-class field accessors and pattern matchers.

Optics let you focus on parts of a data structure -- reading, writing, and transforming nested fields or enum variants -- without breaking encapsulation. Karpal provides a full hierarchy of optic types, each constrained by a different profunctor class:

Optics form a subtyping hierarchy -- every Iso can be used as a Lens or Prism, every Lens can be used as a Getter, Setter, Traversal, or Fold, and so on. Karpal provides explicit to_* conversion methods for these relationships.

All optic types live in the karpal-optics crate and implement the Optic marker trait.

Optic

Marker trait for the optic family.

Signature

#![allow(unused)]
fn main() {
/// Marker trait for all optics.
///
/// This trait exists to unify the optic family under a single taxonomy.
/// Concrete optic types (Lens, Prism, etc.) implement this trait.
pub trait Optic {}
}

Optic carries no methods. It exists solely to classify types as optics, which is useful for trait bounds and documentation. All concrete optic types implement Optic: Iso, Lens, ComposedLens, Prism, Getter, ComposedGetter, Review, Setter, Traversal, ComposedTraversal, Fold, and ComposedFold.

Iso

An isomorphism: a lossless, reversible conversion between two representations.

Struct definition

#![allow(unused)]
fn main() {
pub struct Iso<S, T, A, B> {
    forward: fn(&S) -> A,
    backward: fn(B) -> T,
}

pub type SimpleIso<S, A> = Iso<S, S, A, A>;
}

An Iso witnesses that S and A carry the same information. It is the strongest optic -- it requires only Profunctor (no Strong or Choice), and can be converted to any other optic type.

Methods

#![allow(unused)]
fn main() {
impl<S, T, A, B> Iso<S, T, A, B> {
    pub fn new(forward: fn(&S) -> A, backward: fn(B) -> T) -> Self;
    pub fn get(&self, s: &S) -> A;
    pub fn review(&self, b: B) -> T;
    pub fn set(&self, _s: S, b: B) -> T;

    /// Profunctor encoding -- only requires Profunctor (weakest constraint).
    pub fn transform<P: Profunctor>(&self, pab: P::P<A, B>) -> P::P<S, T>;

    // Conversions
    pub fn to_getter(&self) -> Getter<S, A>;
    pub fn to_review(&self) -> Review<T, B>;
    pub fn to_fold(&self) -> Fold<S, A>;
}

impl<S: Clone, T, A, B> Iso<S, T, A, B> {
    pub fn over(&self, s: S, f: impl FnOnce(A) -> B) -> T;
    pub fn to_lens(&self) -> ComposedLens<S, T, A, B>;   // boxed (captures backward)
    pub fn to_setter(&self) -> Setter<S, T, A, B>;
    pub fn to_traversal(&self) -> Traversal<S, T, A, B>;
}
}

Laws

Roundtrip (forward-backward)

#![allow(unused)]
fn main() {
iso.review(iso.get(&s)) == s
}

Roundtrip (backward-forward)

#![allow(unused)]
fn main() {
iso.get(&iso.review(b)) == b
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Iso, SimpleIso};

// Celsius <-> Fahrenheit
let temp: SimpleIso<f64, f64> = Iso::new(
    |c: &f64| c * 9.0 / 5.0 + 32.0,  // forward: C -> F
    |f: f64| (f - 32.0) * 5.0 / 9.0,   // backward: F -> C
);

assert!((temp.get(&100.0) - 212.0).abs() < 1e-10);
assert!((temp.review(32.0) - 0.0).abs() < 1e-10);

// Modify in the "other" representation
let result = temp.over(0.0, |f| f + 18.0); // add 18F to 0C
assert!((result - 10.0).abs() < 1e-10);    // = 10C
}

Lens

A first-class getter/setter pair for focusing on a field inside a product type.

Struct definition

#![allow(unused)]
fn main() {
/// A van Laarhoven-style lens encoded with getter/setter function pointers.
///
/// `S` -- source type, `T` -- modified source type,
/// `A` -- focus type, `B` -- replacement type.
pub struct Lens<S, T, A, B> {
    getter: fn(&S) -> A,
    setter: fn(S, B) -> T,
}

/// A simple (monomorphic) lens where `S == T` and `A == B`.
pub type SimpleLens<S, A> = Lens<S, S, A, A>;
}

The four type parameters support polymorphic update: you can replace a field of type A with a value of type B, changing the source from S to T. In practice, most lenses are simple (monomorphic), where S == T and A == B. The SimpleLens type alias covers this common case.

Methods

#![allow(unused)]
fn main() {
impl<S, T, A, B> Lens<S, T, A, B> {
    /// Create a new lens from a getter and setter.
    pub fn new(getter: fn(&S) -> A, setter: fn(S, B) -> T) -> Self;

    /// Extract the focus from the source.
    pub fn get(&self, s: &S) -> A;

    /// Replace the focus, producing a new source.
    pub fn set(&self, s: S, b: B) -> T;

    /// Chain another lens to focus deeper, producing a ComposedLens.
    /// Requires all type parameters to be `'static`.
    pub fn then<X, Y>(self, inner: Lens<A, B, X, Y>) -> ComposedLens<S, T, X, Y>
    where
        S: 'static, T: 'static, A: 'static, B: 'static,
        X: 'static, Y: 'static;
}

impl<S: Clone, T, A, B> Lens<S, T, A, B> {
    /// Modify the focus by applying a function. Requires `S: Clone`.
    pub fn over(&self, s: S, f: impl FnOnce(A) -> B) -> T;

    /// Profunctor encoding: transform a `P<A, B>` into a `P<S, T>`.
    /// Requires `S: Clone` and `Strong` profunctor `P`.
    /// All type parameters must be `'static`.
    pub fn transform<P: Strong>(&self, pab: P::P<A, B>) -> P::P<S, T>
    where
        S: 'static, T: 'static, A: 'static, B: 'static;

    // Conversions (all type params must be 'static)
    pub fn to_getter(&self) -> Getter<S, A>;
    pub fn to_setter(&self) -> Setter<S, T, A, B>;
    pub fn to_traversal(&self) -> Traversal<S, T, A, B>;
    pub fn to_fold(&self) -> Fold<S, A>;
}
}

How transform works (Strong)

The transform method connects a concrete lens to the profunctor hierarchy through the Strong trait. Given any Strong profunctor P and a value pab: P<A, B>, it produces P<S, T> by:

1. P::first(pab) lifts to P<(A, S), (B, S)>
2. P::dimap pre-composes with |s| (get(s), s) and post-composes with |(b, s)| set(s, b)

#![allow(unused)]
fn main() {
pub fn transform<P: Strong>(&self, pab: P::P<A, B>) -> P::P<S, T>
where
    S: 'static, T: 'static, A: 'static, B: 'static,
{
    let getter = self.getter;
    let setter = self.setter;
    let first_pab = P::first::<A, B, S>(pab);
    P::dimap(
        move |s: S| {
            let a = getter(&s);
            (a, s)
        },
        move |(b, s)| setter(s, b),
        first_pab,
    )
}
}

Laws

A well-behaved lens must satisfy three laws:

GetSet

Setting a value you just got changes nothing:

#![allow(unused)]
fn main() {
lens.set(s.clone(), lens.get(&s)) == s
}

SetGet

Getting after setting yields the value you set:

#![allow(unused)]
fn main() {
lens.get(&lens.set(s, b)) == b
}

SetSet

Setting twice is the same as setting once with the second value:

#![allow(unused)]
fn main() {
lens.set(lens.set(s.clone(), b1), b2) == lens.set(s, b2)
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Lens, SimpleLens};

#[derive(Debug, Clone, PartialEq)]
struct Person {
    name: String,
    age: u32,
}

let age_lens: SimpleLens<Person, u32> = Lens::new(
    |p: &Person| p.age,
    |p, age| Person { age, ..p },
);

let alice = Person { name: "Alice".into(), age: 30 };

// get
assert_eq!(age_lens.get(&alice), 30);

// set
let updated = age_lens.set(alice.clone(), 31);
assert_eq!(updated.age, 31);

// over -- modify the focus with a function
let updated = age_lens.over(alice.clone(), |a| a + 1);
assert_eq!(updated.age, 31);
}

Profunctor usage with FnP

#![allow(unused)]
fn main() {
use karpal_optics::{Lens, SimpleLens};
use karpal_profunctor::FnP;

let age_lens: SimpleLens<Person, u32> = Lens::new(
    |p: &Person| p.age,
    |p, age| Person { age, ..p },
);

let increment: Box<dyn Fn(u32) -> u32> = Box::new(|age| age + 1);
let transform_fn = age_lens.transform::<FnP>(increment);

let result = transform_fn(Person { name: "Alice".into(), age: 30 });
assert_eq!(result.age, 31);
}

ComposedLens

A lens built by chaining two or more lenses for deep field access.

Struct definition

#![allow(unused)]
fn main() {
/// A composed lens built from two lenses chained together.
///
/// Unlike `Lens`, which stores `fn` pointers, a composed lens stores
/// boxed closures because closure composition cannot produce `fn` pointers.
pub struct ComposedLens<S, T, X, Y> {
    getter: Box<dyn Fn(&S) -> X>,
    setter: Box<dyn Fn(S, Y) -> T>,
}

/// A simple (monomorphic) composed lens where `S == T` and `X == Y`.
pub type SimpleComposedLens<S, X> = ComposedLens<S, S, X, X>;
}

ComposedLens is produced by calling Lens::then() or ComposedLens::then(). It stores Box<dyn Fn> closures instead of fn pointers because closure composition captures the outer lens's getter and setter, which cannot be represented as bare function pointers.

Methods

#![allow(unused)]
fn main() {
impl<S, T, X, Y> ComposedLens<S, T, X, Y> {
    /// Extract the deeply-nested focus from the source.
    pub fn get(&self, s: &S) -> X;

    /// Replace the deeply-nested focus, producing a new source.
    pub fn set(&self, s: S, y: Y) -> T;
}

impl<S: Clone, T, X, Y> ComposedLens<S, T, X, Y> {
    /// Modify the deeply-nested focus by applying a function. Requires `S: Clone`.
    pub fn over(&self, s: S, f: impl FnOnce(X) -> Y) -> T;

    /// Chain another lens to focus even deeper.
    /// All type parameters must be `'static`.
    pub fn then<U, V>(self, inner: Lens<X, Y, U, V>) -> ComposedLens<S, T, U, V>
    where
        S: 'static, T: 'static, X: 'static, Y: 'static,
        U: 'static, V: 'static;
}
}

No transform on ComposedLens

ComposedLens does not provide a transform method. For profunctor-level composition, use nested Lens::transform calls on the original lenses instead:

#![allow(unused)]
fn main() {
// Instead of composed_lens.transform::<P>(pab), write:
let result = outer.transform::<P>(inner.transform::<P>(pab));
}

This avoids the need for Rc/Arc to share closures at the profunctor level and preserves the clean semantics of the profunctor encoding.

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Lens, SimpleLens};

#[derive(Debug, Clone, PartialEq)]
struct Company {
    name: String,
    ceo: Person,
}

let ceo_lens: SimpleLens<Company, Person> = Lens::new(
    |c: &Company| c.ceo.clone(),
    |c, ceo| Company { ceo, ..c },
);

let age_lens: SimpleLens<Person, u32> = Lens::new(
    |p: &Person| p.age,
    |p, age| Person { age, ..p },
);

// Compose: Company -> ceo -> age
let ceo_age = ceo_lens.then(age_lens);

let acme = Company {
    name: "Acme".into(),
    ceo: Person { name: "Alice".into(), age: 30 },
};

assert_eq!(ceo_age.get(&acme), 30);

let updated = ceo_age.set(acme.clone(), 31);
assert_eq!(updated.ceo.age, 31);

let updated = ceo_age.over(acme, |age| age + 1);
assert_eq!(updated.ceo.age, 31);
}

Prism

A first-class pattern matcher for focusing on one variant of a sum type.

Struct definition

#![allow(unused)]
fn main() {
/// A prism focuses on one variant of a sum type.
///
/// `S` -- source type, `T` -- modified source type,
/// `A` -- focus type (the variant's inner value), `B` -- replacement type.
///
/// Where a Lens uses Strong to decompose products, a Prism uses Choice
/// to decompose coproducts.
pub struct Prism<S, T, A, B> {
    /// Attempt to match. `Ok(a)` = matched, `Err(t)` = didn't match (pass-through).
    match_: fn(S) -> Result<A, T>,
    /// Construct a `T` from the replacement value.
    build: fn(B) -> T,
}

/// A simple (monomorphic) prism where `S == T` and `A == B`.
pub type SimplePrism<S, A> = Prism<S, S, A, A>;
}

A Prism is the dual of a Lens. Where a lens focuses on a field that is always present (product types), a prism focuses on a variant that may or may not be present (sum types). The match_ function returns Ok(a) if the variant matches and Err(t) if it does not, allowing the original value to pass through unchanged.

Methods

#![allow(unused)]
fn main() {
impl<S, T, A, B> Prism<S, T, A, B> {
    /// Create a new prism from a match function and a build function.
    pub fn new(match_: fn(S) -> Result<A, T>, build: fn(B) -> T) -> Self;

    /// Try to extract the focus. Returns `Some(a)` if the variant matches.
    /// Requires `S: Clone`.
    pub fn preview(&self, s: &S) -> Option<A>
    where
        S: Clone;

    /// Construct a `T` from a replacement value (inject/construct).
    pub fn review(&self, b: B) -> T;

    /// Replace the focus if the variant matches; otherwise pass through.
    pub fn set(&self, s: S, b: B) -> T;

    /// Modify the focus if the variant matches; otherwise pass through.
    pub fn over(&self, s: S, f: impl FnOnce(A) -> B) -> T;

    /// Profunctor encoding: transform a `P<A, B>` into a `P<S, T>`.
    /// Requires `Choice` profunctor `P`.
    /// All type parameters must be `'static`.
    pub fn transform<P: Choice>(&self, pab: P::P<A, B>) -> P::P<S, T>
    where
        S: 'static, T: 'static, A: 'static, B: 'static;

    // Conversions
    pub fn to_review(&self) -> Review<T, B>;
    pub fn to_setter(&self) -> Setter<S, T, A, B>;
    pub fn to_traversal(&self) -> Traversal<S, T, A, B>; // S: Clone
    pub fn to_fold(&self) -> Fold<S, A>;                  // S: Clone
}
}

How transform works (Choice)

The transform method connects a concrete prism to the profunctor hierarchy through the Choice trait. Given any Choice profunctor P and a value pab: P<A, B>, it produces P<S, T> by:

1. P::right(pab) lifts to P<Result<T, A>, Result<T, B>>
2. P::dimap pre-composes with match_ (swapping Ok/Err arms) and post-composes with build (reassembling)

The arm-swapping (Ok to Err, Err to Ok in pre-composition) is necessary because Choice::right acts on the Err branch of Result.

#![allow(unused)]
fn main() {
pub fn transform<P: Choice>(&self, pab: P::P<A, B>) -> P::P<S, T>
where
    S: 'static, T: 'static, A: 'static, B: 'static,
{
    let match_ = self.match_;
    let build = self.build;
    let right_pab = P::right::<A, B, T>(pab);
    P::dimap(
        move |s: S| match match_(s) {
            Ok(a) => Err(a),  // focus found -- Err arm for Choice::right
            Err(t) => Ok(t),  // no match -- Ok arm passes through
        },
        move |result: Result<T, B>| match result {
            Ok(t) => t,          // passed through unchanged
            Err(b) => build(b),  // transformed, rebuild
        },
        right_pab,
    )
}
}

Laws

A well-behaved prism must satisfy two laws:

PreviewReview

If a preview succeeds, reviewing the result reconstructs the original:

#![allow(unused)]
fn main() {
if let Some(a) = prism.preview(&s) {
    assert_eq!(prism.review(a), s);
}
}

ReviewPreview

Previewing a value built with review always succeeds and returns the original value:

#![allow(unused)]
fn main() {
assert_eq!(prism.preview(&prism.review(b)), Some(b));
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Prism, SimplePrism};

#[derive(Debug, Clone, PartialEq)]
enum Shape {
    Circle(f64),
    Rectangle(f64, f64),
}

let circle: SimplePrism<Shape, f64> = Prism::new(
    |s| match s {
        Shape::Circle(r) => Ok(r),
        Shape::Rectangle(w, h) => Err(Shape::Rectangle(w, h)),
    },
    Shape::Circle,
);

// preview -- extract if the variant matches
assert_eq!(circle.preview(&Shape::Circle(5.0)), Some(5.0));
assert_eq!(circle.preview(&Shape::Rectangle(3.0, 4.0)), None);

// review -- construct the variant
assert_eq!(circle.review(10.0), Shape::Circle(10.0));

// set -- replace the focus if matched
assert_eq!(circle.set(Shape::Circle(5.0), 10.0), Shape::Circle(10.0));
assert_eq!(
    circle.set(Shape::Rectangle(3.0, 4.0), 10.0),
    Shape::Rectangle(3.0, 4.0),
);

// over -- modify the focus if matched
assert_eq!(
    circle.over(Shape::Circle(5.0), |r| r * 2.0),
    Shape::Circle(10.0),
);
}

Profunctor usage with FnP

#![allow(unused)]
fn main() {
use karpal_optics::{Prism, SimplePrism};
use karpal_profunctor::FnP;

let circle: SimplePrism<Shape, f64> = Prism::new(
    |s| match s {
        Shape::Circle(r) => Ok(r),
        Shape::Rectangle(w, h) => Err(Shape::Rectangle(w, h)),
    },
    Shape::Circle,
);

let double: Box<dyn Fn(f64) -> f64> = Box::new(|r| r * 2.0);
let transform_fn = circle.transform::<FnP>(double);

// Matching variant is transformed
assert_eq!(transform_fn(Shape::Circle(5.0)), Shape::Circle(10.0));

// Non-matching variant passes through unchanged
assert_eq!(
    transform_fn(Shape::Rectangle(3.0, 4.0)),
    Shape::Rectangle(3.0, 4.0),
);
}

Getter

A read-only optic that extracts a single value from a source.

Struct definition

#![allow(unused)]
fn main() {
pub struct Getter<S, A> {
    get: fn(&S) -> A,
}

/// Composed variant (from .then() or conversions).
pub struct ComposedGetter<S, A> {
    get: Box<dyn Fn(&S) -> A>,
}
}

A Getter is the read-only component of a Lens. It can extract a focus but cannot modify it. Getters are typically obtained via Lens::to_getter() or Iso::to_getter().

Methods

#![allow(unused)]
fn main() {
impl<S, A> Getter<S, A> {
    pub fn new(get: fn(&S) -> A) -> Self;
    pub fn get(&self, s: &S) -> A;
    pub fn then<B>(self, inner: Getter<A, B>) -> ComposedGetter<S, B>;
}
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Lens, SimpleLens};

let age_lens: SimpleLens<Person, u32> = Lens::new(
    |p: &Person| p.age,
    |p, age| Person { age, ..p },
);

let getter = age_lens.to_getter();
assert_eq!(getter.get(&alice), 30);
}

Review

A write-only optic that constructs a target from a value.

Struct definition

#![allow(unused)]
fn main() {
pub struct Review<T, B> {
    build: fn(B) -> T,
}
}

A Review is the construction component of a Prism or Iso. It can build a target but cannot inspect one. At the profunctor level, Review corresponds to TaggedF, which is Choice but deliberately not Strong -- this enforces the write-only constraint at the type level.

Methods

#![allow(unused)]
fn main() {
impl<T, B> Review<T, B> {
    pub fn new(build: fn(B) -> T) -> Self;
    pub fn review(&self, b: B) -> T;
}
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Prism, SimplePrism};

let circle: SimplePrism<Shape, f64> = Prism::new(/* ... */);

let review = circle.to_review();
assert_eq!(review.review(5.0), Shape::Circle(5.0));
}

Setter

A modify-only optic that can transform foci but not read them independently.

Struct definition

#![allow(unused)]
fn main() {
pub struct Setter<S, T, A, B> {
    modify: Box<dyn Fn(S, &dyn Fn(A) -> B) -> T>,
}

pub type SimpleSetter<S, A> = Setter<S, S, A, A>;
}

A Setter always uses boxed closures since it is typically derived from composition or conversion (e.g. Lens::to_setter() or Prism::to_setter()). The modify closure takes the source and a transformation function, and returns the modified source.

Methods

#![allow(unused)]
fn main() {
impl<S, T, A, B> Setter<S, T, A, B> {
    pub fn new(modify: impl Fn(S, &dyn Fn(A) -> B) -> T + 'static) -> Self;
    pub fn over(&self, s: S, f: impl Fn(A) -> B) -> T;
    pub fn set(&self, s: S, b: B) -> T where B: Clone;
}
}

Laws

Identity

Modifying with identity changes nothing:

#![allow(unused)]
fn main() {
setter.over(s, |x| x) == s
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Lens, SimpleLens};

let age_lens: SimpleLens<Person, u32> = Lens::new(
    |p: &Person| p.age,
    |p, age| Person { age, ..p },
);

let setter = age_lens.to_setter();
let updated = setter.over(alice, |age| age + 1);
assert_eq!(updated.age, 31);

let updated = setter.set(alice, 99);
assert_eq!(updated.age, 99);
}

Traversal

A multi-focus optic that can get and modify zero or more foci.

Struct definition

#![allow(unused)]
fn main() {
pub struct Traversal<S, T, A, B> {
    get_all: Rc<dyn Fn(&S) -> Vec<A>>,
    modify_all: Rc<dyn Fn(S, &dyn Fn(A) -> B) -> T>,
}

pub type SimpleTraversal<S, A> = Traversal<S, S, A, A>;

/// Composed variant (from .then()).
pub struct ComposedTraversal<S, T, A, B> {
    get_all: Box<dyn Fn(&S) -> Vec<A>>,
    modify_all: Box<dyn Fn(S, &dyn Fn(A) -> B) -> T>,
}
}

A Traversal generalizes both Lens (exactly one focus) and Prism (zero or one focus) to zero or more foci. It stores Rc<dyn Fn> closures to allow sharing between get_all, modify_all, and the transform method.

Methods

#![allow(unused)]
fn main() {
impl<S, T, A, B> Traversal<S, T, A, B> {
    pub fn new(
        get_all: impl Fn(&S) -> Vec<A> + 'static,
        modify_all: impl Fn(S, &dyn Fn(A) -> B) -> T + 'static,
    ) -> Self;

    pub fn get_all(&self, s: &S) -> Vec<A>;
    pub fn over(&self, s: S, f: impl Fn(A) -> B) -> T;
    pub fn set(&self, s: S, b: B) -> T where B: Clone;

    /// Profunctor encoding via Traversing::wander.
    pub fn transform<P: Traversing>(&self, pab: P::P<A, B>) -> P::P<S, T>;

    pub fn to_fold(&self) -> Fold<S, A>;
    pub fn then<X, Y>(self, inner: Traversal<A, B, X, Y>) -> ComposedTraversal<S, T, X, Y>;
}
}

How transform works (Traversing)

The transform method connects a traversal to the profunctor hierarchy through Traversing. It calls P::wander(get_all, modify_all, pab) -- each profunctor instance decides how to interpret the traversal:

• FnP uses modify_all to apply the function to every focus
• ForgetF<R: Monoid> uses get_all to extract every focus, maps each through the profunctor, and combines results with Monoid

Laws

Identity

#![allow(unused)]
fn main() {
trav.over(s, |x| x) == s
}

Composition

#![allow(unused)]
fn main() {
trav.over(trav.over(s, f), g) == trav.over(s, |x| g(f(x)))
}

Example

#![allow(unused)]
fn main() {
use karpal_optics::{Traversal, SimpleTraversal};
use karpal_profunctor::{FnP, ForgetF};

// Traverse all elements of a Vec
let each: SimpleTraversal<Vec<i32>, i32> = Traversal::new(
    |v: &Vec<i32>| v.clone(),
    |v: Vec<i32>, f: &dyn Fn(i32) -> i32| v.into_iter().map(f).collect(),
);

assert_eq!(each.get_all(&vec![1, 2, 3]), vec![1, 2, 3]);
assert_eq!(each.over(vec![1, 2, 3], |x| x * 10), vec![10, 20, 30]);
assert_eq!(each.set(vec![1, 2, 3], 0), vec![0, 0, 0]);

// Profunctor usage: FnP applies function to all elements
let double: Box<dyn Fn(i32) -> i32> = Box::new(|x| x * 2);
let f = each.transform::<FnP>(double);
assert_eq!(f(vec![1, 2, 3]), vec![2, 4, 6]);

// Profunctor usage: ForgetF<String> concatenates results
let to_str: Box<dyn Fn(i32) -> String> = Box::new(|x| x.to_string());
let g = each.transform::<ForgetF<String>>(to_str);
assert_eq!(g(vec![1, 2, 3]), "123");
}

Fold

A read-only multi-focus optic with powerful aggregation methods.

Struct definition

#![allow(unused)]
fn main() {
pub struct Fold<S, A> {
    fold_fn: Box<dyn Fn(&S) -> Vec<A>>,
}

/// Composed variant (from .then()).
pub struct ComposedFold<S, A> {
    fold_fn: Box<dyn Fn(&S) -> Vec<A>>,
}
}

A Fold is the read-only counterpart of a Traversal. It extracts zero or more foci from a source, with convenience methods for aggregation via Monoid. Folds are typically obtained from Lens::to_fold(), Prism::to_fold(), or Traversal::to_fold().

Methods

#![allow(unused)]
fn main() {
impl<S, A> Fold<S, A> {
    pub fn new(fold_fn: impl Fn(&S) -> Vec<A> + 'static) -> Self;
    pub fn get_all(&self, s: &S) -> Vec<A>;
    pub fn fold_map<R: Monoid>(&self, s: &S, f: impl Fn(A) -> R) -> R;
    pub fn any(&self, s: &S, f: impl Fn(&A) -> bool) -> bool;
    pub fn all(&self, s: &S, f: impl Fn(&A) -> bool) -> bool;
    pub fn find(&self, s: &S, f: impl Fn(&A) -> bool) -> Option<A>;
    pub fn length(&self, s: &S) -> usize;
    pub fn then<B>(self, inner: Fold<A, B>) -> ComposedFold<S, B>;
}
}

The fold_map method maps each focus to a Monoid value and combines them. This is the core aggregation operation -- any, all, find, and length are convenience wrappers.

Example

#![allow(unused)]
fn main() {
use karpal_optics::Fold;

let fold = Fold::new(|v: &Vec<i32>| v.clone());

assert_eq!(fold.get_all(&vec![1, 2, 3]), vec![1, 2, 3]);

// fold_map: sum all elements (i32 Monoid is additive)
let sum: i32 = fold.fold_map(&vec![1, 2, 3], |x| x);
assert_eq!(sum, 6);

// fold_map: concatenate string representations
let s: String = fold.fold_map(&vec![1, 2, 3], |x| x.to_string());
assert_eq!(s, "123");

// Predicate queries
assert!(fold.any(&vec![1, 2, 3], |x| *x > 2));
assert!(fold.all(&vec![1, 2, 3], |x| *x > 0));
assert_eq!(fold.find(&vec![1, 2, 3], |x| *x > 1), Some(2));
assert_eq!(fold.length(&vec![1, 2, 3]), 3);
}

Optic Conversions

Optics form a subtyping hierarchy. A stronger optic can always be used where a weaker one is expected. Karpal provides explicit to_* methods for these conversions:

#![allow(unused)]
fn main() {
  Iso
  / \
Lens  Prism
 |  \  / |
 | Traversal
 |    |    |
 | +--+---+
 | |      |
Getter  Setter  Review
   \    |
    \   |
     Fold
}

Note: Iso::to_lens() returns a ComposedLens (not Lens) because the conversion captures the iso's backward function in a closure, which cannot be represented as a bare fn pointer.

Composing Lenses with .then()

Lenses compose naturally via the .then() method. Each call to then produces a ComposedLens that focuses one level deeper. You can chain as many lenses as needed for deep access into nested structures.

#![allow(unused)]
fn main() {
use karpal_optics::{Lens, SimpleLens};

#[derive(Debug, Clone, PartialEq)]
struct Address {
    street: String,
    city: String,
}

#[derive(Debug, Clone, PartialEq)]
struct Employee {
    name: String,
    addr: Address,
}

#[derive(Debug, Clone, PartialEq)]
struct Org {
    title: String,
    lead: Employee,
}

let lead_lens: SimpleLens<Org, Employee> = Lens::new(
    |o: &Org| o.lead.clone(),
    |o, lead| Org { lead, ..o },
);

let addr_lens: SimpleLens<Employee, Address> = Lens::new(
    |e: &Employee| e.addr.clone(),
    |e, addr| Employee { addr, ..e },
);

let city_lens: SimpleLens<Address, String> = Lens::new(
    |a: &Address| a.city.clone(),
    |a, city| Address { city, ..a },
);

// Three-deep composition: Org -> lead -> addr -> city
let org_city = lead_lens.then(addr_lens).then(city_lens);

let org = Org {
    title: "R&D".into(),
    lead: Employee {
        name: "Alice".into(),
        addr: Address {
            street: "123 Main St".into(),
            city: "Springfield".into(),
        },
    },
};

// Read a deeply nested field
assert_eq!(org_city.get(&org), "Springfield");

// Update a deeply nested field
let updated = org_city.set(org.clone(), "Shelbyville".into());
assert_eq!(updated.lead.addr.city, "Shelbyville");
assert_eq!(updated.lead.addr.street, "123 Main St");

// Modify a deeply nested field with a function
let updated = org_city.over(org, |c| c.to_uppercase());
assert_eq!(updated.lead.addr.city, "SPRINGFIELD");
}

For profunctor-level composition (where you need transform), nest the original lens transforms instead of using the composed lens:

#![allow(unused)]
fn main() {
use karpal_profunctor::FnP;

let ceo_lens: SimpleLens<Company, Person> = /* ... */;
let age_lens: SimpleLens<Person, u32> = /* ... */;

let increment: Box<dyn Fn(u32) -> u32> = Box::new(|age| age + 1);

// Nested transform: equivalent to composed_lens.over(company, |age| age + 1)
let transform_fn = ceo_lens.transform::<FnP>(age_lens.transform::<FnP>(increment));
}

Karpal is licensed under Apache-2.0 + CLA. View on GitHub.

Abstract Algebra

Higher algebraic structures built on top of Semigroup & Monoid. These traits live in the karpal-algebra crate and extend the hierarchy with groups, rings, fields, lattices, and vector spaces.

Overview

Trait Hierarchy

Semigroup (karpal-core)         Semiring (independent)      Lattice (independent)
  |                               |                           |
Monoid (karpal-core)            Ring                        BoundedLattice
  |                               |
Group                           Field
  |
AbelianGroup (marker)           Module<R: Ring>: AbelianGroup
                                  |
                                VectorSpace<F: Field>

The Semigroup → Monoid → Group chain extends the existing karpal-core hierarchy. Semiring and Lattice are independent hierarchies — they define their own operations to avoid the "which operation is the semigroup?" ambiguity.

Newtype Wrappers

The default Semigroup for numeric types uses addition. Newtype wrappers in karpal-core let you select a different combining strategy. This is the standard approach to the "a type can be a monoid in multiple ways" problem.

Sum & Product

Select additive or multiplicative combining.

Definition

#![allow(unused)]
fn main() {
pub struct Sum<T>(pub T);      // Semigroup: +, Monoid: 0
pub struct Product<T>(pub T);  // Semigroup: *, Monoid: 1
}

Examples

#![allow(unused)]
fn main() {
use karpal_core::{Sum, Product, Semigroup, Monoid};
use karpal_core::Foldable;
use karpal_core::hkt::VecF;

// Sum uses addition
assert_eq!(Sum(3i32).combine(Sum(4)), Sum(7));
assert_eq!(Sum::<i32>::empty(), Sum(0));

// Product uses multiplication
assert_eq!(Product(3i32).combine(Product(4)), Product(12));
assert_eq!(Product::<i32>::empty(), Product(1));

// Fold a list as a product instead of a sum
let product = VecF::fold_map(vec![1, 2, 3, 4], |x| Product(x));
assert_eq!(product, Product(24));
}

Instances

Min & Max

Select minimum or maximum combining for ordered types.

Definition

#![allow(unused)]
fn main() {
pub struct Min<T>(pub T);  // Semigroup: min, Monoid: T::MAX
pub struct Max<T>(pub T);  // Semigroup: max, Monoid: T::MIN
}

Examples

#![allow(unused)]
fn main() {
use karpal_core::{Min, Max, Semigroup, Monoid};

assert_eq!(Min(3i32).combine(Min(7)), Min(3));
assert_eq!(Max(3i32).combine(Max(7)), Max(7));

// Monoid identity: combining with empty returns the other value
assert_eq!(Min::<i32>::empty().combine(Min(5)), Min(5));  // MAX.min(5) = 5
assert_eq!(Max::<i32>::empty().combine(Max(5)), Max(5));  // MIN.max(5) = 5
}

Monoid is implemented for all integer types (i8–i128, u8–u128) using T::MAX for Min and T::MIN for Max. Floats have Semigroup but not Monoid because f64::INFINITY is debatable and NaN breaks the identity law.

First & Last

Select the first or last Some value.

Definition

#![allow(unused)]
fn main() {
pub struct First<T>(pub T);  // Only Semigroup+Monoid for Option<T>
pub struct Last<T>(pub T);   // Only Semigroup+Monoid for Option<T>
}

Examples

#![allow(unused)]
fn main() {
use karpal_core::{First, Last, Semigroup, Monoid};

// First picks the first Some value
assert_eq!(First(Some(1)).combine(First(Some(2))), First(Some(1)));
assert_eq!(First(None::<i32>).combine(First(Some(2))), First(Some(2)));

// Last picks the last Some value
assert_eq!(Last(Some(1)).combine(Last(Some(2))), Last(Some(2)));
assert_eq!(Last(Some(1)).combine(Last(None)), Last(Some(1)));

// Monoid identity is None (neutral under "pick the Some")
assert_eq!(First::<Option<i32>>::empty(), First(None));
}

First and Last are only implemented for Option<T>, matching Haskell's Data.Monoid.First/Last. A blanket First<T> would conflict with the Option specialization due to Rust's coherence rules.

Group Hierarchy

Group

A Monoid where every element has an inverse.

Signature

#![allow(unused)]
fn main() {
pub trait Group: Monoid {
    fn invert(self) -> Self;

    // Provided: a.combine(b.invert())
    fn combine_inverse(self, other: Self) -> Self { ... }
}
}

Laws

Left Inverse

#![allow(unused)]
fn main() {
a.invert().combine(a) == Self::empty()
}

Right Inverse

#![allow(unused)]
fn main() {
a.combine(a.invert()) == Self::empty()
}

Instances

Unsigned integers are not groups — they have no additive inverse.

Examples

#![allow(unused)]
fn main() {
use karpal_algebra::Group;
use karpal_core::{Semigroup, Monoid};

assert_eq!(5i32.invert(), -5);
assert_eq!(5i32.combine(5i32.invert()), 0);  // right inverse
assert_eq!(10i32.combine_inverse(3), 7);      // 10 + (-3) = 7
}

AbelianGroup

A Group whose operation is commutative. Marker trait — commutativity verified by property tests.

Signature

#![allow(unused)]
fn main() {
pub trait AbelianGroup: Group {}
}

Commutativity

#![allow(unused)]
fn main() {
a.combine(b) == b.combine(a)
}

All Group instances in Karpal are abelian (addition is commutative). The marker trait exists so that Module can require it — modules are defined over abelian groups.

Instances

All signed integers (i8–i128), f32, f64, and (A, B) where both components are AbelianGroup.

Semiring / Ring / Field

These traits model the algebraic structures from abstract algebra, with two operations: addition and multiplication. They are independent of Semigroup — they define their own method names to avoid the ambiguity of which operation the semigroup uses.

Semiring

A type with addition (commutative monoid) and multiplication (monoid), where multiplication distributes over addition.

Signature

#![allow(unused)]
fn main() {
pub trait Semiring: Sized + Clone + PartialEq {
    fn zero() -> Self;
    fn one() -> Self;
    fn add(self, other: Self) -> Self;
    fn mul(self, other: Self) -> Self;
}
}

Laws

Additive Commutative Monoid

#![allow(unused)]
fn main() {
a.add(b) == b.add(a)                    // commutativity
a.add(b).add(c) == a.add(b.add(c))      // associativity
Self::zero().add(a) == a                 // identity
}

Multiplicative Monoid

#![allow(unused)]
fn main() {
a.mul(b).mul(c) == a.mul(b.mul(c))      // associativity
Self::one().mul(a) == a                  // identity
}

Distribution & Annihilation

#![allow(unused)]
fn main() {
a.mul(b.add(c)) == a.mul(b).add(a.mul(c))  // left distribution
a.add(b).mul(c) == a.mul(c).add(b.mul(c))  // right distribution
Self::zero().mul(a) == Self::zero()         // annihilation
}

Instances

The bool semiring is the classic example: OR is "addition" (with identity false), AND is "multiplication" (with identity true), AND distributes over OR, and false && x == false (annihilation).

Examples

#![allow(unused)]
fn main() {
use karpal_algebra::Semiring;

assert_eq!(3i32.add(4), 7);
assert_eq!(3i32.mul(4), 12);
assert_eq!(i32::zero(), 0);
assert_eq!(i32::one(), 1);

// Boolean semiring
assert_eq!(false.add(true), true);   // OR
assert_eq!(true.mul(false), false);  // AND
}

Ring

A Semiring with additive inverses (negation).