JoinSemilattice

algebra

Trait JoinSemilattice 

Source 
pub trait JoinSemilattice: Sized {
    // Required method
    fn join(&self, other: &Self) -> Self;

    // Provided methods
    fn join_assign(&mut self, other: &Self) { ... }
    fn leq(&self, other: &Self) -> bool
       where Self: PartialEq { ... }
    fn join_all<I>(it: I) -> Option<Self>
       where I: IntoIterator<Item = Self> { ... }
}
Expand description

A join-semilattice: a type with an associative, commutative, and idempotent binary operation (the join).

Laws (not enforced by type system):

  • Associative: a.join(b).join(c) == a.join(b.join(c))
  • Commutative: a.join(b) == b.join(a)
  • Idempotent: a.join(a) == a

The join operation computes the least upper bound (supremum) in the induced partial order: x ≤ y iff x.join(y) == y.

§Example

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

let a = Max(3);
let b = Max(5);

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

// Idempotent
assert_eq!(a.join(&a), a);

Required Methods§

Source

fn join(&self, other: &Self) -> Self

The join (least upper bound).

Provided Methods§

Source

fn join_assign(&mut self, other: &Self)

In-place variant.

Source

fn leq(&self, other: &Self) -> bool
where Self: PartialEq,

Derived partial order: x ≤ y iff x ⊔ y = y.

Source

fn join_all<I>(it: I) -> Option<Self>
where I: IntoIterator<Item = Self>,

Join a finite iterator of values. Returns None for empty iterators.

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types§

Source§

impl JoinSemilattice for ()

(): trivial unit lattice

The unit type forms a trivial lattice with a single element.

Source§

fn join(&self, _other: &Self) -> Self

Source§

impl<L: JoinSemilattice + Clone> JoinSemilattice for Option<L>

Option<L>: lifted lattice

Option<L> lifts a lattice L by adding a new bottom element (None).

  • None is the bottom element
  • Some(a).join(Some(b)) = Some(a.join(b))
  • None.join(x) = x.join(None) = x

This is useful for representing “optional” lattice values where absence is distinct from any present value.

Source§

fn join(&self, other: &Self) -> Self

Source§

impl<T: Eq + Hash + Clone> JoinSemilattice for HashSet<T>

HashSet<T>: join = union

A HashSet<T> forms a join-semilattice under set union:

  • join = union (∪)
  • bottom = empty set (∅)

This makes HashSet ideal for tracking “sets of things” in distributed systems where we want to accumulate all observed values across replicas.

Source§

fn join(&self, other: &Self) -> Self

Source§

impl<T: Ord + Clone> JoinSemilattice for BTreeSet<T>

BTreeSet<T>: join = union

Same semantics as HashSet, but uses Ord instead of Hash.

Source§

fn join(&self, other: &Self) -> Self

Implementors§