Classifiers and Canonical Simplifiers
A classifying function for an equivalence ~ has the property ; that is, two elements are equivalent if the result of applying the classifier to both elements is the same. Note that the range of need not be the same as the domain. For example, the length function on symbol names is a classifier for the relation introduced in the section on Equivalences. The length function appeared in all our ordering predicates and equivalence relations and we may wonder whether we could not speed up the code by computing the length once for each element and then working with the lengths only.
A canonical simplifier is a classifier with the property (here, the range is the same as the domain). This condition implies . A canonical simplifier thus allows to identify a unique (simplest) element in every equivalence class. For every , is this simplest element in the equivalence class of .
If the range of a classifier is totally ordered, this order induces a total preorder on the domain: . The equivalence class generated by this preorder is of course the one classified by .
Because Mathematica expressions are totally ordered (by the so-called canonical ordering), every classifier introduces a preorder: . It follows that whenever we can find a classifier or canonical simplifier, we can use the faster method involving sorting to find equivalence classes.
The code for partitioning into equivalence classes using a classifier is similar to the code for
The default canonical simplifier
This function was called
This method is much faster than the earlier ones.
The code for computing a transversal (or union) based on classifiers is much faster than the built-in
If the classifier is a canonical simplifier there is one preferred transversal, where each class is represented by its canonical element. It is particularly easy to code.
Incidentally, we could also express
Converted by Mathematica