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