Repository navigation
Speculative Named Restrictions
Speculative. A proposal, not adopted.
A restriction of a collection by a predicate is sometimes a collection the catalogue already names and has a fast kernel for: the permutations of n with no fixed point are Derangements(n). Today a user who writes Restricted(SymmetricGroup(n), …) gets a lazy filter of the base, enumerative and slow, even where a kernel would answer in the same order. The reverse reading is half built: a table says what each named restriction is a restriction of. This page designs the join: how a restricted expression is recognized as a named collection, and where the facts it needs are kept (Restrictions).
"Measured" below means read from the tree at origin/main or counted there, with a path:line. "Assumed" means reasoned, not run: no code was run for this page, and nothing was probed through compute-engine. In paths, combinatorics/ is packages/symbols/combinatorics/combinatorics/.
The alias is a row of data on the named collection's record, matched exactly: Restricted(base, predicate) resolves to the named collection only when its base is the row's base and its predicate is the row's predicate (option (c) below, with parameter holes). Any other predicate, equivalent or not, stays the lazy filter it is now. That failure mode is slow, never wrong.
-
The row is a
restrictskey in the record's front matter: the base call and the predicate, both written in Epsil over the head's own parameters and_x. It replaces theRESTRICTIONStable in@notatio/structures, which today holds the same facts for 19 heads in TypeScript, one size parameter only. -
Resolution happens when
Restrictedevaluates, as the headRestrictedalready does by delegating toFilter. The input expression is left as typed; its value isDerangements(5). - Order needs no new rule: Restrictions already says a restriction head means the base's induced order. A row is a claim of that, and the existing differential test holds it, element by element, on small parameters. A collection in another order is not a row; it is a sibling with its own name (the measured siblings are in "What exists").
- Not (a), (b) or (d). (a) is a special case of (c) with no benefit once holes exist; (b) buys equivalence reasoning no one has asked for and cannot fail safely if it is wrong; (d) as literally stated puts an O(n!) filter where the family format wants count, unrank, rank and valid (§1).
The first slice is four permutation rows, all with a statistic as the predicate (§6).
Restricted exists, and is Filter. declareRestricted declares Restricted(collection, function) -> collection and evaluates it as Filter(base, predicate), so the base stays lazy (packages/structures/src/restriction.ts:267-276; its record is combinatorics/reference/Restricted/index.md:1-8). It never looks at what the base or predicate is. The Wolfram-style Select is not a separate head here; Filter is compute-engine's.
A table of named restrictions exists, and runs the other way. RESTRICTIONS is readonly Restriction[], each row a name, a base head, a carrier type on, a predicate over _x (and _raw, the carrier's contents), a summary and optionally implementedBy: "collections" (restriction.ts:26-41, rows at :43-244). Measured: 19 rows, 18 with implementedBy.
| Base | Rows | Predicate |
|---|---|---|
SymmetricGroup |
Derangements, CyclicPermutations
|
FixedPoints(_x) = 0, CycleCount(_x) = 1
|
IntegerPartitions |
DistinctPartitions, SelfConjugatePartitions, OddPartitions, PrimePartitions, SquarePartitions, TriangularPartitions
|
a statistic (DistinctParts, IsSelfConjugate) or All(_raw, part test)
|
IntegerCompositions |
Odd, Proper, Dyadic, Fibonacci, Tri, Tetra, Triangular, Prime, Carlitz, Palindromic, Zigzag Compositions
|
All(_raw, …), sliding windows Partition(_raw, k, 1), or _raw = Reverse(_raw)
|
2 + 6 + 11 = 19. SelfConjugatePartitions is the one row with no kernel: its record is a stub (combinatorics/reference/SelfConjugatePartitions/index.md, stub: carrier), and declareRestrictions declares it as a filter of its base (restriction.ts:305-327).
What declareRestrictions does with a row. If a collection of that name is already declared (the fast one), it skips: the kernel answers and the row is only its specification; if the name is taken and the row has no implementedBy, it is a RestrictionCollisionError (restriction.ts:301-304, :330, :333-341). The census declares Restricted and the table after combinatorics (packages/census/src/engine.ts:73-80). So the table never resolves a Restricted(…) expression; it only supplies names.
The tests. combinatorics/tests/statistics-carrier-restriction.test.ts builds Restricted(base(n), Function(predicate, _e)) for each row (:32-36) and requires the named collection to match it in count and in every member in order, for n = 0..5 (:79-93), n = 0..8 for the compositions and partitions (:109-144). It also requires each row's base and carrier to exist (:146-154) and a collision to be an error (:156-159). This is the test an alias row needs; it exists and covers 18 rows.
Many named restrictions are not rows. The permutation families built by permutationRestriction (combinatorics/collections/src/families/lex-restriction.ts:91) are restrictions of lex-ordered SymmetricGroup by completion counts (:1-8). Measured by counting call sites: Derangements, Involutions, CyclicPermutations, KCyclePermutations (combinatorics/permutations/src/families/core.ts:251,272,318,372); AlternatingPermutations, ConnectedPermutations, KDescentPermutations, KInversionPermutations, AdjacentTranspositionInvolutions, BooleanPermutations, NonCrossingPermutations, SeparablePermutations, NonCrossingCycleSupportPermutations, VexillaryPermutations (combinatorics/permutations/src/families/restrictions.ts, calls at :139,194,285,331,363,414,531,850,1092,1206), the two Grassmannians (:1421-1422) and the six PermutationsAvoiding… (one call, :654, six names per Restrictions §3): 22 in all, of which 2 are in the table. A family may state its membership predicate in Epsil (lex-restriction.ts:42); Involutions and KCyclePermutations do (core.ts:272-300, :372-380). Also restrictions of their base, outside the table: EvenPermutations (a closed-form family whose reading filters the lex list, combinatorics/permutations/tests/epsil-families.test.ts:263), BaxterPermutations, SimplePermutations, SmoothPermutations (filtering, combinatorics/permutations/src/families/permutation-classes.ts:193-220), the subset restrictions EvenSubsets, OddSubsets, SubsetsOfSizeAtMost, SubsetsWithoutConsecutive ("the order of the subsets it restricts", combinatorics/collections/src/families/subsets.ts:1-3), and PartitionsMaxPart, LargestPartPartitions, PartitionsIntoKParts (read as filters of the partition list in combinatorics/partitions/tests/epsil-families.test.ts:126-136; partsInSet states the order, combinatorics/partitions/src/families/partitions.ts:50).
Two parameters are out of the table by construction. The table's rows are (integer) -> collection; the file says PartSizeBoundedCompositions, PartCountBoundedCompositions and LargestPartPartitions are skipped because k does not fit (restriction.ts:197-198, :200-202). KCyclePermutations(n, k) is SymmetricGroup(n) restricted by CycleCount = k (Restrictions §1) and is not a row.
Siblings, not in the base's order. Measured from records and code:
-
PermutationsAsCycles: "the same permutations asSymmetricGroup, in another order", by cycle type, and over another carrier,CycleDecomposition(combinatorics/reference/PermutationsAsCycles/index.md:24). Not a restriction ofSymmetricGroup. -
LehmerCodes,SubexcedantSeqs: other carriers with an implied order (Speculative-Options-Restrictions-and-Orders §4).Arrangements/KPermutations,SignedPermutations: a different set, not a subset. -
SetPartitionsborrowsRestrictedGrowthStrings' order through a bijection, and compositions in cut-word order areBinaryWordsthroughComposition(Restrictions §4): conversions, not restrictions.
Measured: no row in the table, and none of the 22 families above, is recorded as being in an order other than its base's, and the 18-row test passes by construction. What I did not measure is the order of the permutation families that have no row and no test against a filter (the last bullet of "Measured versus assumed").
How a record states "restricts" today: it does not. Derangements' front matter has seeAlso: [SymmetricGroup, Involutions, Subfactorial] and a prose summary, no base and no predicate (combinatorics/reference/Derangements/index.md:1-30); Involutions and AlternatingPermutations are the same shape. The record schema is closed (additionalProperties: false, packages/entry/src/schema.ts:348) and has a carrier key (:334), so a new key needs a schema and a type change (packages/entry/src/types.ts:442 is the neighbouring field).
Carrier has restricts and predicate, and nothing sets them. Carrier.restricts?: string and Carrier.predicate?: string (packages/structures/src/carriers.ts:51-57) record "the carrier this one restricts" as data. Measured: no assignment or read of either anywhere in structures, manifest, census, engine, entry or the combinatorics area. They belong to the subtype idea that restriction.ts:3-7 rejects: a restriction keeps its carrier. They are not this design's data.
The manifest resolves heads as data. A SymbolInfo carries overloads, params, a package and optional fields (packages/manifest/src/types.ts:43-60); an overload's conditions (on, unless, symbols, types) are read before any package loads (Manifest, "Overloads"). There is no field for a restriction.
| Match key | Covers | Cost | Failure mode | |
|---|---|---|---|---|
| (a) named predicate head | (base head, predicate head) | only predicates that are heads: none exist as heads today (no IsDerangement head; those names are kernel helpers) |
a head per predicate, in a namespace that is already crowded | a restriction by a bare statistic comparison does not match |
| (b) structural, after canonicalization | the predicate's canonical form | any predicate written the way the table writes it | relies on compute-engine's canonical order of Equal, And, Function bodies being stable and complete; a fresh-engine probe is needed (Speculative-Posets §1 is the precedent) |
equivalent predicates miss (slow); a canonicalization quirk that equates two different predicates is silently wrong |
| (c) table of named predicates, exact | (base, predicate) up to bound-variable renaming, with parameter holes | statistic comparisons, All over parts, parameterised rows |
a first-order matcher; the rows | a near miss falls through to Filter: slow, correct |
| (d) the named collection expands to its restriction | none (one direction only) | all | the family format wants count, unrank, rank and valid; Filter gives enumeration |
resolves nothing; the user's Restricted stays a filter |
(a) needs a predicate to be a head. The table's predicates are statistic comparisons (FixedPoints(_x) = 0) or folds over _raw; none is a named head. Naming one per row doubles the vocabulary (IsDerangement beside Derangements) to buy what the comparison already says. A sound variant keys on (statistic head, relation, value), which is (c) restricted to one shape; it cannot reach the 17 list-carrier rows.
(b) is the most general and the only one whose wrong answer is silent. The predicate would be matched as a canonical expression, so FixedPoints(p) = 0, 0 = FixedPoints(p) and Not(FixedPoints(p) > 0) would hope to meet. Whether canonicalization makes the first two one expression is assumed; the third is a theorem, not a normal form. A miss costs speed; a false hit costs an answer, which AGENTS.md's "decline rather than answer wrong" stance rules out for a first step. Nothing here needs it.
(c) is the smallest thing that serves the case. The row stores the predicate once, with the head's parameters as holes (§4). Restricted(B, Function(body, v)) matches when B is a call of the row's base head and body with v read as _x equals the row's predicate, binding holes. It is a one-way, first-order match with no search: it descends two trees in step. Whether the engine's pattern-matching can do this, or the matcher is a small function over MathJSON, is assumed; the second is enough.
(d) read literally makes Derangements(n) mean Restricted(SymmetricGroup(n), FixedPoints(_x) = 0) and the kernel its fast path. The rule is "a family's Epsil definition is its meaning; a hand-written TypeScript kernel is only its optional fast path" (AGENTS.md, Code; combinatorics/collections/src/families/epsil.ts:94-98). The completion-count families already satisfy it: Derangements is an Epsil definition (core.ts:318-352), compiled, with no TypeScript kernel, and a family's Epsil is count, unrank, rank and valid. A filter has none of those without enumerating, so it cannot be the family's definition. The rule is better served by a second reading of the same meaning: the predicate in the record is the specification; the family's Epsil valid (or predicate, lex-restriction.ts:42) is checked against it; the family is held to the filter, element by element, which is what the existing test does (statistics-carrier-restriction.test.ts:79-93). (d) is the direction declareRestrictions already takes for the one row without a kernel (restriction.ts:305-327), and stays so.
So the data of (c) is (d)'s specification, and (c)'s matcher is the only new code. Best fit with the rule: (c), with the record's predicate as the family's specification.
| Home | For | Against |
|---|---|---|
Record front matter (restricts key), built into the manifest |
one place per collection with its summary, signature and parameter names; installed libraries bring their own rows (AGENTS.md: "A library may be in the tree or installed"); the page reads it; layering is clean |
schema and type change; the matcher needs the rows loaded when a Restricted expression is evaluated |
The family declaration (FamilyShape) |
next to the Epsil that the row is checked against |
FamilyShape has no base; families are TypeScript; the manifest would have to be rebuilt from code |
A separate file (today's restriction.ts) |
exists | a TypeScript table in @notatio/structures names heads of combinatorics by string; a library outside the tree cannot add a row; two statements of what a collection is |
Recommended: the record. The manifest is the repository's home for facts about heads as data, and the record is the source (Manifest.md: "the record is the source and the code must agree with it, which the drift test enforces"). The table is then derived: built from the records, never committed (AGENTS.md, "Data derived from our own code is built"), and RESTRICTIONS goes. A restricts field belongs on SymbolInfo (manifest/src/types.ts:43) so the resolver can read a row without loading the library, in the way an overload's on is read.
Proposed shape (not existing):
restricts:
base: SymmetricGroup(n)
predicate: FixedPoints(_x) = 0and for a parameter,
# KCyclePermutations(n, k)
restricts:
base: SymmetricGroup(n)
predicate: CycleCount(_x) = kWhat a test holds, for every row: the named collection equals Restricted(base, predicate) evaluated as a filter, in order, on a small grid of the head's parameters. This is statistics-carrier-restriction.test.ts:79-93 fed from the records instead of RESTRICTIONS, with its grid taken from the row's parameters (a row with k runs k = 0..n+1). Two tests are new: the matcher resolves each row's own Restricted form to the named head, and a near miss (the predicate with the relation changed, a different base head, an extra conjunct) does not.
Base parameters. The row's base is a call over the head's own parameter names; the match binds them. Derangements(n) ↔ SymmetricGroup(n); OddPartitions(n) ↔ IntegerPartitions(n). A Restricted expression whose base is SymmetricGroup(5) binds n = 5, and the answer is Derangements(5). A base head with more parameters than the restriction names (PartitionsMaxPart's own n, m) is a row whose base names only those it takes.
A restriction's own parameter. KCyclePermutations(n, k) has k that is not the base's. In the row, k appears in the predicate and is a hole: it matches any expression that does not mention the element variable, and is bound to it. Restricted(SymmetricGroup(5), CycleCount(_) = 2) resolves to KCyclePermutations(5, 2). IntegerPartitions with Length(_x) = k is PartitionsIntoKParts(n, k); with All(_raw, _ ≤ m) it is PartitionsMaxPart(n, m) where the predicate reads parts. This reaches the families the table could not hold (restriction.ts:197-202).
A predicate that takes arguments. Not options: option keys are never domain names and options are Rules (AGENTS.md, Names), and a restriction's k is a quantity, not an option. A hole is enough: the predicate is an expression whose free names are the head's parameters. A curried named predicate would need named predicate heads (§1, (a)).
What a hole may bind. An expression free of the element variable. CycleCount(_) = k + 1 binds k + 1 to the hole; whether it should be evaluated first is the builder's call; recommended: bind the evaluated value, so a hole always holds a number a count can take.
The _raw wart. A carrier-typed list value is opaque to generic heads, so the table's 17 list-carrier rows read _raw, the contents, through a Block/Assign in the engine (restriction.ts:246-259, :310-320). A user writing Restricted(IntegerPartitions(5), …) has to reach the contents the same way. A row of that kind is matchable only by a predicate written like it, which no user does by accident. They are not first-slice rows.
The page. The record's page says what the collection is from its row: "The permutations of n with no fixed point, in the order of SymmetricGroup(n)", the predicate rendered from restricts. This is a generated line from data, not a second hand-written summary; how the page builds it is assumed (the renderer was not read). A sibling's page says the opposite in its own words, as PermutationsAsCycles does (combinatorics/reference/PermutationsAsCycles/index.md:24).
Restricted(…) in an expression. Resolution on evaluation, not on canonicalization or parse: the cell shows what the user typed, and its value is Derangements(5). A user who wants to see the filter still has Filter. The alternative, showing the named head as the input is typed, rewrites the user's expression and breaks round trips to Epsil text and Wolfram-style forms. Whether the evaluated head survives compute-engine's own evaluation of the base (SymmetricGroup(5) is a lazy indexed collection, and the matcher reads its head before it is evaluated further) is assumed, and the builder probes it first.
The reverse reading. restricts on a SymbolInfo answers "what is Derangements a restriction of" for the page, the finder and the census without running code.
First slice: four permutation rows, each with a statistic as the predicate, so none needs the _raw wart or the part-test folds.
-
Derangements(FixedPoints(_x) = 0) andCyclicPermutations(CycleCount(_x) = 1): rows exist inRESTRICTIONSand have kernels and tests. -
KCyclePermutations(n, k)(CycleCount(_x) = k): the first parameter hole. -
EvenPermutations(the parity ofInversions(_x), held to the lex filter,permutations/tests/epsil-families.test.ts:263): a predicate that is not a bare comparison, to find out whether the match survives it. If it does not, swap inKInversionPermutations(n, k)(Inversions(_x) = k).
Files that change:
-
packages/entry/src/schema.tsandtypes.ts: therestrictskey (base,predicate, strings). - The four records under
combinatorics/reference/: add the rows. -
packages/manifest/src/types.tsand its assembly (assemble.ts,declaration.tsread records): carryrestrictsonSymbolInfo. -
packages/structures/src/restriction.ts:declareRestrictedmatches before it filters; the matcher is one function. The 19 rows move to records over later changes, ordeclareRestrictionsreads the manifest; until then both sources agree by test. -
combinatorics/tests/statistics-carrier-restriction.test.ts: the differential test iterates records' rows.
The test that proves it: for each of the four rows, Restricted(SymmetricGroup(n), Function(predicate, p)) evaluates to the named head with the bound parameters, and the named collection matches the filter in count and in every member in order for n = 0..6 (and k = 0..n+1); then the near-miss cases filter and still equal the same members. Run it in the combinatorics tests (vp test), and the schema, manifest and census drift tests that read records.
Do not alias a restriction whose predicate is not a plain expression yet (Involutions as the all fold at core.ts:376, the pattern classes' occurs), and do not alias the 17 _raw rows, until the _raw convention is settled (question 3).
-
Where does the match happen: parse, canonicalization or evaluation? Evaluation. The input keeps its text, round trips survive, and
Restrictedalready does its work at evaluation (restriction.ts:270-274). -
A row in the record, or the table kept and read by the manifest? The record. It is the source for everything else about a head, and an installed library has no
restriction.tsto add to. The 19 rows move in a follow-up change by hand; it is not a codemod-sized change. -
How do the list-carrier rows (17 of 19) state their predicate without
_raw? Undecided; recommend a statistic or a collection-level head (Parts(_x)) that reads the contents, soAll(Parts(_x), …)is the user's form too. Until then the rows stay in the table, unresolved, andRestrictedon them filters as today. -
Match modulo equivalence? No. Exact up to renaming and holes. A miss is slow and correct; an over-eager match is wrong with no test to say so. If an equivalence is common (
0 = FixedPoints(p)), the row lists it. -
Does
Restricted(Restricted(B, p), q)fuse? No.Filterover a lazy filter composes already; fusing to a conjunction would match a row only by luck. -
Does a base that is itself a named restriction match? Yes, with no new machinery: a row's base is any head, so a row over
Derangements(n)is a row like the others.Restricted(Derangements(n), CycleCount(_x) = 1)matches none today because none is written. -
What of
Carrier.restrictsandCarrier.predicate? Remove them in the same change: unused (measured), and the opposite of the rule that a restriction keeps its carrier (restriction.ts:3-7). -
Is a wrong row detectable at declaration time? A row is checked at test time, on a grid. Recommend also a cheap check at declaration of the head's first few members,
Count(Restricted)against the named count at n ≤ 4, only in development builds; it costs the filter, which is bounded at that size. Assumed useful; the builder measures. -
The sibling's page: does it state its relation to the base? Yes, in prose as now; a
siblingOfkey would be a second claim to keep true, so none until a use exists.
Measured, by reading and counting the tree: that Restricted is Filter (restriction.ts:267-276); 19 rows in RESTRICTIONS, 18 with implementedBy, 2 on SymmetricGroup, 6 on IntegerPartitions, 11 on IntegerCompositions; that the table is skipped for a declared name and never resolves an expression (:301-304); that the differential test covers the 18 (statistics-carrier-restriction.test.ts:79-144); the 22 permutationRestriction families and which are in the table; that records carry no base or predicate (Derangements, Involutions, AlternatingPermutations) and the record schema is closed (schema.ts:348); that Carrier.restricts and Carrier.predicate are set nowhere; that PermutationsAsCycles is the sibling its record says; that no IsDerangement-like head exists.
Assumed: that the matcher is a small first-order function over MathJSON and compute-engine's pattern machinery is not needed; that compute-engine leaves SymmetricGroup(5) as a call whose head the matcher can read when Restricted's operands arrive; that holes bind values rather than expressions needing evaluation; that the page generator can render a restricts row; that EvenPermutations' parity predicate matches by (c) as a non-comparison (the builder tests it); that no sibling hides among the permutation families that have neither a row nor a filter test (Involutions, Alternating, Connected, KDescent, the pattern classes): their order is stated by Restrictions §3 as induced and held by their own brute-force readings (combinatorics/tests/restriction-fast-paths.test.ts:1-5), not read case by case for this page.