Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Why does the order of down values come back?
10 views
Skip to first unread message
Shizu
Feb 6, 2012, 2:45:13 AM2/6/12
to
In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
In[]:= DownValues[f]
Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
In[]:= DownValues[f] = Reverse[DownValues[f]]
Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] :> 1, HoldPattern[f[0]] :> 0}
In[]:= DownValues[f]
Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
====================================================
My question is:
Why does the order of down values comes back after reordering?
Thanks.
In[]:= DownValues[f]
Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
In[]:= DownValues[f] = Reverse[DownValues[f]]
Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] :> 1, HoldPattern[f[0]] :> 0}
In[]:= DownValues[f]
Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
====================================================
My question is:
Why does the order of down values comes back after reordering?
Thanks.
Shizu
Feb 7, 2012, 4:01:41 AM2/7/12
to
In[]:= g[x_ + y_] := op1[x, y]; g[x_ y_] := op2[x, y]
In[]:= DownValues[g]
Out[]:= {HoldPattern[g[x_ + y_]] :> op1[x, y], HoldPattern[g[x_ y_]] :> op2[x, y]}
In[]:= DownValues[g] = Reverse[DownValues[g]]
Out[]:= {HoldPattern[g[x_ y_]] :> op2[x, y], HoldPattern[g[x_ + y_]] :> op1[x, y]}
In[]:= DownValues[g]
Out[]:= {HoldPattern[g[x_ y_]] :> op2[x, y], HoldPattern[g[x_ + y_]] :> op1[x, y]}
===================================================
What I did here does NOT make sense either.
But after reordering, the original order doesn't come back.
This one is predictable.
Actually, we can even define the previous function as follows:
In[]:= f[n_] := f[n - 1] + f[n - 2];
f[1] := 1;
f[0] := 0;
In[]:= f[10]
Out[]:= 55
The order we set up the function is not important.
Any comments?
Thanks.
In[]:= DownValues[g]
Out[]:= {HoldPattern[g[x_ + y_]] :> op1[x, y], HoldPattern[g[x_ y_]] :> op2[x, y]}
In[]:= DownValues[g] = Reverse[DownValues[g]]
Out[]:= {HoldPattern[g[x_ y_]] :> op2[x, y], HoldPattern[g[x_ + y_]] :> op1[x, y]}
In[]:= DownValues[g]
Out[]:= {HoldPattern[g[x_ y_]] :> op2[x, y], HoldPattern[g[x_ + y_]] :> op1[x, y]}
===================================================
What I did here does NOT make sense either.
But after reordering, the original order doesn't come back.
This one is predictable.
Actually, we can even define the previous function as follows:
In[]:= f[n_] := f[n - 1] + f[n - 2];
f[1] := 1;
f[0] := 0;
In[]:= f[10]
Out[]:= 55
The order we set up the function is not important.
Any comments?
Thanks.
David Reiss
Feb 7, 2012, 4:06:24 AM2/7/12
to
Options[DownValues]={Sort->True}
--David
On Feb 6, 2:45 am, Shizu <slivo.v...@msa.hinet.net> wrote:
> In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> In[]:= DownValues[f] = Reverse[DownValues[f]]
> Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] :=
--David
On Feb 6, 2:45 am, Shizu <slivo.v...@msa.hinet.net> wrote:
> In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> In[]:= DownValues[f] = Reverse[DownValues[f]]
> 1, HoldPattern[f[0]] :> 0}
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> =========================
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> =========================
David Reiss
Feb 7, 2012, 4:07:57 AM2/7/12
to
Sorry for my previous suggestion... What appears to be happening is
that DownValues (even if you set Sort->False) will continue to order
the rules based on which seems to be more general with the special
cases first and the more general patterns afterwards.
that DownValues (even if you set Sort->False) will continue to order
the rules based on which seems to be more general with the special
cases first and the more general patterns afterwards.
> In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> In[]:= DownValues[f] = Reverse[DownValues[f]]
> Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] :=
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> In[]:= DownValues[f] = Reverse[DownValues[f]]
> 1, HoldPattern[f[0]] :> 0}
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> =========================
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1, HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> =========================
Oleksandr Rasputinov
Feb 7, 2012, 4:08:58 AM2/7/12
to
not, however, sorted; the order is as you set them. To see their actual
order, use the (undocumented) option:
DownValues[f, Sort -> False]
DrMajorBob
Feb 7, 2012, 4:11:01 AM2/7/12
to
More specific patterns always come first.
In your example, especially, it would make NO sense to put them in the
order you tried.
Bobby
On Mon, 06 Feb 2012 01:38:08 -0600, Shizu <slivo...@msa.hinet.net> wrote:
> In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1,
> HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> In[]:= DownValues[f] = Reverse[DownValues[f]]
> Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] :>
> 1, HoldPattern[f[0]] :> 0}
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1,
> HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> ====================================================
> My question is:
>
> Why does the order of down values comes back after reordering?
>
> Thanks.
>
--
DrMaj...@yahoo.com
In your example, especially, it would make NO sense to put them in the
order you tried.
Bobby
On Mon, 06 Feb 2012 01:38:08 -0600, Shizu <slivo...@msa.hinet.net> wrote:
> In[]:= f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1,
> HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> In[]:= DownValues[f] = Reverse[DownValues[f]]
> Out[]:= {HoldPattern[f[n_]] :> f[n - 1] + f[n - 2], HoldPattern[f[1]] :>
> 1, HoldPattern[f[0]] :> 0}
>
> In[]:= DownValues[f]
> Out[]:= {HoldPattern[f[0]] :> 0, HoldPattern[f[1]] :> 1,
> HoldPattern[f[n_]] :> f[n - 1] + f[n - 2]}
>
> ====================================================
> My question is:
>
> Why does the order of down values comes back after reordering?
>
> Thanks.
>
DrMaj...@yahoo.com
DrMajorBob
Feb 8, 2012, 5:29:51 AM2/8/12
to
I suspect the unsorted version is irrelevant, however, in that when
f[something] is evaluated, rules will be tested from most specific to
least.
Bobby
On Tue, 07 Feb 2012 03:05:34 -0600, Oleksandr Rasputinov
<oleksandr_...@ymail.com> wrote:
> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo...@msa.hinet.net>
> wrote:
>
DrMaj...@yahoo.com
f[something] is evaluated, rules will be tested from most specific to
least.
Bobby
On Tue, 07 Feb 2012 03:05:34 -0600, Oleksandr Rasputinov
<oleksandr_...@ymail.com> wrote:
> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo...@msa.hinet.net>
> wrote:
>
> Because DownValues sorts its output by default. The actual downvalues are
> not, however, sorted; the order is as you set them. To see their actual
> order, use the (undocumented) option:
>
> DownValues[f, Sort -> False]
>
--
> not, however, sorted; the order is as you set them. To see their actual
> order, use the (undocumented) option:
>
> DownValues[f, Sort -> False]
>
DrMaj...@yahoo.com
Leonid Shifrin
Feb 8, 2012, 5:32:55 AM2/8/12
to
A more precise statement would be that DownValues with Sort->False do not
perform additional sorting,
and presumably expose the content of the rules just as they are kept in the
underlying hash-table. This does not however mean that they will come in
the order they were entered - since generally hash-table (at least the one
used to implement DownValues) does not guarantee you that. This happens to
be true for a small number of key-value pairs, but not in general. Try, for
example, this:
f[x_] := f[x] = x;
f /@ Range[100]
and then inspect the DownValues of f. Here is one relevant discussion I am
aware of:
http://stackoverflow.com/questions/7062268/what-sort-option-of-values-does/7063143#7063143
Cheers,
Leonid
On Tue, Feb 7, 2012 at 12:05 PM, Oleksandr Rasputinov <
perform additional sorting,
and presumably expose the content of the rules just as they are kept in the
underlying hash-table. This does not however mean that they will come in
the order they were entered - since generally hash-table (at least the one
used to implement DownValues) does not guarantee you that. This happens to
be true for a small number of key-value pairs, but not in general. Try, for
example, this:
f[x_] := f[x] = x;
f /@ Range[100]
and then inspect the DownValues of f. Here is one relevant discussion I am
aware of:
http://stackoverflow.com/questions/7062268/what-sort-option-of-values-does/7063143#7063143
Cheers,
Leonid
On Tue, Feb 7, 2012 at 12:05 PM, Oleksandr Rasputinov <
oleksandr_...@ymail.com> wrote:
> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo...@msa.hinet.net>
> wrote:
>
> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo...@msa.hinet.net>
> wrote:
>
Oleksandr Rasputinov
Feb 9, 2012, 5:39:53 AM2/9/12
to
A very good point. To tell the truth, the only time I've ever had to worry
about the order of DownValues is when there is some ambiguity in their
ordering, so I had never noticed the ordering based on position in the
hash table of those values for which the hash is sufficient to completely
specify the way in which they are applied. It would be interesting to know
to what extent the hash table (or tables, if multiple levels of hashing
are applied, as one might anticipate from the statements about ordering
based on specificity) is used in the resolution of more complicated
DownValues and at which point the process reduces to a sequential test for
applicability by pattern matching (i.e., when the ordering begins to
matter). Perhaps this can be determined by experiment?
Best,
O. R.
On Wed, 08 Feb 2012 10:32:55 -0000, Leonid Shifrin <lsh...@gmail.com>
wrote:
about the order of DownValues is when there is some ambiguity in their
ordering, so I had never noticed the ordering based on position in the
hash table of those values for which the hash is sufficient to completely
specify the way in which they are applied. It would be interesting to know
to what extent the hash table (or tables, if multiple levels of hashing
are applied, as one might anticipate from the statements about ordering
based on specificity) is used in the resolution of more complicated
DownValues and at which point the process reduces to a sequential test for
applicability by pattern matching (i.e., when the ordering begins to
matter). Perhaps this can be determined by experiment?
Best,
O. R.
On Wed, 08 Feb 2012 10:32:55 -0000, Leonid Shifrin <lsh...@gmail.com>
wrote:
Christoph Lhotka
Feb 10, 2012, 6:00:27 AM2/10/12
to
hi,
On 02/09/2012 11:37 AM, Oleksandr Rasputinov wrote:
> A very good point. To tell the truth, the only time I've ever had to worry
> about the order of DownValues is when there is some ambiguity in their
> ordering, so I had never noticed the ordering based on position in the
> hash table of those values for which the hash is sufficient to completely
> specify the way in which they are applied. It would be interesting to know
> to what extent the hash table (or tables, if multiple levels of hashing
> are applied, as one might anticipate from the statements about ordering
> based on specificity) is used in the resolution of more complicated
> DownValues and at which point the process reduces to a sequential test for
> applicability by pattern matching (i.e., when the ordering begins to
> matter). Perhaps this can be determined by experiment?
It is an interesting problem to find out how the order of downvalues
changes the results. You can make your own experiments like I did below:
f[0] := 0; f[1] := 1; f[n_] := f[n - 1] + f[n - 2]
dvl = Permutations[DownValues[f]] /. f -> cf;
cf[n] /. dvl
{cf[-2 + n] + cf[-1 + n], cf[-2 + n] + cf[-1 + n],
cf[-2 + n] + cf[-1 + n], cf[-2 + n] + cf[-1 + n],
cf[-2 + n] + cf[-1 + n], cf[-2 + n] + cf[-1 + n]}
cf[1] /. dvl
{1, cf[-1] + cf[0], 1, 1, cf[-1] + cf[0], cf[-1] + cf[0]}
cf[0] /. dvl
{0, 0, 0, cf[-2] + cf[-1], cf[-2] + cf[-1], cf[-2] + cf[-1]}
As you see, I produced a table of all possible permutations
of the internal rules for f named dvl and replaced f by a copy
of it called cf to avoid the acting of the internal evaluation
chain (you could also clear f after the definition of dvl).
The output shows in which way the ordering matters for
cf[n], cf[1], cf[0] (i.e. also for f[n], f[1], f[0]).
Wolfram did a good choice.
Best,
Christoph
On 02/09/2012 11:37 AM, Oleksandr Rasputinov wrote:
> A very good point. To tell the truth, the only time I've ever had to worry
> about the order of DownValues is when there is some ambiguity in their
> ordering, so I had never noticed the ordering based on position in the
> hash table of those values for which the hash is sufficient to completely
> specify the way in which they are applied. It would be interesting to know
> to what extent the hash table (or tables, if multiple levels of hashing
> are applied, as one might anticipate from the statements about ordering
> based on specificity) is used in the resolution of more complicated
> DownValues and at which point the process reduces to a sequential test for
> applicability by pattern matching (i.e., when the ordering begins to
> matter). Perhaps this can be determined by experiment?
changes the results. You can make your own experiments like I did below:
f[0] := 0; f[1] := 1; f[n_] := f[n - 1] + f[n - 2]
cf[n] /. dvl
{cf[-2 + n] + cf[-1 + n], cf[-2 + n] + cf[-1 + n],
cf[-2 + n] + cf[-1 + n], cf[-2 + n] + cf[-1 + n],
cf[-2 + n] + cf[-1 + n], cf[-2 + n] + cf[-1 + n]}
cf[1] /. dvl
{1, cf[-1] + cf[0], 1, 1, cf[-1] + cf[0], cf[-1] + cf[0]}
cf[0] /. dvl
{0, 0, 0, cf[-2] + cf[-1], cf[-2] + cf[-1], cf[-2] + cf[-1]}
As you see, I produced a table of all possible permutations
of the internal rules for f named dvl and replaced f by a copy
of it called cf to avoid the acting of the internal evaluation
chain (you could also clear f after the definition of dvl).
The output shows in which way the ordering matters for
cf[n], cf[1], cf[0] (i.e. also for f[n], f[1], f[0]).
Wolfram did a good choice.
Best,
Christoph
Shizu
Feb 11, 2012, 3:45:44 PM2/11/12
to
> ......Perhaps this can be determined by experiment?
>
> Best,
>
> O. R.
Yeah, that's it.
We may expect a rigorous and complete documentation of the core language.
Thank you, all the bright people who tried to help me understand something.
You are wonderful.
>
> Best,
>
> O. R.
Yeah, that's it.
We may expect a rigorous and complete documentation of the core language.
Thank you, all the bright people who tried to help me understand something.
You are wonderful.
Leonid Shifrin
Feb 11, 2012, 3:43:05 PM2/11/12
to
Best I can tell, only the rules with non-patterns (no Pattern-s, no blanks,
etc) are directly based on hash-tables. And, these are the only rules which ignore manual reordering of the relevant ...Values. Rules with patterns and / or blanks are most likely also hashed in some way for speed, but their order can be manually changed, and my impression was that they come in their original order indeed, when using Sort->False. I may be wrong however, did not do extensive checks on that.
Cheers,
Leonid
On Thu, Feb 9, 2012 at 1:37 PM, Oleksandr Rasputinov <
oleksandr_...@ymail.com> wrote:
> A very good point. To tell the truth, the only time I've ever had to worry
> about the order of DownValues is when there is some ambiguity in their
> ordering, so I had never noticed the ordering based on position in the
> hash table of those values for which the hash is sufficient to completely
> specify the way in which they are applied. It would be interesting to know
> to what extent the hash table (or tables, if multiple levels of hashing
> are applied, as one might anticipate from the statements about ordering
> based on specificity) is used in the resolution of more complicated
> DownValues and at which point the process reduces to a sequential test for
> applicability by pattern matching (i.e., when the ordering begins to
> matter). Perhaps this can be determined by experiment?
>
> Best,
>
> O. R.
>
etc) are directly based on hash-tables. And, these are the only rules which ignore manual reordering of the relevant ...Values. Rules with patterns and / or blanks are most likely also hashed in some way for speed, but their order can be manually changed, and my impression was that they come in their original order indeed, when using Sort->False. I may be wrong however, did not do extensive checks on that.
Cheers,
Leonid
On Thu, Feb 9, 2012 at 1:37 PM, Oleksandr Rasputinov <
oleksandr_...@ymail.com> wrote:
> A very good point. To tell the truth, the only time I've ever had to worry
> about the order of DownValues is when there is some ambiguity in their
> ordering, so I had never noticed the ordering based on position in the
> hash table of those values for which the hash is sufficient to completely
> specify the way in which they are applied. It would be interesting to know
> to what extent the hash table (or tables, if multiple levels of hashing
> are applied, as one might anticipate from the statements about ordering
> based on specificity) is used in the resolution of more complicated
> DownValues and at which point the process reduces to a sequential test for
> applicability by pattern matching (i.e., when the ordering begins to
>
> Best,
>
> O. R.
>
A Retey
Feb 11, 2012, 3:48:18 PM2/11/12
to
Hi,
I'm sure that you (Oleksandr) are aware of it, but I doubt the OP is:
there are actually two sorting activities involved:
1) whenever you add to or change the DownValues, they will be sorted so
that more specific patterns will be tried before more general ones. I
don't think there is any way to circumvent this, which probably is
because the pattern matcher does somehow rely on it.
2) when using DownValues to show what's there, the patterns are by
default not shown as stored, but are again sorted. This can be avoided
by using the Sort option. I guess this is supposed to make it easier to
compare lists of DownValues which would behave identically when used by
the pattern matcher. AFAIK this sorting will preserve the specific
before general rule.
In consequence, for your example
f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
Reverse. In cases where it's not possible to decide about which pattern
is more specific, it is the order in which you evaluate your definitions
that defines the order in which they are tried (and listed by
DownValues), compare e.g.:
ClearAll[g]
g[x_, 1] := 1
g[1, y_] := 2
g[1,1]
ClearAll[g]
g[1, y_] := 2
g[x_, 1] := 1
g[1,1]
hth,
albert
there are actually two sorting activities involved:
1) whenever you add to or change the DownValues, they will be sorted so
that more specific patterns will be tried before more general ones. I
don't think there is any way to circumvent this, which probably is
because the pattern matcher does somehow rely on it.
2) when using DownValues to show what's there, the patterns are by
default not shown as stored, but are again sorted. This can be avoided
by using the Sort option. I guess this is supposed to make it easier to
compare lists of DownValues which would behave identically when used by
the pattern matcher. AFAIK this sorting will preserve the specific
before general rule.
In consequence, for your example
f[0] := 0;f[1] := 1;f[n_] := f[n - 1] + f[n - 2]
DownValues[f] = Reverse[DownValues[f]]
DownValues[f, Sort -> False]
will still list the most general pattern as last entry, despite the
Reverse. In cases where it's not possible to decide about which pattern
is more specific, it is the order in which you evaluate your definitions
that defines the order in which they are tried (and listed by
DownValues), compare e.g.:
ClearAll[g]
g[x_, 1] := 1
g[1, y_] := 2
g[1,1]
ClearAll[g]
g[1, y_] := 2
g[x_, 1] := 1
g[1,1]
hth,
albert
0 new messages