RE: Baffled By Underscore Pattern Matching

• To: mathgroup at smc.vnet.net
• Subject: [mg46022] RE: [mg45992] Baffled By Underscore Pattern Matching
• From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
• Date: Tue, 3 Feb 2004 03:20:52 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

>-----Original Message-----
>From: Harold.Noffke at wpafb.af.mil [mailto:Harold.Noffke at wpafb.af.mil]
To: mathgroup at smc.vnet.net
>Sent: Monday, February 02, 2004 11:20 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg46022] [mg45992] Baffled By Underscore Pattern Matching
>
>
>MathGroup:
>
>In my study of Mathematica 5.0, I have reached "The Mathematica Book >
>Principals of Mathematica > Patterns > 2.3.8 Functions with Variable
>Numbers of Arguments".  The In[1]/Out[1] example I understand, but the
>In[2,3]/Out[3] example (discussed below) has me totally mystified.
>
>As printed, we have ...
>
>	In[2]:= h[a___, x_, b___, x_, c___] := hh[x] h[a, b, c]
>
>	In[3]:= h[2, 3, 2, 4, 5, 3]
>
>	Out[3]= h[4, 5] hh[2] hh[3]
>
>Now let's make a change to In[2] ...
>
>	In[4]:= Clear[h, hh]
>
>	In[5]:= h[a___, x_, b___, x_, c___] := hh[x] h[{a}, {b}, {c}]
>
>	In[6]:= h[2, 3, 2, 4, 5, 3]
>
>	Out[6]= h[{}, {3}, {4, 5, 3}] hh[2]
>
>I did a Trace on this pattern match problem, and found only that
>doublets were pulled out on each iteration.  In order to understand
>what is happening here, I think I need to understand the matching
>process at a level of granularity finer than Trace can supply.  I
>don"t have a clear mental picture of how In[5] manipulates the number
>stream which feeds into it from In[6].  I have no idea of how the
>In[6] lists came to contain the numbers they do.
>
>Any help, pointers to tutorial papers, or more illuminating examples
>will be greatly appreciated.
>
>Thanks.
>Harold
>

Perhaps things become clearer if you define

In[4]:= h[a___, x_, b___, x_, c___] := {hh[x], h[a, b, c]}

In[5]:= h[2, 3, 2, 4, 5, 3]
Out[5]= {hh[2], {hh[3], h[4, 5]}}

Here the two seperate steps of application of h become visible.

Pattern matching is not traced (as it doesn't go through the main evaluation
loop). However, you may study pattern matching more detailed with
ReplaceList (and fitting examples).

We use a different pattern, to see more (or anything) from the machinery:

In[21]:= Clear[h]
In[22]:= ReplaceList[h[2, 3, 2, 4, 5, 3],
h[a___, x_, b___, x2_, c___] :> {{a}, x, {b}, x2, {c}}]
Out[22]=
{{{}, 2, {}, 3, {2, 4, 5, 3}},
{{}, 2, {3}, 2, {4, 5, 3}},
{{2}, 3, {}, 2, {4, 5, 3}},
{{}, 2, {3, 2}, 4, {5, 3}},
{{2}, 3, {2}, 4, {5, 3}},
{{2, 3}, 2, {}, 4, {5, 3}},
{{}, 2, {3, 2, 4}, 5, {3}},
{{2}, 3, {2, 4}, 5, {3}},
{{2, 3}, 2, {4}, 5, {3}},
{{2, 3, 2}, 4, {}, 5, {3}},
{{}, 2, {3, 2, 4, 5}, 3, {}},
{{2}, 3, {2, 4, 5}, 3, {}},
{{2, 3}, 2, {4, 5}, 3, {}},
{{2, 3, 2}, 4, {5}, 3, {}},
{{2, 3, 2, 4}, 5, {}, 3, {}}}

>From this my guess is:

(1) try:
Pattern[a, BlankNullSequence[]]	matches to Sequence[]
Pattern[x, Blank[]]			matches to 2
Pattern[b, BlankNullSequence[]]	matches to Sequence[]
now 2 (value of pattern variable x)	does not match to 3 ==> fail

(2) retry:
Pattern[a, BlankNullSequence[]]	matches to Sequence[]
Pattern[x, Blank[]]			matches to 2
Pattern[b, BlankNullSequence[]]	matches to Sequence[]
2						matches to 2
Pattern[c, BlankNullSequence[]]	matches to Sequence[4,5,3]
==> success and the first transformation occurs, resulting in
{hh[2], h[3,4,5,3]}

Now term rewriting for the second element is initiated anew:

In[23]:= ReplaceList[h[3, 4, 5, 3],
h[a___, x_, b___, x2_, c___] :> {{a}, x, {b}, x2, {c}}]
Out[23]=
{{{}, 3, {}, 4, {5, 3}},
{{}, 3, {4}, 5, {3}},
{{3}, 4, {}, 5, {3}},
{{}, 3, {4, 5}, 3, {}},
{{3}, 4, {5}, 3, {}},
{{3, 4}, 5, {}, 3, {}}}

(1) try:
Pattern[a, BlankNullSequence[]]	matches to Sequence[]
Pattern[x, Blank[]]			matches to 3
Pattern[b, BlankNullSequence[]]	matches to Sequence[]
now 3 (value of pattern variable x)	does not match to 4 ==> fail

(2) retry:
Pattern[a, BlankNullSequence[]]	matches to Sequence[]
Pattern[x, Blank[]]			matches to 3
Pattern[b, BlankNullSequence[]]	matches to Sequence[4]
now 3 (value of pattern variable x)	does not match to 5 ==> fail

(3)
Pattern[a, BlankNullSequence[]]	matches to Sequence[3]
Pattern[x, Blank[]]			matches to 4
Pattern[b, BlankNullSequence[]]	matches to Sequence[]
now 3 (value of pattern variable x)	does not match to 5 ==> fail

(4)
Pattern[a, BlankNullSequence[]]	matches to Sequence[]
Pattern[x, Blank[]]			matches to 3
Pattern[b, BlankNullSequence[]]	matches to Sequence[4,5]
now 3 (value of pattern variable x)	matches to 3
Pattern[c, BlankNullSequence[]]	Matches to Sequence[]
==> success and the second transformation occurs, resulting in
{hh[3], h[4,5]}

Now term rewriting for the second element is initiated anew:

In[24]:=
ReplaceList[h[4, 5], h[a___, x_, b___, x2_, c___] :> {{a}, x, {b}, x2, {c}}]
Out[24]= {{{}, 4, {}, 5, {}}}

(1) try:
Pattern[a, BlankNullSequence[]]	matches to Sequence[]
Pattern[x, Blank[]]			matches to 4
Pattern[b, BlankNullSequence[]]	matches to Sequence[]
now 4 (value of pattern variable x)	does not match to 5 ==> fail

no substitution occurred and rewriting terminates.

However the Mathematica book is not too explicit with stating the sequences
of tries:

"When you use multiple blanks, there are often several matches that are
possible for a particular expression. In general, Mathematica tries first
those matches that assign the shortest sequences of arguments to the first
multiple blanks that appear in the pattern."

With this you can predict the sequence of matches with ReplaceList more
easily if you state that as this: the pattern sequences to the right are
most greedy, all matches are tried with them being longest, then they
reluctendly shorten for other possibel matches (with priority from right to
left).

The "explanations" I gave above are only illustrative, the actual machinery
is hidden to me. Perhaps first the BlankNullSequences and BlankSequences are
first arranged among the elements, before the pattern variables are checked.
Never mind, it would not change the sequence of tries.

--
Hartmut Wolf

• Prev by Date: Re: clarification. Re: one liner for a function?
• Next by Date: how to run a shell command in mathematica?
• Previous by thread: Re: Baffled By Underscore Pattern Matching
• Next by thread: Re: Baffled By Underscore Pattern Matching