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