Skip to Content
ReferenceLibrary

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).

Source

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 == 0
  • Monoid<Int>.of(*).op(3, 4) == 12
  • Monoid<?Int>.of(min).id == None

Source

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: +,
)
  • id is the no-op tag (apply(id, x, len) == x).
  • compose(new_f, old_f) applies old_f first and then new_f.
  • apply(f, val, span) returns the folded value val of span covered leaves after applying f.

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: [...]).

Source

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) == 16
  • Action<Int, Int>(apply: (d, x, span) => x + d * span).compose(2, 5) == 7

Source

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

Source

Desc

pub struct Desc<T>(x

x with its order reversed. Build it with desc(x).

Source

Desc<T>

impl Ord for Desc<T>

Source

Desc<T>.lt

fn lt(a, b)

Source

Desc<T>

impl Show for Desc<T>

Source

Desc<T>.show

fn show(a)

Source

Reversible

pub trait Reversible

A 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.

Source

Reversible.rev

fn rev(self) -> Self

Source

MaxSub

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.

Source

MaxSub.empty

fn empty() -> MaxSub

The summary of no elements: the identity of join. It has no best subarray.

  • cost: O(1)
  • traps: never

Examples:

  • MaxSub.empty().try_best == None

Source

MaxSub.of

fn of(v: Int) -> MaxSub

The 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)

Source

MaxSub.join

fn join(a: MaxSub, b: MaxSub) -> MaxSub

The 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)

Source

MaxSub.scale

fn scale(self, k: Int) -> MaxSub

The 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)

Source

MaxSub.try_best

fn try_best(self) -> ?Int

The 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)

Source

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

Source

MaxSub

impl Add for MaxSub

Source

MaxSub.add

fn add(a, b)

Source

MaxSub

impl Mul<Int> for MaxSub

O(1). Scale every underlying value by k >= 0.

Source

MaxSub.mul

fn mul(self, k: Int) -> MaxSub

Source

MaxSub

impl Reversible for MaxSub

Source

MaxSub.rev

fn rev(self) -> MaxSub

Source

Semigroup

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).

Source

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.

Source

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) == -5
  • Group<Int>.of(^).inv(5) == 5

Source

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).

Source

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

Source

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 == 2
  • MinCount.join(MinCount(1, 3), MinCount(2, 5)).val == 1

Source

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

Source

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)).

Source

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

Source

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

Source

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

Source

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>).

Source

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

Source

Affine.eval

fn eval(self, x: T) -> T

a * x + b.

  • cost: O(1)
  • traps: never (overflow wraps in release, traps in debug)

Examples:

  • Affine(2, 3).eval(5) == 13

Source

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) == 11
  • Affine.then(Affine(1, 1), Affine(2, 0)).eval(5) == 12

Source

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

Source

Word

impl Reversible for Word

Source

Word.rev

fn rev(self) -> Word

Source

Ordering

pub enum Ordering

O(1). Three-way ordering result returned by cmp.

Source

Ordering.Less

Less

Source

Ordering.Equal

Equal

Source

Ordering.Greater

Greater

Source

Semiring

pub struct Semiring<A, M>(add: A, mul

O(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.

Source

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)).

Source

Op.op

fn op(self, a: T, b: T) -> T

Source

HasId

pub trait HasId<T>

The identity of an operation. Law: op(id, a) == a == op(a, id).

Source

HasId.id

fn id(self) -> T

Source

HasInv

pub trait HasInv<T>

The inverse of an operation. Law: op(a, inv(a)) == id.

Source

HasInv.inv

fn inv(self, a: T) -> T

Source

Commutative

pub trait Commutative<T>

Law: op(a, b) == op(b, a). Lets folds reorder and tags skip push-down.

Source

Idempotent

pub trait Idempotent<T>

Law: op(a, a) == a. Lets SparseTable overlap halves.

Source

Selective

pub trait Selective<T>

Law: op(a, b) is a or b. Lets sliding folds use a monotone deque.

Source

AddAction

pub struct AddAction

Marker type for the stock add action.

Source

AssignAction

pub struct AssignAction

Marker type for the stock assign action.

Source

AffineAction

pub struct AffineAction

Marker type for the stock affine action.

Source

FlipAction

pub struct FlipAction

Marker type for the stock flip action.

Source

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).

Source

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.

Source

affine

pub const affine: AffineAction = AffineAction()

Stock action: x -> a * x + b on + folds (span n: a * s + b * n). Not commutative.

Source

flip

pub const flip: FlipAction = FlipAction()

Stock action: swap the two halves of a Flip<T> value.

Source

On this page