# Linearity Requirement for Patterns

**Brian Boutel
**
brian@boutel.co.nz

*Sat, 17 Mar 2001 15:49:15 +1300*

"Samuel E. Moelius III" wrote:
>*
*>* What is the reasoning for the requirement that patterns be linear? Am I
*>* correct to say that if non-linear patterns were allowed, it would require
*>* equality to be defined for all data types? Is this the reason, or are there
*>* others?
*>*
*
If that were the reason, then to be consistent, there would be no
literals in patterns, as these are tested using equality.
Here is a reason. Some people believe that the equations that form a
function definition should be disjoint. A good reason for this view is
that fold/unfold transformations can be then performed without reference
to the other cases in the definition - if it matches, it is correct to
use it. Although Haskell does not require disjoint cases, and defines
the semantics in terms of a top-to-bottom testing order, the rejection
of non-linear patterns was largely because it is not generally possible
to specify, as a pattern, the complement of the set of values that match
a non-linear pattern, and so not possible to write a set of disjoint
case equations if non-linear patterns occur.
In any case, the same effect can be obtained using guards, where the
extra power of expression syntax solves the problem. Instead of
f x x = e1
f (illegal pattern) = e2
...
you can write the single equation
f x y | x == y = e1
| x /= y = e2
--brian