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