Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Re: bug in IntegerPart ?
  • Next by Date: Re: Re: Question on pattern matching
  • Previous by thread: RE: Re: Question on pattern matching
  • Next by thread: Re: Re: Question on pattern matching