Generally, you can divide ML/Haskell pattern-match compilers into thre
groups:

1. Trivial. These compile each pattern in isolation and so may cause a
lot of repeated testing, but the code is guaranteed to be linear in
the size of the pattern.

2. Optimal. These compile a set of patterns to code that never
compares the same constructor in the value twice against the same
constructor-pattern constant. These may even exploit that once you
have compared against N-1 possibilities, there is no need to compare
to the Nth possibility. These will some times cause exponential
explosion (same reason that DFAs can be exponentially larger than
NFAs). The algorithm in Peter Sestofts article ML Pattern Match
Compilation and Partial Evaluation (LNCS 1110) is in this category.

3. Linear code. These compile a set of patterns to code that is linear
in the size of the patterns and tries to avoid comparing the sme
things twice, but give up optimality for code size. The algoritm
described by Wadler in Simon Peyton Jones' book The Implementation
of Functional Languages.

In practice, exponential explosion occurs rarely, and even when it does,
pattern sets are typically small enough that you can live with it. So
it is, IMO, acceptable to compile to optimal code always.

Optimal code will often have several places in the code where the same
RHS is selected. You should avoid copying the RHS code in all of these
places and, instead, jump to the RHS from all of these places.

Torben