Skip to content

Speculative Equality

enumeratio edited this page Nov 16, 2026 · 1 revision

Equality and sameness

Speculative. A proposal, not adopted.

Many heads need a notion of "the same": Union, Unique, Tally, Gather, Intersection, Complement, Contains, IndexOf, GroupBy, set-like collections, IsIsomorphicGraph, numeric comparison, canonical forms. Today each picks its own test. compute-engine's native heads use structural identity (isSame); this repo's overrides of Union, Gather, GatherBy and Commonest use mathematical equality (isEqual); Unique, Gather and Split take a positional test; VerificationTest takes a SameTest -> f rule. There is no single rule for what the test is, what it may be, or what happens when it is not an equivalence relation. This page works out what exists and proposes one treatment, most of it for upstream.

"Measured" means read from the tree at origin/main (commit bfa63e225) or from compute-engine at tag v0.187.1 (commit fdbbf5091, 2026-11-11), the version this repo pins (pnpm-workspace.yaml:41). Paths beginning src/ are compute-engine's, at that tag. "origin/main" for compute-engine means e5c3026fe (0.192.0). Nothing was run; every behaviour below is read from code, not probed. "From memory" means about Wolfram or another system, not checked against a file. "Assumed" means reasoned. (The local compute-engine clone's checked-out commit is 8c3b9f519, 2026-10-06, 1509 commits behind origin/main; its tags were read instead.)

Recommendation

  1. Keep compute-engine's names. IsSame (raw structural), Same (structural after canonicalization), Equal (value, within tolerance, may stay inert). Do not ask upstream for SameQ. compute-engine documents Same as deliberately not evaluating (src/compute-engine/library/relational-operator.ts:1566-1580), so Wolfram's SameQ is a different operator, and docs/MATHEMATICA-NAMES.md rule 3 allows an alias only when the meaning matches.
  2. One mechanism for "equal up to a relation": a two-argument predicate, SameTest -> f, on every head that pairs elements (Union, Intersection, Complement, Unique, Gather, Tally, Split), with the positional spelling kept where it already ships (Unique, Gather, Split). f is read as a relation, with fixed semantics: each element is compared against the kept representatives in order, the first match wins, the first element in the operand's order survives.
  3. Prefer a key where one exists. GatherBy, SortBy and a Unique-by-key head take a function x -> key; a canonical form (CanonicalGraph) is exactly such a key. Documented as the fast path (hash or sort, not pairwise). A key cannot express a tolerance.
  4. An undecided test verdict leaves the call unevaluated, and a pairwise loop has a cap past which it declines. Both are what compute-engine's own Unique(xs, test) does on origin/main.
  5. No named tolerance head yet. A lambda (a, b) => Abs(a - b) <= eps covers the one frontier example. Revisit when a second head needs the same relative-or-absolute rule.
  6. Upstream: the Tally test argument and a design question for the option form on the variadic set heads (an issue alone, since it needs the maintainer's call). Here: the default-sameness fix for the overrides, the shared helper, isomorphism and canonical-form heads.

What exists

compute-engine (v0.187.1)

Head Compares Evaluates operands Unknowns Tolerance Where
IsSame structure, no canonicalization no (lazy) decides, never inert none src/compute-engine/library/relational-operator.ts:1351
Same (Epsil ===) structure of the canonical forms; variadic, adjacent pairs canonicalizes, never evaluates; ignores a symbol's value decides (x === y is False) none relational-operator.ts:1557
Equal value; chains; broadcasts list-vs-scalar yes stays inert (x^2 = 4 is a condition) exact numbers exactly; floats within ce.tolerance relational-operator.ts:1366, verdict :938
NotEqual negation, same rules yes inert as Equal relational-operator.ts:1616
IdenticallyEqual identity in the free variables (prover) yes inert when undecided tolerance in samples relational-operator.ts:1503
Approx, ApproxEqual difference of .N() values is zero .N() undefined with unknowns absolute, ce.chop relational-operator.ts:1897, :1917, approxEq :2622
Chop replaces a tiny value by 0 yes n/a absolute, ce.tolerance src/compute-engine/library/arithmetic.ts:7456
FixedPoint "two successive values are the same" yes n/a relative: 2^-46 at machine precision src/compute-engine/library/control-structures.ts:1625-1669
  • Same does not evaluate: sqrt(2) === 1.4142135623730951 is False, and a list is compared whole (relational-operator.ts:1583-1596). The wiki's Ideas page says Same "evaluates"; at this tag it does not.
  • The tolerance is one engine setting, absolute, default 1e-10 whatever the precision (src/compute-engine/numerics/numeric.ts:30; src/compute-engine/index.ts:1518-1522). Two exact numbers compare exactly, without tolerance (relational-operator.ts:488-497); a machine float compares with Math.abs(av - b) <= tolerance (src/compute-engine/boxed-expression/compare.ts:1527).
  • isEqual is the "cheap tier": evaluate, then isSame, then the difference within tolerance when no unknowns; undecided is undefined, not false (compare.ts:841-856).
  • isSame is documented as reflexive, symmetric and transitive for every operand, so any dedup key is safe (compare.ts:575-583). It is not alpha-equivalence: bound variables compare by name (compare.ts:538-546). Equal is not transitive for floats within a tolerance (assumed from the absolute test above).
  • A kind value can supply its own equality: Measurement compares by nominal (src/compute-engine/library/arithmetic.ts:11438), and kindEqual orders the cases (src/compute-engine/boxed-expression/kind-compare.ts:389-414).

Collection heads and their sameness:

Head Sameness today Where
Unique(xs), Tally isSame, linear scan over kept values (O(n·u), u kept) src/compute-engine/library/collections.ts:20893, tally :24612-24637
Union, Intersection, Complement isSame with elem.hash buckets (expected O(n)); an element with a random effect is never merged src/compute-engine/library/sets.ts:1546, :1834-1853
Contains, IndexOf structural; NaN finds NaN collections.ts:13851, :19788
Sort(xs, order) a comparator or a key collections.ts:20241
GroupBy(xs, key) a key function collections.ts:21538
Position a predicate on the element collections.ts:20173

No head in the v0.187.1 library declares an option rule in its signature (a grep of signature: '…' strings for Rule found none; assumed complete).

After v0.187.1, origin/main (0.189.0) gives Unique a test: Unique([1, 2, 3, 4], (a, b) => a mod 2 == b mod 2) is [1, 2] (CHANGELOG.md:840-855, PR #539 by enumeratio). Its loop compares each new element with the kept ones as f(kept, x), stops at the first True, declines past ce.iterationLimit, and leaves the call unevaluated on an undecided verdict (src/compute-engine/library/collections.ts:24696-24729 on origin/main). Tally, Contains, Union and Intersection take no test there (signatures at collections.ts:20958, :13912; sets.ts:1507, :1560). compute-engine's ROADMAP.md and docs/ have no plan for SameTest, SameQ or a tolerance head (grep: none).

This repo

Head Sameness today Where
Unique(xs, test) override: positional test, f(kept, x), undecided counts as "not a duplicate" packages/symbols/combinatorics/combinatorics/collections/src/list-stats.ts:254-275
Gather(xs, test?) default isEqual(a, b) === true; test positional, applied to the group's first element .../collections/src/list-ops-wolfram.ts:115-123, :282-301
GatherBy(xs, f) key compared by isEqual === true, linear scan list-ops-wolfram.ts:303-320
Split(xs, test?), SortBy test or key, as above list-ops-wolfram.ts:322, :362
Union (override) dedup by isEqual !== true against every kept element, then canonicalCompare sort .../collections/src/list-heads.ts:386-415
Commonest isEqual === true list-heads.ts:647-662
Same (override) evaluates the operands, "as SameQ does" .../collections/src/expression-ops.ts:211-221; record packages/reference/entries/Same/index.md
VerificationTest SameTest -> f rule, default isSame; f applied through applyFunction, result read as True packages/symbols/evaluation/evaluation/src/declare.ts:117-150, verification-test.ts:41
Chop(x, tolerance) positional absolute tolerance, widened from compute-engine .../collections/src/rounding-heads.ts:12
IsIsomorphicGraph brute force over n! relabelings after size, edge and degree filters; unevaluated past 9 vertices .../collections/src/graphs-2.ts:206, :248; record reference/IsIsomorphicGraph/index.md
KNecklaces, BinaryNecklaces, bracelets list one representative per rotation (reflection) class: least word record reference/KNecklaces/index.md
Around, CenteredInterval uncertainty values in @notatio/analytic; their equality was not read packages/symbols/analysis/analytic/reference/Around/index.md

Option plumbing exists: optionsOf and ruleOf read trailing rules, leftmost setting wins (packages/engine/src/options.ts:1-50), and applyFunction applies a function value (packages/engine/src/apply-function.ts:99). Not found in the tree: SameTest on any set head, WithinTolerance, CanonicalGraph (the Graphs page says there is none), EquivalenceClasses, Counts, DeleteDuplicatesBy. Tally is compute-engine's, unoverridden.

Findings from the table:

  • The defaults disagree. Unique, Tally, Contains, IndexOf use isSame; our Union, Gather, GatherBy, Commonest use isEqual. Whether Union([1, 1.0]) or a pair of floats 1e-11 apart collapse differs by head. (Which one Wolfram's Union and Gather use by default is from memory: SameQ.)
  • Our Union dedup is order-dependent for floats. It keeps an element when no kept element is isEqual; with an absolute tolerance that is not transitive (assumed from compare.ts:841-856; not run).
  • Undecided is treated differently. compute-engine's Unique declines; our Unique, Gather and Union treat an undecided test as "different" (list-stats.ts:263, list-ops-wolfram.ts:296, list-heads.ts:399).
  • Our Same override changes an Epsil operator. === is Same, which compute-engine specifies as non-evaluating; the override evaluates and records it "as SameQ".

1. The three kinds of "same"

(a) Structural identity of expressions. Two expressions are the same term. Served by IsSame (raw) and Same (canonical form); the default of Unique, Tally, Union, Contains and IndexOf in compute-engine. Total, reflexive, symmetric, transitive, hashable (compare.ts:575-583, sets.ts:1834). The repo's VerificationTest default is this. Gap: none for the engine; the repo's Same override blurs it with (b).

(b) Mathematical equality after evaluation. Equal: exact numbers exactly, floats within ce.tolerance, symbolic stays inert. Three-valued; not an equivalence relation on floats. Served by Equal, Approx, Chop. Gaps: the tolerance is global and absolute while FixedPoint uses a relative bound; two numbers of very different magnitude (1e-20 and 2e-20) are Equal under the absolute rule (assumed from the code).

(c) Equivalence under a stated relation.

Relation Example Served by Gap
up to relabeling graphs, posets IsIsomorphicGraph (pairwise, n ≤ 9); planned CanonicalGraph, CanonicalPoset (Graphs and Posets pages) no canonical form yet; no way to dedup a list of graphs but pairwise
up to rotation or reflection necklaces, bracelets the collections list representatives no head maps a word to its class representative, so "are these two words the same necklace" has no head
up to a key GatherBy, SortBy, GroupBy key heads exist no Unique by key, no Tally/Counts by key (Counts is a frontier gap)
within a tolerance float dedup Unique(xs, test), Gather(xs, test) none on Union, Intersection, Complement, Tally; no relative form

The Graphs page states the principle: values stay structurally unequal, and an isomorphism check compares canonical forms ("Equality of values stays structural"). This page adopts it for every carrier: equality of a value is (a); "up to R" is a key or a test, never a change to Equal.

2. Wolfram's design and what the frontier uses

From memory, not checked: SameQ is structural and evaluates its arguments, with 1 and 1. different; Equal is mathematical, inert on symbols, and tolerant of the last bits of floats; UnsameQ and Unequal negate them. Union, Intersection and Complement take a SameTest -> f option; DeleteDuplicates, Gather, Split and Tally take the test as a second positional argument; FixedPoint takes SameTest. The …By heads (GatherBy, SortBy, CountsBy, DeleteDuplicatesBy) take a key. MemberQ and Position match patterns, not a test. Which head takes which form should be checked against Wolfram's reference before anything is posted.

Measured in the repo's data:

  • Wolfram documents SameTest, SameQ, UnsameQ, Unequal, Counts, CountsBy, DeleteDuplicatesBy and Tolerance as symbols (packages/reference/src/wolfram-documented-data.ts:5471-5473, :1499-1500, :1741, :6404, :6611, :6647; names only).
  • The frontier (heads Wolfram's 52,424 documentation examples call that we cannot answer) lists UnsameQ (7 uses), PossibleZeroQ (6), Nearest (5), Counts (3) (packages/census/src/wolfram-frontier-data.ts:1076, :1196, :1380, :1920). SameQ is not in it.
  • SameTest occurs nowhere in the frontier or call-form tables (grep: 0). The call-form table is a sample of a few forms per head, so this is weak evidence of absence.
  • What the sample shows: DeleteDuplicates with a test in 3 of 7 forms, one a tolerance (Abs[#1 - #2] <= 0.01 &) (wolfram-frontier-data.ts:3362-3368); Gather with a test in 1 of 2 (:4475); UnsameQ as the predicate of NestWhile, NestWhileList and Split in 9 forms (:6062-6074, :7239); Union 4 forms and Intersection 2, none with a test (:7632, :4883).
  • The transpiler maps UnsameQ to a conjunction of Not(Same(a, b)) over pairs (packages/wolfram/src/from-wolfram.ts:288-291); Unique renames to DeleteDuplicates (packages/wolfram/tests/to-wolfram.test.ts:259).

What transfers: the test-as-predicate shape and the key-function family. What does not: Wolfram spreads the test over two spellings (option, positional) by head; compute-engine has no option mechanism in signatures, so a rule option on a native head is new machinery upstream.

3. The options

A: SameTest -> f everywhere B: keys only C: both, key preferred D: named heads per relation
Cost per call pairwise, ≤ n·u calls of f hash or sort: n key calls, expected O(n) or O(n log n) key path as B, predicate path as A per head
Tolerance yes no (a grid key splits near cell edges) yes, via the predicate one head per tolerance kind
Canonical forms as a test Same(canon(a), canon(b)), recomputed per pair exactly a key, computed once per element key IsIsomorphicGraph etc.
New API an option on ~7 heads …By heads or a By option A + B many heads
Upstream needs an option mechanism GroupBy, Sort already take keys A's part is the blocker none general
Non-equivalence needs a defined behavior cannot occur (a key is an equivalence) defined on the predicate path only n/a

A. Written Union(xs, ys, SameTest -> ((a, b) => Abs(a - b) < 10^-9)) and, where shipped, Unique(xs, (a, b) => …). It is Wolfram's shape and the repo's option rule (Over -> R; VerificationTest is the precedent). Variadic heads cannot take a positional test (a trailing function is ambiguous with a collection operand), so the rule form is needed there. Cost: pairwise, and compute-engine has no option mechanism.

B. GatherBy(graphs, CanonicalGraph), UniqueBy(words, NecklaceRepresentative) (both names proposed, neither exists). Cheap, and the key can reuse .hash (sets.ts:1834). Cannot say "within 1e-9".

C is the recommendation: B documented as the fast path, A for what a key cannot say.

D (a head per relation, e.g. IsIsomorphicGraph) stays for relations with a real name and a kernel; it is not a general mechanism.

When f is not an equivalence relation. Tolerance is not transitive: with f = |a-b| <= 1, Unique([0, 1, 2]) keeps 0, drops 1, and keeps 2, but Unique([1, 0, 2]) keeps 1, drops 0 and 2. Proposed rule: elements are visited in the operand's order; each is compared with the kept representatives as f(kept, x) in kept order; the first True makes it a duplicate; otherwise it is kept. That is what compute-engine's Unique and this repo's Unique and Gather already do, so the behavior is defined and order-dependent, not an error. Not reflexive: an element is never tested against itself, so it does not matter. Not symmetric: the argument order is (kept, new), documented. The numerics rule "decline rather than answer wrong" applies to a kernel vouching for digits; a deterministic leader rule is stated behavior, not a wrong answer. It must be written in each head's record. Declining applies to the other failure: an undecided verdict or a cap hit leaves the call unevaluated.

Order. Which duplicate survives is the first in the operand's order. For an ordered collection that is a defined element (for LabeledGraphs(n) ranked by canonical rank, the least rank, which is also the canonical representative). For an unordered Set operand, the iteration order was not checked; the proposal is to visit in canonical order (as the Union override sorts with canonicalCompare, list-heads.ts:402) and say so.

4. Tolerance

The engine has one absolute tolerance (1e-10), a chop that uses it, an Approx family that uses it, and FixedPoint, which uses a relative one after finding the absolute one stopped too early (control-structures.ts:1625-1631). So "within tolerance" already means two things in compute-engine.

  • Named head, WithinTolerance(eps) as a predicate constructor. Usable as SameTest -> WithinTolerance(10^-9). Gains: one place for the absolute-or-relative rule (|a-b| <= eps·max(|a|, |b|) is easy to get wrong in a lambda, and a zero operand needs the absolute form). Cost: a new head with no Wolfram counterpart (assumed: not in Wolfram), no demand in the data beyond one lambda example (wolfram-frontier-data.ts:3366).
  • A Tolerance -> eps rule on Equal-like heads. Wolfram documents Tolerance as a symbol (wolfram-documented-data.ts:6404); which heads take it is from memory only. It would change what a collection head means, with two options (SameTest, Tolerance) doing one job.
  • The engine's global tolerance. A default SameTest of Equal inherits it; changing it is a session setting, which is hidden state for a catalogue record. Examples should state the tolerance in the test.

Recommendation: no named head now; use a lambda; add WithinTolerance(abs, rel) only when a second head or a documented pattern needs it. Intervals and uncertainty values: compute-engine's Measurement compares by nominal, ignoring the error (arithmetic.ts:11433-11438); docs/plans/2026-10-26-value-kinds.md says Around compares by nominal in Wolfram (from the plan's own text, not checked). Whether our Around and CenteredInterval follow was not read. Equality of two enclosures (same ball, or overlapping) is a separate question, and "overlap" is a natural SameTest for them.

5. Upstream and here

Part Where Why
Tally(xs, test) patch in packages/ce-patches/, then issue with PR widens a native head; the Unique precedent (#539) landed
SameTest rule on Union, Intersection, Complement issue alone first compute-engine has no option rule in any signature; maintainer's design call (Contributing, upstreaming)
Same/IsSame naming nothing compute-engine's documented design beats a Wolfram lean
default sameness of our Union, Gather, Commonest here overrides; no upstream change
a shared test/option reader here one helper, not a copy per head
IsIsomorphicGraph, CanonicalGraph, CanonicalPoset, necklace representative here our carriers

Unique(xs, test) is on origin/main from 0.189.0; our override (list-stats.ts:254) is retired when the pin passes it, and tests/landed.test.ts will say so.

Plan for a builder

  1. Probe, one session, no edits. On the pinned engine: Union([1, 1.0]), Union of two floats 1e-11 apart, Gather of the same, Unique of the same, and Equal of two floats at the tolerance edge in both argument orders. Record the table of defaults per head. This settles the open question on the default and costs minutes.
  2. A shared helper in the collections package: reads a trailing SameTest -> f rule or a positional function with optionsOf/applyFunction, returns (kept, x) => true | false | undefined, and the leader loop with a step cap. Unique, Gather and Split use it, keeping their positional spelling.
  3. SameTest on our Union (and Intersection, Complement if overridden), with the default fixed to the answer of question 1.
  4. Decline on undecided in the repo's Unique, Gather, Union (the repo currently reads undecided as different).
  5. Tally(xs, test) as a patch in ce-patches: widen the signature with widenSignature/wrapOperator as Unique does, reuse the same loop and cap. Tests in compute-engine's style: Jest describe/test, a typed cases array, names carrying the expected value, each case through evaluate(), .N(), .simplify() and the parse route, explicit assertions, one file test/compute-engine/item-<n>-tally-test.test.ts; cases: parity classes, a tolerance with the order-dependent result stated, an undecided test staying unevaluated, the step cap, a string operand.
  6. Records: for each head, one bullet in its reference entry saying the leader rule and that f should be an equivalence relation.
  7. Later: CanonicalGraph and UniqueBy as in the Graphs page's lane.

Tests in the repo follow its rules: examples as the snapshots, a role: test example for the order-dependent case, no toMatchSnapshot.

Open questions, with recommended answers

  1. Default sameness of Union, Gather, GatherBy, Commonest: isSame or isEqual? Recommend isSame, as compute-engine's Union/Unique/Tally and (from memory) Wolfram's SameQ; a tolerance is then opt-in through SameTest. Reason: a transitive, hashable default, no order-dependence, and one answer across heads. Cost: Union([1, 1.0]) may now keep both if the two are not isSame (to be probed).
  2. Does the repo keep compute-engine's IsSame/Same, or ask for SameQ? Keep; ask for nothing. The repo's rule that predicates are Is… already gives IsSame, and a compute-engine ruling beats a Wolfram lean.
  3. Keep the Same override that evaluates? Recommend dropping it from Same and mapping Wolfram's SameQ[a, b] in the transpiler to Same of the evaluated operands, so Epsil === keeps compute-engine's documented meaning. Reason: the override contradicts relational-operator.ts:1566-1580. Needs the owner: the override's tests (expression-ops.test.ts:114-117) assert the evaluating behavior.
  4. Rule or positional test? Both: positional where shipped (compute-engine accepted it for Unique), SameTest -> f on variadic heads, one reader for both. Reason: the option rule is the repo's convention, the positional form is what upstream took.
  5. Upstream the option on the set heads? Post an issue alone first asking for the design call. Reason: no native head has an option rule.
  6. Reject a non-equivalence f? No: define the leader rule and document it. Reason: reflexivity and symmetry cannot be checked cheaply, and tolerance is the main use.
  7. Named tolerance head? Not yet (section 4).
  8. Unordered operands with a test: visit in canonical order, or decline? Recommend canonical order, stated in the record. Needs a probe of how Set iterates.
  9. Key-form names: UniqueBy, CountsBy, or a By rule? Recommend heads (GatherBy and SortBy exist, and Wolfram has DeleteDuplicatesBy, CountsBy, from memory); Unique keeps its Wolfram rename DeleteDuplicates, so UniqueBy maps to DeleteDuplicatesBy.

Measured versus assumed

Measured (read, not run): the compute-engine heads, handlers and line references in "What exists" at v0.187.1; Unique(xs, test) on origin/main and its changelog entry; the absence of a SameTest plan in compute-engine's ROADMAP.md and docs/; the repo heads and their sameness functions; the VerificationTest option plumbing; the frontier and documented-name data and the counts quoted from it.

Not measured: any evaluation result (no engine was run: Union([1, 1.0]), float dedup, Equal at the tolerance edge); the iteration order of a Set; how Equal treats Around and CenteredInterval in this repo; costs of the pairwise loop on real sizes.

From memory, not checked: every statement about Wolfram's behavior and its spelling per head (section 2, and the defaults in the findings), that 1 and 1. differ under SameQ, that Wolfram has no tolerance-predicate head, what Tolerance is an option of.

Assumed: that absolute-tolerance equality is non-transitive in the way described; that Union dedup with isEqual is order-dependent for floats; that Equal(1e-20, 2e-20) is true; the complexity figures for the key and predicate paths; that no head in the v0.187.1 library declares a rule option beyond what the grep covered.

Home

Project

Working

Design: every design page, by subject

Clone this wiki locally