[Haskell-cafe] conflicting variable definitions in pattern

[Conor McBride]

Hi

On 15 May 2009, at 09:11, 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.

>
> 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.

>
>> Isn't this allowed, because this would require a strict evaluation of
>> the 'x' variables?
>
> The translation into == would probably introduce some strictness, for
> most implementations of Eq. I don't think this is a huge problem in
> itself.

There's some conceptual ugliness in that such a mechanism
*relies* on fall-through. In principle a sequence of guardless
patterns can always be fleshed out (at some cost) to disjoint
patterns. What precisely covers the case disjoint from (x, x)?

This is fixable if one stops quibbling about guardlessness,
or even if one adds inequality patterns.

One certainly needs a convention about the order in which
things happen: delaying equality tests until after constructor
matching --- effectively the guard translation --- seems
sensible and preserves the existing compilation regime.
Otherwise, repeated pattern variables get (==)-tested, linear
ones are lazy. Meanwhile, yes the semantics depends on the
implementation of (==), but what's new? That's true of do too.

The guard translation: linearize the pattern, introducing
new vars for all but the leftmost occurrence of repeated
vars. For each new x' made from x, add a guard x == x'. The
new guards should come in the same order as the new variables
and stand before any other guards present.

Presumably one can already cook up an ugly version of this
with view patterns ((x ==) -> True).

It seems to me that the only questions of substance remaining
is whether improved clarity in normal usage is worth a little
more translational overhead to unpick what's wrong when weird
things happen, and whether any such gain is worth the effort
in implementation.

I miss lots of stuff from when I was a kid. I used to write

   elem x (_ ++ x : _)  = True
   elem _ _             = False

and think that was cool. How dumb was I?

Cheers

Conor