algebra
An associative operation with an identity: the pair (id, op), written Monoid<T>(id, op) or, naming both, Monoid<T>(id: e, op: (a, b) => ...).
Generated from spec/std/algebra.cp by cpl doc --format json.
Monoid
pub struct Monoid<T>(id: T, op: (T, T) -> T)An associative operation with an identity: the pair (id, op), written
Monoid<T>(id, op) or, naming both, Monoid<T>(id: e, op: (a, b) => ...).
op(a, b) folds a on the left of b, which matters when it does not commute.
The laws are checked by laws_hold(m, samples).
Monoid.of
fn of<M>(m: M) -> Monoid<T>The monoid a structure was handed: a Monoid is itself, and a bare operator brings its
identity: zero for +, ^, | and gcd, one for *, all bits for &, and for min /
max the far end of T (None on a ?T). Any other fn has no known identity and needs
Monoid(id, op).
- cost: O(1)
- traps: never (an operator without a known identity is a compile-time error)
Examples:
Monoid<Int>.of(+).id == 0Monoid<Int>.of(*).op(3, 4) == 12Monoid<?Int>.of(min).id == None
Action
pub struct Action<T, F>(id: F, compose: (F, F) -> F, apply: (F, T, Int) -> T, over: Monoid<T>)A lazy update F on values T folded with over. Name every argument, in any order, so
the roles read at the call site:
Action<Int, (Int, Int)>(
id: (1, 0),
compose: (new_f, old_f) => (new_f.0 * old_f.0, new_f.0 * old_f.1 + new_f.1),
apply: (f, val, span) => f.0 * val + f.1 * span,
over: +,
)idis the no-op tag (apply(id, x, len) == x).compose(new_f, old_f)appliesold_ffirst and thennew_f.apply(f, val, span)returns the folded valuevalofspancovered leaves after applyingf.
The positional form Action(id, compose, apply, over: op) is the same call. A flipped
compose still type-checks, so check a hand-written action once with
laws_hold(act, T: [...], F: [...]).
Action.new
fn new<M>(id: F = F.zero, compose: (F, F) -> F = (+), apply: (F, T, Int) -> T, over: M = (+)) -> Action<T, F>A lazy action of tags F on values T folded with over. id is the no-op tag,
compose(new_f, old_f) applies old_f first and then new_f, and apply(f, val, span)
is the folded value of span leaves, val, after f. id, compose and over default
to F.zero, F's + and T's +, so an additive tag on sums needs only apply.
- cost: O(1)
- traps: never (laws are not checked here; use
laws_hold)
Examples:
Action<Int, Int>(apply: (d, x, span) => x + d * span).apply(2, 10, 3) == 16Action<Int, Int>(apply: (d, x, span) => x + d * span).compose(2, 5) == 7
Action.of
fn of<A, M>(a: A, op: M) -> Action<T, F>Resolve a stock action (add, assign, affine) or an Action against fold op.
- cost: O(1)
- traps: never
Desc
pub struct Desc<T>(xx with its order reversed. Build it with desc(x).
Desc<T>
impl Ord for Desc<T>Desc<T>.lt
fn lt(a, b)Desc<T>
impl Show for Desc<T>Desc<T>.show
fn show(a)Reversible
pub trait ReversibleA folded value that can be read from the other end. A fold along a tree path walks some
stretches upwards; Rooted.fold_path reverses those with rev. A type that does not
implement it is its own reverse, which is right for every commutative operation.
Reversible.rev
fn rev(self) -> SelfMaxSub
pub struct MaxSub(has: Bool, best: Int, total: Int, pre: Int, suf: Int)Maximum non-empty subarray summary (Kadane monoid).
Concatenation (+ or MaxSub.join) is associative with identity MaxSub.empty in O(1);
s.scale(k) scales every element by non-negative k in O(1).
Implements Reversible (swapping pre and suf) for tree-path folds.
MaxSub.empty
fn empty() -> MaxSubThe summary of no elements: the identity of join. It has no best subarray.
- cost: O(1)
- traps: never
Examples:
MaxSub.empty().try_best == None
MaxSub.of
fn of(v: Int) -> MaxSubThe summary of the single element v: best, total, best prefix and best suffix are all v.
- cost: O(1)
- traps: never
Examples:
MaxSub.of(-3).try_best == Some(-3)
MaxSub.join
fn join(a: MaxSub, b: MaxSub) -> MaxSubThe summary of a's elements followed by b's (the same as a + b). Associative, with
MaxSub.empty() as identity; the best subarray may cross the seam (a.suf + b.pre).
- cost: O(1)
- traps: never (overflow wraps in release, traps in debug)
Examples:
MaxSub.join(MaxSub.of(2), MaxSub.of(-1)).try_best == Some(2)fold(MaxSub.monoid(), [MaxSub.of(v) for v in [2, -5, 3, 1]]).try_best == Some(4)
MaxSub.scale
fn scale(self, k: Int) -> MaxSubThe summary of the same elements each multiplied by k (the same as self * k). Exact
because every maximum scales by a non-negative factor; the empty summary stays empty.
- cost: O(1)
- traps: when
k < 0
Examples:
MaxSub.of(-3).scale(2).try_best == Some(-6)MaxSub.of(-3).scale(0).try_best == Some(0)
MaxSub.try_best
fn try_best(self) -> ?IntThe largest sum of a non-empty contiguous run of the summarized elements, or None for
the empty summary.
- cost: O(1)
- empty:
None - traps: never
Examples:
MaxSub.join(MaxSub.of(-1), MaxSub.of(-2)).try_best == Some(-1)
MaxSub.monoid
fn monoid() -> Monoid<MaxSub>Monoid(MaxSub.empty(), MaxSub.join), for SegTree and fold.
- cost: O(1)
- traps: never
Examples:
MaxSub.monoid().id.try_best == None
MaxSub
impl Add for MaxSubMaxSub.add
fn add(a, b)MaxSub
impl Mul<Int> for MaxSubO(1). Scale every underlying value by k >= 0.
MaxSub.mul
fn mul(self, k: Int) -> MaxSubMaxSub
impl Reversible for MaxSubMaxSub.rev
fn rev(self) -> MaxSubSemigroup
pub struct Semigroup<T>(op: (T, T) -> T)O(1) construction. Associative operation without an identity, for non-empty folds
(SparseTable, DisjointSparseTable, SegTree.try_fold).
Group
pub struct Group<T>(id: T, op: (T, T) -> T, inv: T -> T)O(1) construction. Associative operation with identity and inverse (inv),
for generalized Fenwick trees and difference structures.
Group.of
fn of<G>(g: G) -> Group<T>The group a structure was handed: a Group is itself, + brings zero and negation, ^
brings zero and itself as inverse. Any other fn needs Group(id, op, inv).
- cost: O(1)
- traps: never (an operator without a known inverse is a compile-time error)
Examples:
Group<Int>.of(+).inv(5) == -5Group<Int>.of(^).inv(5) == 5
MinCount
pub struct MinCount<T>(val: T, count: Int)O(1) per merge. Minimum value together with its multiplicity, for counting zeros or
minimum-covered cells under range add (AddMinCount).
MinCount.of
fn of(v: T) -> MinCount<T>The summary of the single element v: value v, count 1.
- cost: O(1)
- traps: never
Examples:
MinCount.of(5).count == 1
MinCount.join
fn join(a: MinCount<T>, b: MinCount<T>) -> MinCount<T>The smaller value with its count; on equal values, the value with both counts summed.
- cost: O(1)
- ties: equal values merge; their counts add
- traps: never
Examples:
MinCount.join(MinCount.of(2), MinCount.of(2)).count == 2MinCount.join(MinCount(1, 3), MinCount(2, 5)).val == 1
MinCount.monoid
fn monoid() -> Monoid<MinCount<T>>Monoid(id, MinCount.join) with identity value the far end of T (as Monoid.of(min))
and count 0, for SegTree and fold.
- cost: O(1)
- traps: never
Examples:
fold(MinCount.monoid(), [MinCount.of(v) for v in [3, 1, 1]]).count == 2
MaxCount
pub struct MaxCount<T>(val: T, count: Int)O(1) per merge. Maximum value together with its multiplicity (range add: SegTree(MaxCount.monoid, a, act: add)).
MaxCount.of
fn of(v: T) -> MaxCount<T>The summary of the single element v: value v, count 1.
- cost: O(1)
- traps: never
Examples:
MaxCount.of(5).count == 1
MaxCount.join
fn join(a: MaxCount<T>, b: MaxCount<T>) -> MaxCount<T>The larger value with its count; on equal values, the value with both counts summed.
- cost: O(1)
- ties: equal values merge; their counts add
- traps: never
Examples:
MaxCount.join(MaxCount(4, 1), MaxCount(4, 2)).count == 3
MaxCount.monoid
fn monoid() -> Monoid<MaxCount<T>>Monoid(id, MaxCount.join) with identity value the low end of T (as Monoid.of(max))
and count 0, for SegTree and fold.
- cost: O(1)
- traps: never
Examples:
fold(MaxCount.monoid(), [MaxCount.of(v) for v in [3, 1, 3]]).count == 2
Affine
pub struct Affine<T>(a: T, b: T)O(1) per composition/eval. Affine map x -> a * x + b over any ring T (Int, Mod<P>).
Affine.id
fn id() -> Affine<T>The identity map x -> 1 * x + 0.
- cost: O(1)
- traps: never
Examples:
Affine<Int>.id().eval(7) == 7
Affine.eval
fn eval(self, x: T) -> Ta * x + b.
- cost: O(1)
- traps: never (overflow wraps in release, traps in debug)
Examples:
Affine(2, 3).eval(5) == 13
Affine.then
fn then(f: Affine<T>, g: Affine<T>) -> Affine<T>f first, then g: the map x -> g.eval(f.eval(x)), which is
Affine(g.a * f.a, g.a * f.b + g.b).
- cost: O(1)
- traps: never (overflow wraps in release, traps in debug)
Examples:
Affine.then(Affine(2, 0), Affine(1, 1)).eval(5) == 11Affine.then(Affine(1, 1), Affine(2, 0)).eval(5) == 12
Affine.monoid
fn monoid() -> Monoid<Affine<T>>Monoid(Affine.id(), Affine.then): a fold applies the leftmost map first, so a segment tree
over maps answers "push x through positions l..r in order".
- cost: O(1)
- traps: never
Examples:
fold(Affine.monoid(), [Affine(1, 1), Affine(2, 0)]).eval(5) == 12
Word
impl Reversible for WordWord.rev
fn rev(self) -> WordOrdering
pub enum OrderingO(1). Three-way ordering result returned by cmp.
Ordering.Less
LessOrdering.Equal
EqualOrdering.Greater
GreaterSemiring
pub struct Semiring<A, M>(add: A, mulO(1). A semiring from two operation values: Semiring(min, +), Semiring(or, and).
add is a commutative monoid, mul a monoid that distributes over it; zero and one are
their identities. Matrix products (Mat(over:)), path algebras and convolve(over:) take
it. Semiring(+, *) is the default wherever one is accepted.
Op
pub trait Op<T>An associative operation, possibly without an identity (round 5). Bare operators
(+ * ^ | & min max gcd and or) implement it. Folds over an Op of an empty range
return None. Law (promised, sampled by stress): op(op(a, b), c) == op(a, op(b, c)).
Op.op
fn op(self, a: T, b: T) -> THasId
pub trait HasId<T>The identity of an operation. Law: op(id, a) == a == op(a, id).
HasId.id
fn id(self) -> THasInv
pub trait HasInv<T>The inverse of an operation. Law: op(a, inv(a)) == id.
HasInv.inv
fn inv(self, a: T) -> TCommutative
pub trait Commutative<T>Law: op(a, b) == op(b, a). Lets folds reorder and tags skip push-down.
Idempotent
pub trait Idempotent<T>Law: op(a, a) == a. Lets SparseTable overlap halves.
Selective
pub trait Selective<T>Law: op(a, b) is a or b. Lets sliding folds use a monotone deque.
AddAction
pub struct AddActionMarker type for the stock add action.
AssignAction
pub struct AssignActionMarker type for the stock assign action.
AffineAction
pub struct AffineActionMarker type for the stock affine action.
FlipAction
pub struct FlipActionMarker type for the stock flip action.
add
pub const add: AddAction = AddAction()Stock action: add a tag to every element. On + a span of n changes by f * n; on
min/max by f. Tags commute, so a SegTree with it never pushes down. O(1).
assign
pub const assign: AssignAction = AssignAction()Stock action: assign a tag to every element (?T tags, None is no-op). O(1) on +,
min, max; O(log n) folding f n times for other ops.
affine
pub const affine: AffineAction = AffineAction()Stock action: x -> a * x + b on + folds (span n: a * s + b * n). Not commutative.
flip
pub const flip: FlipAction = FlipAction()Stock action: swap the two halves of a Flip<T> value.