Archive Survey Rust Traits and Number Libraries

Survey — Rust traits + number-theory libraries

Carried over from the earlier enumeratio. The trait-composition half feeds the same ground Structures now covers; the number-theory library half (the num crates, p-adic prior art) is still relevant background for @enumeratio/number-theory and the residues package, neither of which existed when this was written.

One of the ecosystem surveys feeding the trait/category model. Prior art for base_trait / base_category (backlog #8's enumeration-capability traits) and for the p-adic side of the number-gradings carrier. Verdict up front: enumeratio's HAS/IS split is already the right shape — this survey sharpens which mechanism each half should copy, and flags where the current all-marker base_trait layer leaves value on the table. Steal/avoid table at the bottom.

1. Rust's trait system as a capability model

Rust has no inheritance — no struct extends another, no object is-a anything. The only way one type shares an interface with another is by both implementing the same trait. So the whole capability vocabulary lives in traits, and the language gives a handful of orthogonal knobs for composing them. The num crates exercise every one, which is why they're the reference.

Mechanism	What it is	What it buys you
Supertrait	trait B: A {} — B requires A.	Capability composition. PrimInt: Num + NumCast + Bounded + BitAnd + … + Saturating builds a rich capability by naming ~17 simpler ones, not by restating them.
Blanket impl	impl<T: A + B> C for T {} — every type meeting the bound gets C for free.	Capability derivation. A type that already has the primitive pieces acquires the composite with zero per-type wiring.
Associated type	type Err; inside a trait — one binding per implementing type.	A companion type fixed by the impl. Num::FromStrRadixErr — one error type per numeric type.
Generic param on a trait	trait Pow<RHS> { … } — many impls per type.	The same type implements the trait several ways. Pow<u8>, Pow<u32>, Pow<&u8> all on one type; associated types can't do this.
Associated const	const ZERO: Self;	Static data attached to a capability, resolved at compile time — not a method call. ConstZero::ZERO.
Marker trait	trait Unsigned: Num {} — empty body.	A compile-time tag. Carries no behavior; exists so generic code can write T: Unsigned to exclude Signed.
Bound / where	fn f<T: Num + Copy>(…)	The capability requirement at the use site — an algorithm names the traits it needs and works over any representation supplying them.

Two structural facts shape everything downstream:

• The orphan rule / coherence. You may implement a trait for a type only if you own the trait or the type. So num-traits cannot add inherent methods to i64 (a foreign type) — it defines a trait and impls it for the primitives inside the crate that owns the trait. Downstream crates (num-bigint, and user code) impl the same traits for their own types. The trait is the only extension point the orphan rule leaves open for "add capability X to a type someone else defined." This is why the numeric ecosystem is trait-heavy rather than wrapper-heavy.

• Blanket vs. macro. A true blanket impl works only when the composite behavior is derivable from the pieces. NumOps (all five arithmetic ops) is a genuine impl<T> NumOps for T where T: Add + Sub + … — free for anyone with the std ops. But Pow and NumCast can't be blanket-impl'd (the actual pow/cast body differs per type), so the crate fakes coverage with a macro_rules! that stamps out one monomorphic impl per type. Lesson: derive when the capability follows structurally; enumerate when it doesn't. (Directly relevant — enumeratio's derived-vs-declared trait question below is the same fork.)

2. The num / num-traits numeric tower

The vocabulary is a supertrait lattice rooted at the two identities, and it is scrupulous about keeping capability (the trait) separate from representation (the concrete type).

Zero  One            (identity: zero()/one(), is_zero()/is_one())
  \   /
   Num               (+ NumOps; assoc type FromStrRadixErr, from_str_radix)  ← the only stateful root
  /  |  \
Signed Unsigned  Integer(: Num + Ord)      ← num-integer: gcd/lcm/div_rem/is_multiple_of/is_even…
         |          \
      PrimInt        Roots(: Integer)       ← sqrt/cbrt/nth_root split OUT, not bloated into Integer
   (bundles ~17:      \
    Num+NumCast+        (num-bigint BigInt/BigUint impl the whole stack)
    Bounded+bitops+
    Checked*+Saturating)
Float / Real / FloatCore  (Num + NumCast + Neg + PartialOrd + Copy; differ by method-set, not bounds)

Observations worth stealing:

• Marker-ish traits carry the composition, capability traits carry the methods. NumOps, NumRef, NumAssign, Unsigned have zero methods of their own — they exist purely to name a bound-bundle once so it can be reused as a supertrait. Num, Integer, PrimInt, Signed, Float carry the real method surface. The layer cake is deliberate: bundles name the shape, capabilities supply the behavior.

• Ratio<T> is the model of representation-over-capability. num-rational's Ratio<T> isn't hard-wired to i64; nearly every impl is conditional — impl<T: Clone + Integer> Zero for Ratio<T>. The rational representation inherits its whole Num-family membership by requiring its component T to already be Integer. Swap i64 for BigInt and Ratio<BigInt> still works, no algorithm change. This is the payoff of the split: write the algorithm against the trait, pick the representation later.

• Bounded's // FIXME: should be associated constants is a live confession: min_value()/max_value() are methods only because const-trait-fns weren't mature when it was written. When a capability's value is static per type, model it as an associated const, not a method (ConstZero::ZERO is the modern form). We'll want this for the enumeration cost tags.

• Split the capability, don't bloat the trait. Root extraction is Roots: Integer, a separate trait — not extra methods on Integer. A type gets roots only if it opts in.

3. The adic crate — p-adic numbers (docs.rs/adic)

A mature p-adic library (polynomials, power series, Hensel-lifting root-finding). Its design is dominated by one constraint that rhymes exactly with enumeratio's: the prime p is a runtime value, not a type parameter.

• Prime-as-data breaks the no-arg factory. You can't build a p-adic zero without knowing which prime, but num_traits::Zero::zero() takes no arguments. So adic can't sit on Zero/One/Num directly. It splits the identity into two honest paths:

  • AdicPrimitive::zero<P: Into<Prime>>(p) -> Self — the prime-parameterized static constructor.
  • LocalZero::local_zero(&self) -> Self — a zero relative to an existing instance (which already carries its p).

  LocalZero/LocalOne are blanket-impl'd for any num_traits::Zero/One — an adapter over the num tower, not a rejection of it. Prime itself is a validating newtype (struct Prime(…)), not a bare u64.

• Capability is a small orthogonal ladder, not a monolith. HasDigits → CanTruncate / CanApproximate → Normed / UltraNormed → AdicPrimitive / AdicInteger. AdicInteger is a named bound-bundle alias (AdicPrimitive + UltraNormed<Unit=Self> + CanTruncate<…> + CanApproximate<Approximation=ZAdic> + …) — a capability set with no data of its own, exactly the NumOps/Unsigned pattern.

• Representation splits on the guarantee. Not one generic Padic<P> but a family of concrete structs, each opting into only the traits it can honestly satisfy: UAdic (exact unsigned), EAdic (exact signed), ZAdic (approximate, carries a runtime certainty counter), QAdic<A> (fractional, generic over the backing integer type), PowAdic/MAdic (prime-power / composite modulus). Exact types "downgrade" into the approximate world via CanApproximate::Approximation = ZAdic — a typed, honest lossy conversion.

• The valuation of zero is a first-class sentinel. enum Valuation<F> { PosInf, Finite(F) } — PosInf is v_p(0) = ∞, not a null or a magic number. norm() returns an exact Ratio (p^-v), no float rounding.

• Precision is runtime, and reading past it is fallible. HasDigits::digit(n) -> AdicResult<u32> (the coefficient of pⁿ), digits() an iterator from min_index(); asking past the known frontier is an error, not a guess. There is no compile-time precision bound anywhere — ZAdic carries a certainty counter; exact types carry none.

Other Rust p-adic crates are toys or narrow by comparison (padic early/unstable; acid2 2-adic floats only; adic-shape is rendering). adic is the one to mine.

4. The clean vocabulary: CAPABILITY vs REPRESENTATION

Both libraries converge on the same separation, and it's the answer to the spike's core question:

• A capability is a trait — what you can do (list, count, unrank, valuate, take gcd). Named once, composed by supertraits, derived by blanket impls where structure permits, tagged with static data by associated consts.
• A representation is a concrete type — how the object is stored (i64, BigInt, Ratio<T>, UAdic vs ZAdic; for us: int[], text, a composite carrier). A representation opts into exactly the capabilities it can honestly satisfy — and a lossy or partial one (ZAdic, a scan-only collection) says so by not implementing the stronger trait, or by making the operation fallible.

The discipline that makes this pay: never bake identity-fixing parameters into the type when they're runtime data. adic refuses a const-generic prime; Ratio<T> refuses a hard-coded component. Capabilities are generic; the data rides on the instance.

5. Mapping onto enumeratio

5.1 base_trait ≈ the Rust supertrait graph

Already built this way — realizer.sql literally calls implies "like Rust supertraits." base_trait(id, title, description, implies text[]) with transitive closure over implies is the supertrait lattice; base_collection_trait derives membership from the registries then closes it.

What the survey adds:

• The derivation is already a blanket impl, and that's a strength. has_stats is granted to any collection with a base_stat row; has_glyph to any whose carrier joins base_glyph. That's precisely impl<T: Add+Sub+…> NumOps for T — capability follows structurally, no per-collection declaration. Keep leaning on derivation; hand-declare a trait only when it doesn't follow structurally (the macro case).
• Today every trait is a bare marker. finite, graded, has_stats, visual carry no data — fine for filter/group. But the num-traits lesson (Bounded's FIXME; ConstZero::ZERO) is that a capability with a static value should carry it. That's exactly what backlog #8 needs (next section) — the first traits that should stop being markers.

5.2 base_category ≈ the IS-a hierarchy Rust deliberately lacks

The HAS/IS split is well-founded, and Rust confirms the trait side should not be the hierarchical one:

• base_trait = Rust traits — capabilities a collection HAS; a flat implies-lattice, not an inheritance tree.
• base_category = Sage categories — what a collection IS; hierarchical (parents), with requires naming the traits the classification entails (its axioms: mathematical requires immutable).

Rust has no IS-a mechanism at all, so it's correct that base_category is modeled on Sage, not Rust. One subtlety to name: Rust supertraits go trait → trait (a capability requires another capability); enumeratio's requires goes category → trait (a classification grants capabilities). That grant-by-axiom is the Sage pattern, and it's fine — but note it's declarative, whereas the base_collection_trait derivation is structural (blanket-impl-like). Both coexist today; keep the structural path primary and reserve requires for genuine axioms.

5.3 Enumeration-capability traits (backlog #8) — where markers stop being enough

This is the payoff. Backlog #8 wants traits declaring each collection's enumeration capability — unrankable / better-than-table-scan random access, with an asymptotic cost or size heuristic — so the sampler can tell an O(1)-ish unrank from a scan-only collection. Map it straight onto the two libraries:

• Model it as adic's orthogonal ladder, not one flag. A small supertrait chain, each rung a real capability:
  • enumerable — can list a fiber in global order (the hand-authored floor; every collection has it).
  • countable — has a closed-form cardinality accel (not a floor count).
  • unrankable — has a native unrank engine giving random access. This is the PrimInt-of-the-set: the rich rung that enables random_element the way PrimInt enables bit-twiddling. random_element is a blanket capability over countable + unrankable, transportable across a bijection (ties to maps-and-bijections increment 5).
  • Each rung carries a cost tag as associated-const-style data — scan | linear | logarithmic | constant — not a method. This is the direct application of Bounded's FIXME: the heuristic is static per collection, so it's data on the trait row, not a function to call.
• Derive it, à la has_stats. A collection gets unrankable iff it has a native unrank engine — read from the same registries, not hand-declared. The scan-only collections (abundant_numbers, catalan_numbers, motzkin_numbers — whose floors literally "scan the monotonic floor") then land as enumerable but not unrankable, automatically. The trait split makes scan-only-vs-random-access first-class data the sampler reads, with no per-collection bookkeeping.
• Honesty is the invariant (adic's ZAdic lesson). A representation opts into only what it can satisfy. A scan-only collection must not claim unrankable; the infinite/unknown-count sampler must be fallible (sample a bounded prefix, or refuse) — the same contract as HasDigits::digit(n) erroring past the known frontier. Absent trait = honest absence, never a lie of convenience.

5.4 p-adic modeling ↔ the prime-exponent-vector carrier

adic is the reference implementation for the p-adic ideas parked in number-gradings. Three concrete transfers:

• v_p(0) = ⊥ should be an explicit sentinel, not NULL. number-gradings floated encoding 0 as a NULL/absent exponent vector. adic's Valuation::PosInf says the cleaner move is a first-class ∞-everywhere value — a tagged variant, not an overloaded null. When the p-adic carrier is promoted, give the "zero / infinite valuation" case its own inhabitant of the type rather than reusing NULL (which SQL will conflate with unknown).
• Our carrier is the adelic transpose of adic's digit vector. adic indexes digits by power-of-p position within one prime; our v = (v₂, v₃, v₅, …) indexes by prime rank, one exponent per prime — the global product-of-places view of the same information. Ω = Σvᵢ and ω = |support| are our norm-ish reads; adic's UltraNormed::valuation() is the single-place analog. Complementary, not competing — but adic's HasDigits interface (indexable + iterable coefficients, fallible past the frontier) is the right shape for a prime_rank-indexed accessor if/when the vector becomes a first-class bit-register carrier (backlog item 6).
• Prime-as-runtime-value validates the data-parameterized design. adic refuses a const-generic prime because p is runtime state; enumeratio already carries collection/axis parameters as data (the handle/fiber), never baked into a static type — which is why a num-traits-style no-arg zero()/one() factory would fail for us the same way it fails adic. The constructor-takes-args discipline is the correct analog; this survey is external confirmation of it. adic's runtime certainty counter is likewise the model for the bounded-prefix behavior over infinite collections (backlog #8).

Status caveat. The prime_rank_vector p-adic projection is currently dropped in the live architecture (it depended on prime_rank()/prime_exponents(), which this architecture doesn't have — see integer_factorizations.sql). So §5.4 is guidance for when the vector is promoted (backlog item 6), not a refactor of live code.

• Avoid adic's struct sprawl. adic mints six concrete types (UAdic/EAdic/ZAdic/QAdic/PowAdic/MAdic) — one per guarantee. For us that would be six carriers. Our restriction + order-iso-borrowing machinery already gets the same coverage from one carrier + sibling collections (square_free ≅ subsets, k-power ≅ square_free). Mint a base_restrict or a borrowed order, not a new carrier, for each variant.

6. Steal / avoid

Steal

• implies-closure = supertrait lattice — already in place; keep deriving membership structurally (has_stats is a blanket impl). Hand-declare only when the capability doesn't follow from the registries.
• HAS (base_trait) vs IS (base_category) — the split is right; Rust confirms the capability side must stay a flat lattice and the IS-a hierarchy belongs to the Sage-style category, not the trait.
• Associated-const cost tags (Bounded FIXME / ConstZero) — carry the backlog-#8 asymptotic heuristic as data on the trait row, not a method.
• Orthogonal capability ladder (adic HasDigits→…→AdicInteger) for enumeration: enumerable ⊂ countable ⊂ unrankable, each a real rung, random_element a blanket over the top rungs.
• Honest opt-in + fallibility (adic ZAdic, HasDigits::digit) — scan-only collections simply lack unrankable; infinite-collection sampling is fallible (bounded prefix or refuse).
• Valuation::PosInf sentinel — model v_p(0) = ∞ as a first-class value, not NULL, in any promoted p-adic carrier.
• Prime/params as runtime data, never in the type — adic and Ratio<T> both refuse to bake identity into the type; matches (and vindicates) enumeratio's data-driven handles/fibers.
• Named bound-bundle aliases (AdicInteger, NumOps) — a trait that's purely a capability set is a legitimate, useful row (a visual-style umbrella), distinct from a data-carrying capability.

Avoid

• Don't leave the enumeration traits as bare markers — the whole point of #8 is the cost data; a flag alone can't drive the sampler's O(1)-vs-scan decision.
• Don't mint a carrier per guarantee (adic's six-struct family) — use base_restrict + order-iso borrowing; one carrier, many sibling collections.
• Don't push IS-a into base_trait — hierarchy/axioms are base_category's job; the trait layer stays a flat implies-lattice.
• Don't overload NULL for a real value — SQL will conflate ⊥/∞ with unknown; use an explicit inhabitant.
• Don't import Sage's axiom-heaviness wholesale — Rust's structural derivation (blanket impls) is lighter than Sage's declarative axiom-grants and already fits our data-driven registries; keep requires for genuine axioms only.