Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #8358 > unrolled thread
| Started by | Shizu <slivo.vitz@msa.hinet.net> |
|---|---|
| First post | 2012-02-06 07:45 +0000 |
| Last post | 2012-02-11 20:43 +0000 |
| Articles | 10 — 7 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
Why does the order of down values come back? Shizu <slivo.vitz@msa.hinet.net> - 2012-02-06 07:45 +0000
Re: Why does the order of down values come back? David Reiss <dbreiss@gmail.com> - 2012-02-07 09:06 +0000
Re: Why does the order of down values come back? David Reiss <dbreiss@gmail.com> - 2012-02-07 09:07 +0000
Re: Why does the order of down values come back? "Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com> - 2012-02-07 09:08 +0000
Re: Why does the order of down values come back? A Retey <awnl@gmx-topmail.de> - 2012-02-11 20:48 +0000
Re: Why does the order of down values come back? DrMajorBob <btreat1@austin.rr.com> - 2012-02-08 10:29 +0000
Re: Why does the order of down values come back? Leonid Shifrin <lshifr@gmail.com> - 2012-02-08 10:32 +0000
Re: Why does the order of down values come back? "Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com> - 2012-02-09 10:39 +0000
Re: Why does the order of down values come back? Christoph Lhotka <christoph.lhotka@fundp.ac.be> - 2012-02-10 11:00 +0000
Re: Why does the order of down values come back? Leonid Shifrin <lshifr@gmail.com> - 2012-02-11 20:43 +0000
| From | Shizu <slivo.vitz@msa.hinet.net> |
|---|---|
| Date | 2012-02-06 07:45 +0000 |
| Subject | Why does the order of down values come back? |
| Message-ID | <jgo0e9$a2k$1@smc.vnet.net> |
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.
[toc] | [next] | [standalone]
| From | David Reiss <dbreiss@gmail.com> |
|---|---|
| Date | 2012-02-07 09:06 +0000 |
| Message-ID | <jgqpig$mvj$1@smc.vnet.net> |
| In reply to | #8358 |
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]] :=
> 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.
[toc] | [prev] | [next] | [standalone]
| From | David Reiss <dbreiss@gmail.com> |
|---|---|
| Date | 2012-02-07 09:07 +0000 |
| Message-ID | <jgqpld$n0d$1@smc.vnet.net> |
| In reply to | #8358 |
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.
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]] :=
> 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.
[toc] | [prev] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com> |
|---|---|
| Date | 2012-02-07 09:08 +0000 |
| Message-ID | <jgqpna$n12$1@smc.vnet.net> |
| In reply to | #8358 |
On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz@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.
>
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]
[toc] | [prev] | [next] | [standalone]
| From | A Retey <awnl@gmx-topmail.de> |
|---|---|
| Date | 2012-02-11 20:48 +0000 |
| Message-ID | <jh6k6i$jrn$1@smc.vnet.net> |
| In reply to | #8379 |
Hi,
>> 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.
>>
>
> 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]
>
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]
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
[toc] | [prev] | [next] | [standalone]
| From | DrMajorBob <btreat1@austin.rr.com> |
|---|---|
| Date | 2012-02-08 10:29 +0000 |
| Message-ID | <jgtiqv$6a9$1@smc.vnet.net> |
| In reply to | #8358 |
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_rasputinov@ymail.com> wrote:
> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz@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.
>>
>
> 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]
>
--
DrMajorBob@yahoo.com
[toc] | [prev] | [next] | [standalone]
| From | Leonid Shifrin <lshifr@gmail.com> |
|---|---|
| Date | 2012-02-08 10:32 +0000 |
| Message-ID | <jgtj0n$6dc$1@smc.vnet.net> |
| In reply to | #8358 |
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 <
oleksandr_rasputinov@ymail.com> wrote:
> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz@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.
> >
>
> 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]
>
>
[toc] | [prev] | [next] | [standalone]
| From | "Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com> |
|---|---|
| Date | 2012-02-09 10:39 +0000 |
| Message-ID | <jh07pp$hu3$1@smc.vnet.net> |
| In reply to | #8396 |
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 <lshifr@gmail.com>
wrote:
> 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 <
> oleksandr_rasputinov@ymail.com> wrote:
>
>> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz@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.
>> >
>>
>> 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]
>>
[toc] | [prev] | [next] | [standalone]
| From | Christoph Lhotka <christoph.lhotka@fundp.ac.be> |
|---|---|
| Date | 2012-02-10 11:00 +0000 |
| Message-ID | <jh2tcb$rg$1@smc.vnet.net> |
| In reply to | #8396 |
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
[toc] | [prev] | [next] | [standalone]
| From | Leonid Shifrin <lshifr@gmail.com> |
|---|---|
| Date | 2012-02-11 20:43 +0000 |
| Message-ID | <jh6jsp$jqf$1@smc.vnet.net> |
| In reply to | #8358 |
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_rasputinov@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.
>
> On Wed, 08 Feb 2012 10:32:55 -0000, Leonid Shifrin <lshifr@gmail.com>
> wrote:
>
> > 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 <
> > oleksandr_rasputinov@ymail.com> wrote:
> >
> >> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz@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.
> >> >
> >>
> >> 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]
> >>
>
>
[toc] | [prev] | [standalone]
Back to top | Article view | comp.soft-sys.math.mathematica
csiph-web