Linearity Requirement for Patterns

[Brian Boutel]

"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