Crate algebra

Crate algebra 

Source
Expand description

Algebraic structures for monotonic accumulation and lattice-based reduction.

This module provides foundational traits and types for expressing commutative, associative, and idempotent operations, enabling principled accumulation in distributed systems.

§Quick Start

use algebra::BoundedJoinSemilattice;
use algebra::JoinSemilattice;
use algebra::Max;

// Max<T> wraps an ordered type where join = max
let a = Max(5);
let b = Max(3);
let c = a.join(&b);
assert_eq!(c, Max(5));

// Bottom element is the identity for join
assert_eq!(Max::<i32>::bottom().join(&a), a);

§Core Concepts

  • Semigroup: A type with an associative binary operation (combine). Examples: addition, max, string concatenation.

  • Monoid: A semigroup with an identity element (empty). Examples: 0 for addition, empty string for concatenation.

  • CommutativeMonoid: A monoid where combine is commutative.

  • Group: A monoid where every element has an inverse.

  • AbelianGroup: A commutative group.

  • JoinSemilattice: A commutative, associative, and idempotent merge operation (join). You can think of join as computing a least upper bound: it produces the smallest value that is “at least as large as” both inputs under the order induced by join (a ≤ b iff a.join(&b) == b). Idempotence (a ⊔ a = a) is what makes this safe under at-least-once delivery: re-merging the same update is a no-op. Examples: max, min, set union.

  • BoundedJoinSemilattice: A join-semilattice with an explicit bottom element (⊥) that serves as the identity for join.

§Homomorphisms

  • SemigroupHom: A structure-preserving map between semigroups.
  • MonoidHom: A structure-preserving map between monoids.

§Provided Types

  • Max<T>: Ordered type where join = max, bottom = minimum.
  • Min<T>: Ordered type where join = min, bottom = maximum.
  • Any: Boolean where join = || (OR), bottom = false.
  • All: Boolean where join = && (AND), bottom = true.
  • LatticeMap<K, V>: Pointwise map lattice over HashMap.
  • LWW<T>: Last-Writer-Wins register CRDT.

§Why Idempotence Matters for Distributed Systems

In distributed systems with at-least-once delivery, messages may be delivered multiple times due to retries, network partitions, or failover. Non-idempotent operations (like addition) produce incorrect results when applied multiple times:

// Problem: sum accumulator with duplicates
sum(1, 2, 2, 3)  // Intended: 1+2+3=6, Actual: 1+2+2+3=8 ❌

// Solution: max accumulator is idempotent
max(1, 2, 2, 3)  // Always 3, regardless of duplicates ✓

By using lattice types like Max and Min, we make the idempotence guarantee explicit in the type system.

§Examples

use algebra::BoundedJoinSemilattice;
use algebra::JoinSemilattice;
use algebra::Max;

let a = Max(5);
let b = Max(10);
let c = a.join(&b);
assert_eq!(c, Max(10));

// Idempotence: joining with self has no effect
assert_eq!(c.join(&c), c);

// Identity: joining with bottom has no effect
assert_eq!(c.join(&Max::bottom()), c);

Structs§

All
Newtype wrapper for bool where join is logical AND.
Any
Newtype wrapper for bool where join is logical OR.
LWW
A Last-Writer-Wins register lattice.
LatticeMap
Pointwise map lattice over HashMap.
Max
Newtype wrapper for an Ord type where join is max.
Min
Newtype wrapper for an Ord type where join is min.

Traits§

AbelianGroup
An abelian group (commutative group): a group where combine is commutative.
BoundedJoinSemilattice
A bounded join-semilattice: a join-semilattice with a bottom element that serves as the identity for join.
CommutativeMonoid
A commutative monoid: a monoid where combine is commutative.
Group
A group: a monoid where every element has an inverse.
JoinSemilattice
A join-semilattice: a type with an associative, commutative, and idempotent binary operation (the join).
Monoid
A monoid: a semigroup with an identity element.
MonoidHom
A monoid homomorphism: a structure-preserving map between monoids that preserves both combine and identity.
MonoidHomFromTo
Helper trait for explicitly specifying source and target monoids.
Semigroup
A semigroup: a type with an associative binary operation.
SemigroupHom
A semigroup homomorphism: a structure-preserving map between semigroups that preserves combine.
SemigroupHomFromTo
Helper trait for explicitly specifying source and target types.