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: [mg47862] Re: [mg47801] Re: [mg47765] Question on pattern matching
  • From: "Roman Green" <rgreen at mail.ru>
  • Date: Thu, 29 Apr 2004 03:05:11 -0400 (EDT)
  • References: <4FDA877403669E48A2CB7F1122A79480194EC2@dassne02.da.gei>
  • Sender: owner-wri-mathgroup at wolfram.com

----- Original Message ----- 
From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
To: mathgroup at smc.vnet.net
Subject: [mg47862] RE: [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: [mg47862] [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


============================================================================
===============

Hello, Wolf

Very clear explanation!

Much appreciated.

I am not yet certain on meaning of symbol RuleCondition (which is omitted
from the help, and stated by Mathematica just as 'internal symbol') but I
want first to investigate this on my own. ;)

Thanks again.

----
Roman Green












  • Prev by Date: Re: Re: Question on pattern matching
  • Next by Date: Re: Re: bug in IntegerPart ?
  • Previous by thread: Re: Re: Question on pattern matching
  • Next by thread: programatically feed mma kernel location to MathKernel.Connect Method ?