Re: Local scoping of pattern names in rules--or not
- To: mathgroup at smc.vnet.net
- Subject: [mg120645] Re: Local scoping of pattern names in rules--or not
- From: "Oleksandr Rasputinov" <oleksandr_rasputinov at hmamail.com>
- Date: Mon, 1 Aug 2011 06:58:06 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- References: <j15790$b5e$1@smc.vnet.net>
On Mon, 01 Aug 2011 04:41:20 +0100, Kris Carlson <carlsonkw at gmail.com> wrote: > Hi, > > I am writing a function to find the shortest paths from a source vertex > to a > target in a directed graph. The actual application of this is identifying > possible circuits in the spinal cord where an electrical stimulator > interferes with pain signals and alleviates the pain. To find direct > connections from source to target, even with 11K connections, is trivial, > but it's less so with intermediate nodes, variable path length in the # > of > vertices, and recurrence. I could not find a built-in shortest paths > function with variable path length, or in Combinatorica. If you know of > one > please let me know. > > Sometimes the local scoping in Rule and Cases works and sometimes not. > I'd > like to have a better understanding of this. Here is what Tech Support > wrote > me a while ago after some initial confusion about the cause and solution > themselves, and a toy example: > > Thank you for the email. I apologize for not providing explanations in my > notebook for what exactly Mathematica is doing. In fact I have figured > out > that it is not a problem with your variables being symbols or lists but > rather that of evaluating the Rule itself. For some reason, even when the > variables are locally scoped, Mathematica is evaluating their values > before > the rule is evaluated. Using a Rule Delayed (:>) solves this problem and > the results are as expected. I have inserted my comments/explanations in > the attached notebook. > > In[558]:= aList=Range[10];n=7; > > In[563]:= f1[list1_List]:=Module[{},Cases[aList,n_/;n>3->50]] > > f2[list1_List]:=Module[{},Cases[aList,n_->{a,n,b}]] (* local scoping > doesn't > work as intended *) > > In[565]:= f3[list1_List]:=Module[{},Cases[aList,n_:>{a,n,b}]] > > In[564]:= f1[aList] > > Out[564]= {50,50,50,50,50,50,50} > > In[562]:= f2[aList] > > Out[562]= > {{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b}} > > In[566]:= f3[aList] > > Out[566]= > {{a,1,b},{a,2,b},{a,3,b},{a,4,b},{a,5,b},{a,6,b},{a,7,b},{a,8,b},{a,9,b},{a,10,b}} > > Thanks, > > Kris Here Module is not the scoping construct; Condition and RuleDelayed are by virtue of their attributes. In fact Module performs no function here and we may omit it in the following. One problem with your code is that the definitions for f1 through f3 accept an argument but do not use this argument for anything since the value aList is hard-coded. However, this is a minor point, and the key to understanding the behaviour is in appreciating the role played by attributes in determining evaluation order. In[1] := aList=Range[10]; n=7; In[3] := Cases[aList, n_ /; n > 3 -> 50] (* f1 *) Out[3] = {50, 50, 50, 50, 50, 50, 50} I am not quite sure if this is what you intended; ReplaceAll used in place of Cases gives a different result that strikes me as more likely to be the one you had wanted. At any rate, even with Cases intact, this worked because Condition (with Condition[a, b] notated as a /; b) has attribute HoldAll. This is to say that none of the arguments are evaluated, i.e. they are all held, so we have Condition[n, n > 3], independently of the value defined for n. The lack of evaluation imparts lexical scoping behaviour because the arguments are, roughly speaking, treated as literals. Let us Trace the evaluation, which allows us to see how each expression is transformed into the next in order to produce the result: In[4] := Trace@In[3] Out[4] = { In[3], Cases[aList, n_ /; n > 3 -> 50], (* the input *) {aList,{1,2,3,4,5,6,7,8,9,10}}, {n_ /; n > 3 -> 50, n_ /; n > 3 -> 50}, (* evaluation of the arguments of Cases: note Cases does _not_ have attributes preventing this *) Cases[{1,2,3,4,5,6,7,8,9,10}, n_ /; n > 3 -> 50], (* the expression to be evaluated *) {1>3,False},{2>3,False},{3>3,False},{4>3,True},{5>3,True},{6>3,True},{7>3,True},{8>3,True},{9>3,True},{10>3,True}, (* evaluation of Condition for each of the elements to see whether they match *) {50,50,50,50,50,50,50} (* the result *) } Notice that the expression to be evaluated is still coherent after evaluation of the arguments. The identical argument applies to the case of RuleDelayed so I will not go over the same ground again. Let us instead contrast this behaviour against the situation with Rule (as opposed to RuleDelayed), which possesses no attributes that might inhibit evaluation in general; it only has SequenceHold which prevents transformations of the form {a,b,Sequence[c,d],e,f} -> {a,b,c,d,e,f}, with a through f all being evaluated: In[5] := Attributes[Rule] Out[5] = {Protected, SequenceHold} In[6] := Cases[aList,n_->{a,n,b}] (* f2 *) Out[6] = {{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b}} This worked, but not as you expected. To see why, again we Trace the evaluation: In[7] := Trace@In[6] Out[7] = { In[6], Cases[aList,n_->{a,n,b}], (* the input *) {aList,{1,2,3,4,5,6,7,8,9,10}}, {{{n,7},{a,7,b}},n_->{a,7,b},n_->{a,7,b}}, (* the arguments: here {a,n,b} is evaluated and thus transformed into {a,7,b} *) Cases[{1,2,3,4,5,6,7,8,9,10},n_->{a,7,b}], (* the expression to be evaluated. n_ matches all of the elements, and so they are all replaced by {a,7,b} *) {{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b},{a,7,b}} (* the result *) } Here the expression to be evaluated has become contaminated by extraneous values due to evaluation of the arguments of Rule before the substitution is made. Let us write the substitutions alone to make this clearer: In[8] := (* f1. Attributes[Condition] = {HoldAll, Protected} *) n_ /; n > 3 Out[8] = n_ /; n > 3 (* evidently, not evaluated, thanks to HoldAll *) In[9] := (* f2. Attributes[Rule] = {Protected, SequenceHold} *) n_ -> {a,n,b} Out[9] = n_ -> {a,7,b} (* evaluated, as Rule possesses no attributes preventing this *) In[10] := (* f3. Attributes[RuleDelayed] = {HoldRest, Protected, SequenceHold} *) n_ :> {a,n,b} Out[10] = n_ :> {a,n,b} (* again, unevaluated, this time due to HoldRest. Actually n_ has been evaluated because the first argument is not held by HoldRest, but a pattern cannot have a value and thus evaluates to itself *) Hopefully this clarifies things somewhat. I emphasize "somewhat", because evaluation order in Mathematica can be rather a complex subject and it is a frequent source of confusion. Best, O. R.