[Haskell-cafe] conflicting variable definitions in pattern
wren ng thornton
wren at freegeek.org
Fri May 15 05:47:23 EDT 2009
Conor McBride wrote:
> 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 and it's much harder to explain to the uninitiated.
Curry 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.
 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.
> > 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.
More information about the Haskell-Cafe