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: [mg47852] RE: [mg47801] Re: [mg47765] Question on pattern matching
  • From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
  • Date: Wed, 28 Apr 2004 06:56:54 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com
  • Thread-topic: [mg47801] Re: [mg47765] Question on pattern matching

>-----Original Message-----
>From: Roman Green [mailto:rgreen at mail.ru]
To: mathgroup at smc.vnet.net
>Sent: Tuesday, April 27, 2004 10:47 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg47852] [mg47801] Re: [mg47765] Question on pattern matching
>
>
>Hi David,
>
>Thanks for reply.
>
>I have to say I still do not understand exactly how 
>Mathematica performs 
>pattern matching in that case.
>
>I supposed the following:
>When processing
>
>expression /. rule
>
>Mathematica considers all forms of expression that are invariant 
>relatively to attributes set for the components of the 
>expression until 
>a form that matches the rule is found.
>For ex. in the simple case of expression = k[a, b, b] when k carries 
>Orderless attribute, Mathematica should consider forms
>k[a,b,b]; k[b,a,b]; k[b,b,a].
>And the third form should match pattern f_[x_, x_, y_].
>But it does not work...
>
>Here are some more tests I made:
>
>In[1]:= SetAttributes[k, Orderless]
>
>In[2]:= k[b,b,a] /. f_[x_, x_, y_]->0
>
>Out[2]= k[a, b, b]
>
>In[4]:= ClearAttributes[k, Orderless]
>
>In[5]:= k[b,b,a] /. f_[x_, x_, y_]->0
>
>Out[5]= 0
>
>So it seems that f_ matches k without any special attributes but does 
>not matches k with attribute Orderless...
>Why ? I thought f_[x_, x_, y_] should be structurally 
>equivalent to <any 
>symbol with any attributes>[<any  another symbol with any attributes>, 
><the same symbol as previous>, <any  another symbol with any 
>attributes>].
>
>In any case, what is a pattern that matches structure <any symbol with 
>any attributes>[<any  another symbol with any attributes>, <the same 
>symbol as previous>, <any  another symbol with any attributes>] ?
>
>Will appreciate any explanation.
>
>
>---
>Cheers
>
>Roman Green
>
>

Hello Roman,

obviously you didn't get my response in time (or it was too terse). Your supposition above -- when I for myself make such, I call it a phantasy, not a conjecture or even a founded opinion; and there is nothing wrong with that, when you try to support them by observation, reason, proof and combining knowledge -- well, your supposition above just isn't true, and hence (possibly not neccessarily) deductions from that.

There are certainly serveral reasons that pattern matching cannot work the way you describe it. Don't forget in first place that Mathematica is founded on term reduction and the left hand side of  Replace is the result of possible a long chain of conversions. You cannot break that up without going into a mess: you might get into non terminating sequences of substitutions, and if not so, even the simplest matches would become incredibly slow.

Instead the Orderless attribute must work at the pattern, at the rhs of Replace. There the different orderings are tried. But this can only be done if the head(s) in the pattern have that attribute. Therefore if you use head k at rhs it works:

Look e.g.

In[1]:= SetAttributes[k,Orderless]

In[2]:= k[5,3,3]/. k[y_,y_,x_] :> {x,y}
Out[2]= {5,3}


Why does that match at all?
The left hand side reduces to 

In[3]:= k[5,3,3]
Out[3]= k[3,3,5]

but the pattern at the right had side to

In[4]:= k[y_,y_,x_]
Out[4]= k[x_,y_,y_]


By eye that doesn't match. Yet now the machinery for Orderless enters and tries the different orderings of x_ and y_ *at the rhs*! This even works when the lhs is not brought to normal order, as e.g. in

In[5]:= Hold[k[3, 5, 3]] /. k[y_, y_, x_] :> {x, y}
Out[5]= Hold[{5, 3}]

In[6]:= Hold[k[3, 5, 3]]
Out[6]= Hold[k[3, 5, 3]]

But the head k *of the pattern* must have the Orderless attribute to do this, and it *must not* do this if it hasn't that attribute (k_ doesn't, k here is a pattern variable different from Global`k, and, BTW, pattern expression k_ is not a symbol and such cannot have an attribute). This is why

In[18]:= k[5, 5, 3]/. k[y_, y_, x_] :> {x, y}
Out[18]= {3, 5}

matches, but 

In[19]:= k[5, 5, 3]/. k_[y_, y_, x_] :> {x, y}
Out[19]= k[3, 5, 5]

doesn't.


Now for your new example above, that is much simpler to understand:
 
In[20]:= k[5, 5, 3] /. f_[x_, x_, y_] :> {y, x}
Out[20]= k[3, 5, 5]

k is Orderless hence k[5, 5, 3] first reduces to k[3, 5, 5] which then doesn't, cannot, and shouldn't match the pattern f_[x_, x_, y_]. 

for another h (without the Orderless attribute), no reordering at lhs takes place and hence the general pattern matches. 

In[21]:= h[5, 5, 3] /. f_[x_, x_, y_] -> {x, y}
Out[21]= {5, 3}


If you want to exploit the properties of head k at lhs for the purpose of pattern matching use the design I have already published:

In[30]:= k[3, 5, 5]/2 /. expr : f_[_, _, _] :> (expr /. f[y_, y_, x_] -> {x, y})
Out[30]= {3/2, 5/2}



That doesn't work for Hold

In[31]:= Hold[k[3, 5, 5]] /. expr : f_[_, _, _] :> (expr /. f[y_, y_, x_] -> {x, y})
Out[31]= Hold[k[3, 5, 5] /. k[y_, y_, x_] -> {x, y}]

but for a completely different reason, as the execution of the second replacement is now prevented by Hold. See now at the appearance of (Orderless) k in the pattern!


But -- for the aficionados -- this still can be enforced by

In[32]:= Hold[k[3, 5, 5]] /. 
  expr : f_[_, _, _] :> RuleCondition[expr /. f[y_, y_, x_] -> {x, y}]
Out[32]= Hold[{3, 5}]

This is the essence of the Trott-Strzebonski-Method as communicated to this group by Allan Hayes.


Of course it is essential to read §2.3.7 of the Book, repeatedly with every increment of knowledge.



--
Hartmut Wolf


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