Re: Re: Question on pattern matching

*To*: mathgroup at smc.vnet.net*Subject*: [mg47882] Re: [mg47851] Re: Question on pattern matching*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Thu, 29 Apr 2004 03:06:27 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

As has often been explained, for reasons of performance Mathematica pattern matcher will not attempt to find all possible patterns. This is particularly true in the presence of the Flat and/or Orderless attributes. Since these attributes are possessed by the most commonly used Mathematica functions (Plus, Times) and since pattern matching is so basic to Mathematica, one can't possibly expect an exhaustive search to be made every time pattern matching is used in an expression involving addition or multiplication. It is difficult for a mere user (unless his first name is Hartmut ;)) to give a complete analysis but the general rule of thumb is to use the simplest and most natural pattern that will do the job in the circumstances. One should not try to use a patterns that is more complex than what is needed because one should remember that for the designers of Mathematica pattern matching was intended to serve a practical purpose of making ordinary programming tasks easier and not to be something that is studied for its own sake. There are in fact systems that will perform exhaustive searches for all patterns and there are articles discussing the issues involved, such as performance. But Mathematica is a general purpose system, which make sit a quite different animal. So now let's turn to some of your examples. They would involve serious issues if they occurred in a system designed to perform exhaustive searches for patterns but Mathematica is not one of them. So why should anybody try a pattern like Module[{f},Attributes[f]=Flat; MatchQ[f[1,2,3],f[__f]]] False instead of the simple: Module[{f},Attributes[f]=Flat; MatchQ[f[1,2,3],__f]] Out[15]= True ? or Module[{f},Attributes[f]=Flat; MatchQ[f[1,2,3],HoldPattern@f[f[1],_]]] False instead of just Module[{f},Attributes[f]=Flat; MatchQ[f[1,2,3],f[1],_]] True ? or Module[{f},Attributes[f]={Flat,Orderless}; MatchQ[f[1,2,3],f[s__,__]/;{s}==={2,1}]] False instead of Module[{f},Attributes[f]={Flat,Orderless}; MatchQ[f[1,2,3],f[2,1,__]]] True an so on, and so on ... Andrzej Kozlowski On 28 Apr 2004, at 19:56, Maxim wrote: > Take a look at > > http://forums.wolfram.com/mathgroup/archive/2000/Jan/msg00296.html > > To sum it up, when Mathematica deals with patterns involving Flat or > Orderless, it performs regrouping/reordering of arguments only if you > explicitly have something like f[_, _] in the pattern. Blank[] as the > head won't do: for a pattern such as h_[_, _] Mathematica is not smart > enough to first match h_ to f and then to look at the attributes of f. > BlankSequence or Repeated won't work in combination with Flat either > (but will work with Orderless): > > In[1]:= > Module[{f}, Attributes[f] = Flat; > MatchQ[f[1, 2, 3], f[_f]] > ] > > Module[{f}, Attributes[f] = Flat; > MatchQ[f[1, 2, 3], f[__f]] > ] > > Module[{f}, Attributes[f] = Flat; > MatchQ[f[1, 2, 3], f[_f..]] > ] > > Module[{f}, Attributes[f] = Flat; > MatchQ[f[1, 2, 3], HoldPattern @ f[f[1], f[2, 3]]] > ] > > Out[1]= > True > > Out[2]= > False > > Out[3]= > False > > Out[4]= > False > > This is very counter-intuitive, because if we have an expression > matching f[_f] then it should also match f[__f] and f[_f..] -- the > last two patterns are more general. It's even harder to explain what > Mathematica didn't like in the following example: > > In[5]:= > Module[{f}, Attributes[f] = Flat; > MatchQ[f[1, 2, 3], f[x_, _] /; x === f[1]] > ] > > Module[{f}, Attributes[f] = Flat; > MatchQ[f[1, 2, 3], HoldPattern @ f[f[1], _]] > ] > > Out[5]= > True > > Out[6]= > False > > And even more confusing in the case of Orderless: > > In[7]:= > Module[{f}, Attributes[f] = Orderless; > MatchQ[f[1, 2], HoldPattern[f][2, 1]] > ] > > Module[{f}, Attributes[f] = Orderless; > MatchQ[f[1, 2], HoldPattern @ f[2, 1]] > ] > > Out[7]= > True > > Out[8]= > False > > What's more, this gives a nasty complication: what if we combine Flat > and Orderless? > > In[9]:= > Module[{f}, Attributes[f] = Orderless; > MatchQ[f[1, 2, 3], f[s__, __] /; {s} === {2, 1}] > ] > > Module[{f}, Attributes[f] = {Flat, Orderless}; > MatchQ[f[1, 2, 3], f[s__, __] /; {s} === {2, 1}] > ] > > Out[9]= > True > > Out[10]= > False > > When we add the Flat attribute, we only make the pattern more general, > but suddenly there's no longer a match. Absolutely illogical and > misleading. > > Maxim Rytin > m.r at prontomail.com > >