[Haskell-cafe] conflicting variable definitions in pattern

[wren ng thornton]

Conor McBride wrote:
> Hi
> 
> Sittampalam, Ganesh wrote:
> > Martin Hofmann wrote:
> > > It is pretty clear, that the following is not a valid Haskell pattern:
> > >
> > > foo (x:x:xs) = x:xs
> > >
> > > My questions is _why_ this is not allowed. IMHO, the semantics should
> > > be
> > > clear: The pattern is expected to succeed, iff 'x' is each time bound
> > > to the same term.
> 
> That's what my daddy did in 1970. It was an extension of
> LISP with pattern matching. He used EQUAL. That makes me
> one of the few functional programmers who's had this
> feature taken away from them. I'm not weeping, but I do
> miss it.

On the one hand, unification is awesome; on the other hand, pattern 
matching is simple. The nice thing about the simplicity is that it's 
easy to compile into efficient code, and it's easy to 
explain/understand. Unification has all sorts of unfortunate 
consequences[1] and it's much harder to explain to the uninitiated.

Curry[2] has features like this, but then it has full 
backtracking-search logic programming. It might be interesting to see if 
a more restricted form is useful in Haskell, though it should be an 
optional feature IMO so that it can be disabled for guaranteed-efficient 
patterns and typo detection.


[1] e.g. optimal factoring of an unordered set of Prolog terms is 
NP-complete. For a fixed ordering there are good algorithms, and Haskell 
has fixed ordering due to the semantics of overlapping patterns, but 
this should still give some clues about what lurks beneath.

[2] http://www.curry-language.org/


> > How do you define the "same term"?
> >
> > One natural way of compiling it would be to
> >
> > foo (x:y:xs) | x == y = x:xs
> >
> > but then pattern matching can introduce Eq constraints which some might
> > see as a bit odd.
> 
> Doesn't seem that odd to me. Plenty of other language features
> come with constraints attached.

Another option is to use structural matching all the way down. This has 
the benefit of not calling user-defined code, though it has the 
disadvantages of not matching heterogeneous but semantically-equal 
values. Of course, by removing the Eq constraint this also re-raises the 
specter of comparing functions. But it's a good Devil's Advocate 
definition to bear in mind.

-- 
Live well,
~wren