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.