Statistics and Maps

Statistics and maps live on their collection

Status: current. CombinatorialStat and CombinatorialMap are built: the carrier and operation tables are in packages/structures, the permutation, partition, Dyck path and set partition statistics and the maps in packages/symbols/combinatorics/combinatorics. What is still open is under "Open".

A statistic or a map is not a global head per name. It is an entry in its carrier's table, reached through one of two heads. A name chosen for what it measures runs out of good names long before the catalogue runs out of statistics, so the head carries the operation's name as an argument. Companion to Namespaces (the resolver and context ladder) and Structures (carriers as nominal types, held constructors, restrictions as sets, not subtypes).

The proposal to describe statistics as fields of a collection, not as operations over its elements, is Speculative-Statistics-as-Fields.

The design

• Carriers are nominal compute-engine types. Permutation is minted over list<integer>; a held constructor (AsPermutation, a signature with no evaluate handler) keeps a value's type through evaluation. Typed dispatch costs a few microseconds per call and minting types a few milliseconds at boot; neither is a reason to avoid typing.
• A statistic is data: { head, on, expr, summary, … }, where expr is a MathJSON tree over a wildcard and is the implementation. A fast TypeScript kernel is only the preferred implementation of the same statistic, and the expression is its reference; the two for one (carrier, name) are one table entry.
• The tables are @enumeratio/structures' (registerCarrier, registerOperation, registerCollectionCarrier), a leaf that collections, statistics and the maps can all reach. CombinatorialStat(x, name) and CombinatorialMap(x, name) find x's carrier from its type, as protocol dispatch does, then the operation by name or FindStat id.
• Over a collection (SymmetricGroup(4), Derangements(4), a plural) they map over its elements lazily, so Tally(CombinatorialStat(SymmetricGroup(4), "Inversions")) is the Mahonian numbers. The result is a collection, not a function: compute-engine's Map takes only a literal Function. CombinatorialStat(C, "Count") is Count(C).
• Dispatch stays in our table. A value's carrier is found by its constructor first, then by type with each carrier's parsed type cached. Dispatching through compute-engine's protocol solver measured about 8 times slower than the table. Hot per-element callers (collection tables, Filter scans, Plausible) call the statistic's head directly, which costs a little less than going through CombinatorialStat.
• Statistics that stay heads. Very general statistics (Count, Rank) remain heads of their own and are reachable through CombinatorialStat too; a name compute-engine or Wolfram already uses for the same meaning may keep a global head. A statistic's bare head is declared where the name is free.
• No silent skip on a taken name. A taken name is allowed only when the table holds another package's kernel for that very statistic, or when compute-engine owns the name (Sign: a permutation's sign is a coherent generalization of a number's, so its head takes the carrier as one more argument). Anything else is a StatisticCollisionError naming every signature. The same part twice in a table is an OperationCollisionError. A restriction says which package implements it (implementedBy: "collections"); any other taken name is a RestrictionCollisionError.
• Maps name from and to carrier types, a body, an optional guard, and a composedOf chain that type-checks step by step. A map on a restricted collection stays guarded, not re-typed: it declines (stays symbolic) outside its set, because restrictions are sets, not subtypes. Reverse, Complement and Inverse extend compute-engine's own heads for permutations (extend.ts) without losing any original overload.
• The record names its carrier. A statistic or map is a record in the reference folder of the package that defines it (reference/<Head>/index.md, with examples.tsv); statOn and mapOn list the carriers it is defined on, and a carrier's own record has catalogCarrier and a glyph. packages/frontend/tests/stat-on.test.ts holds every statOn claim to an answer on its carrier.
• FindStat ids are another name for a statistic, matched by value: enumerate every object of a carrier up to a size FindStat's finder accepts, evaluate our definition, keep the FindStat statistics that agree on every value. An id resolves to a table entry like a name. Several of our names can be one FindStat statistic (LargestCycleLength and LongestCycleLength); an id resolves to the first. Only the id is lifted from FindStat, not its Sage implementation or known-value tables.

Equivalent carriers

A converter pair with an { inverse } law makes two carriers equivalent (registerEquivalence), and a statistic or map one carrier lacks is transported from the nearest carrier that has it, through the chain of bijections. Each is defined once, on whichever carrier states it most naturally, and which carrier is the storage matters much less.

A conversion is not a head of its own: it is an overload of the target's constructor, chosen by the argument's type (SetPartition(RestrictedGrowthString([0, 1, 0, 2]))), also reached as CombinatorialMap(x, SetPartitions) or by FindStat id. The pairs are set partitions (blocks) and restricted growth strings; set compositions (blocks) and surjections; binary trees (nested), their in-order parent arrays and Dyck paths; and a composition of n with its cut word, a binary word of length n - 1.

Every map is defined in Epsil, the nested ones by recursion: a function handed itself as an argument, so a body stays one closed expression. There is no hand-written kernel as input: a hand kernel is a black box an optimizer cannot compile, fuse or simplify through, so a compiled form, where one is needed, is the optimizer's output from the Epsil. A test checks the recursive definitions against an independent TypeScript reading.

Orders

A carrier has no order; a collection is a carrier with a total order, and sibling collections exist for distinct useful orders. Where a conversion happens to match two collections' orders it says so (orderIsomorphism), and a test checks it: set partitions and growth strings, compositions and cut words, binary trees and parent arrays. The map between binary trees and Dyck paths is a bijection but not order-preserving. See Speculative-Options-Restrictions-and-Orders for the vocabulary.

Open

• Retiring the bare heads. The statistics that are bare heads today (Inversions, Descents, and so on) keep working. Retiring one would mean register, deprecate with a pointer to CombinatorialStat(π, "Inversions"), then stop declaring it, at the cost that an old notebook's Inversions(p) errors. Combinatorica has Inversions but no Descents, Ascents or MajorIndex (Combinatorica-Audit); promoting a bare head only where compute-engine or current Wolfram has the identical spelling and meaning is the criterion for exceptions.
• Definitions beside their collection. A definition should live next to the collection it is on, following Plausible's walk from family to carrier to the maps and statistics declared on it, with its examples as real examples (Examples as Data). Today the collections package files the permutation kernels and the statistics are filed by carrier.
• Rank through CombinatorialStat, and the catalogued statistics and maps that have no implementation yet. An entry with no kernel just has no implementation row, so no separate design is needed for them.
• Typed collections. Families type their elements as bare list<integer>; typing them by their element carrier (indexed_collection<permutation>) would let CombinatorialStat(SymmetricGroup(4), name) be checked at boxing through a constrained collection<T> signature, at the cost that every consumer then sees carrier values. Compute-engine has parameterized nominal types and protocol constraints; what it lacks is a type variable in a length (list<integer^N>), which permutation<N> needs and which is an upstream ask. Carriers parameterized by what they are made of (word<T>, set_partition<T>, the species picture) are expressible now and wait for a case.
• Subtypes. Minted types do not subtype (Derangement ⊂ Permutation), which is why restrictions are sets with a runtime guard. A subtype lattice upstream would let a collection-scoped map drop its guard.
• Reverse, Complement, Inverse. Whether the permutation arm stays spliced onto compute-engine's heads or moves behind CombinatorialMap(π, "Reverse") like every other map.
• Merging a multi-carrier name. Whether "same name, dispatch by type" needs a differential check before two carriers share an entry: a sweep once matched a "peaks" that was FindStat's inner peaks.
• A FindStat id on its own, callable without knowing our name for it, or only a lookup key.
• The spelling of the resolver's own names (Namespaces), which a deprecation-period alias would need.

The design as first written, with the section numbers that source comments cite, is Statistics and Maps Design.