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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
