The Mathematica Journal
Feature Articles
New Products
New Publications
News Bulletins
Write Us
About the Journal
Staff and Contributors
Back Issues
Download this Issue

Classifiers and Canonical Simplifiers

A classifying function [Graphics:../Images/index_gr_52.gif] for an equivalence ~ has the property [Graphics:../Images/index_gr_53.gif]; that is, two elements are equivalent if the result of applying the classifier to both elements is the same. Note that the range of [Graphics:../Images/index_gr_54.gif] 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 [Graphics:../Images/index_gr_55.gif] is a classifier with the property [Graphics:../Images/index_gr_56.gif] (here, the range is the same as the domain). This condition implies [Graphics:../Images/index_gr_57.gif]. A canonical simplifier thus allows to identify a unique (simplest) element in every equivalence class. For every [Graphics:../Images/index_gr_58.gif], [Graphics:../Images/index_gr_59.gif] is this simplest element in the equivalence class of [Graphics:../Images/index_gr_60.gif].

If the range of a classifier is totally ordered, this order [Graphics:../Images/index_gr_61.gif] induces a total preorder on the domain: [Graphics:../Images/index_gr_62.gif]. The equivalence class generated by this preorder is of course the one classified by [Graphics:../Images/index_gr_63.gif].

Because Mathematica expressions are totally ordered (by the so-called canonical ordering), every classifier introduces a preorder: [Graphics:../Images/index_gr_64.gif]. 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 PreorderIndices above. The main advantage is that we can use the built-in ordering for sorting the list and SameQ for splitting, because we can first apply the classifier to all elements just once, instead of repeatedly in the preorder predicate (shown in red).


The default canonical simplifier Identity induces canonical ordering and generates the trivial equivalence.


This function was called Classify in a related Usenet discussion in 1995 [3], where it was implemented directly, without ClassifyIndex. However, the detour through the indices does not slow down the computation (as it did in the examples with PreorderClasses). The original solution was rather more complicated, due to the lack of the Split function in earlier versions of Mathematica.


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 Union with a user-defined equivalence relation for large inputs.


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 EquivalenceIndices in terms of ClassifyClasses, using the mapping from indices to list elements as the classifying function: two indices are equivalent if the corresponding list elements are the same.


Converted by Mathematica      

[Article Index] [Prev Page][Next Page]