Crate algebra_core 

algebra-core — Core algebraic abstractions

Part of the postbox workspace

This crate provides fundamental algebraic structures as Rust traits:

• Semigroup: associative binary operation
• Monoid: semigroup with identity element
• CommutativeMonoid: monoid with commutative operation
• Group: monoid with inverse elements
• AbelianGroup: commutative group
• SemigroupHom: structure-preserving map between semigroups
• MonoidHom: structure-preserving map between monoids
• JoinSemilattice: associative, commutative, idempotent operation (least upper bound)
• BoundedJoinSemilattice: join-semilattice with bottom element
• MeetSemilattice: associative, commutative, idempotent operation (greatest lower bound)
• BoundedMeetSemilattice: meet-semilattice with top element
• Lattice: both join and meet operations
• BoundedLattice: lattice with both bottom and top elements

Recursion schemes

• TypeApp: higher-kinded type encoding
• Functor: functor on one type parameter
• Fix: least fixed point (μF) for recursive data structures
• fold: fold / catamorphism for Fix (given an F-algebra)

Quick start

use algebra_core::{Semigroup, Monoid, CommutativeMonoid, Sum};

// Sum<T> is provided by the library for addition monoids
let a = Sum(5);
let b = Sum(3);
let c = a.combine(&b);
assert_eq!(c, Sum(8));
assert_eq!(Sum::<i32>::empty(), Sum(0));

Standard library implementations

This crate provides implementations for common standard library types:

Sets (union as join, intersection as meet)

• HashSet<T>: JoinSemilattice, BoundedJoinSemilattice, MeetSemilattice, Lattice, Semigroup, Monoid, CommutativeMonoid
  • join = union, meet = intersection, bottom = ∅ (no top for arbitrary T)
• BTreeSet<T>: JoinSemilattice, BoundedJoinSemilattice, MeetSemilattice, Lattice, Semigroup, Monoid, CommutativeMonoid

Booleans (OR/AND lattice)

• bool: JoinSemilattice, BoundedJoinSemilattice, MeetSemilattice, BoundedMeetSemilattice, BoundedLattice
  • join = OR, meet = AND, bottom = false, top = true

Strings (concatenation)

• String: Semigroup, Monoid

Optional values (lifted monoid/lattice)

• Option<M> (where M: Semigroup + Clone): Semigroup
• Option<M> (where M: Monoid + Clone): Monoid, Semigroup
• Option<M> (where M: CommutativeMonoid + Clone): CommutativeMonoid
• Option<L> (where L: JoinSemilattice + Clone): JoinSemilattice, BoundedJoinSemilattice
  • None is bottom, Some(a) ⊔ Some(b) = Some(a ⊔ b)
• Option<L> (where L: MeetSemilattice + Clone): MeetSemilattice
  • None ⊓ x = None (bottom ⊓ anything = bottom)
• Option<L> (where L: BoundedMeetSemilattice + Clone): BoundedMeetSemilattice
  • top = Some(L::top())

Tuples (product algebras)

• (): All traits (trivial implementations)
• (A,), (A, B), (A, B, C), (A, B, C, D):
  • Semigroup, Monoid, CommutativeMonoid (componentwise)
  • JoinSemilattice, BoundedJoinSemilattice (componentwise)
  • MeetSemilattice, BoundedMeetSemilattice (componentwise)

All tuple implementations require component types to implement the corresponding trait, and operations are applied componentwise.

Re-exports

pub use fix::fold;

pub use fix::Fix;

pub use fix::Functor;

pub use fix::TypeApp;

Modules

fix

Fixed-point types and recursion schemes

Structs

Product

Wrapper type for the multiplication monoid.

Sum

Wrapper type for the addition monoid.

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.

BoundedLattice

A bounded lattice: a lattice with both bottom and top elements.

BoundedMeetSemilattice

A bounded meet-semilattice: a meet-semilattice with a top element.

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, idempotent binary operation.

Lattice

A lattice: a type with both join (least upper bound) and meet (greatest lower bound) operations.

MeetSemilattice

A meet-semilattice: a type with an associative, commutative, idempotent binary operation that computes greatest lower bounds.

Monoid

A monoid: a semigroup with an identity element.

MonoidHom

A monoid homomorphism: a structure-preserving map between monoids.

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.

SemigroupHomFromTo

Helper trait for explicitly specifying source and target types.

Derive Macros

AbelianGroup

Derive macro for AbelianGroup.

BoundedJoinSemilattice

Derive macro for BoundedJoinSemilattice.

BoundedMeetSemilattice

Derive macro for BoundedMeetSemilattice.

CommutativeMonoid

Derive macro for CommutativeMonoid.

Group

Derive macro for Group.

JoinSemilattice

Derive macro for JoinSemilattice.

MeetSemilattice

Derive macro for MeetSemilattice.

Monoid

Derive macro for Monoid.

Semigroup

Derive macro for Semigroup.