[erlang-questions] erlang *****

[Alpár Jüttner]

> But now consider
> 
> 	f({X,_}\/{_,X},
> 	  {Y,X}\/{X,Y},
> 	  ...
> 	  {Z,W}\/{W,Z}
> 	)
> 
> I don't have a proof, but my gut feeling is that the combination
> of compiling and executing clauses with "or" patterns has to be NP.

The current pattern matching is also NP, so it wouldn't be a problem.
(Contrary to a common misconception, the meaning of NP is _not_
non-polynomial!)
You probably wanted to guess that it is NP-hard (which still doesn't
mean non-polynomial, but something quite close to it.)

If you want to do the pattern matching of all parameters in on step,
then it indeed NP-hard (I even have a proof for it). 

However, if pattern matchings are done one-by-one and left-to-right,
then there is no performance problem. The union operator becomes less
flexible in this case, but it is still quite useful.

Actually, if we want the pattern matching to be deterministic, we _must_
do such a restriction. For example using the patter {X,_} V {_X}, the
value of X could be either element of the tuple. Using the left-to-right
rule, X will always be the first element.

Regards,
Alpar