Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #8358 > unrolled thread

Why does the order of down values come back?

Started byShizu <slivo.vitz@msa.hinet.net>
First post2012-02-06 07:45 +0000
Last post2012-02-11 20:43 +0000
Articles 10 — 7 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  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

#8358 — Why does the order of down values come back?

FromShizu <slivo.vitz@msa.hinet.net>
Date2012-02-06 07:45 +0000
SubjectWhy 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]


#8368

FromDavid Reiss <dbreiss@gmail.com>
Date2012-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]


#8376

FromDavid Reiss <dbreiss@gmail.com>
Date2012-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]


#8379

From"Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com>
Date2012-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]


#8477

FromA Retey <awnl@gmx-topmail.de>
Date2012-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]


#8390

FromDrMajorBob <btreat1@austin.rr.com>
Date2012-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]


#8396

FromLeonid Shifrin <lshifr@gmail.com>
Date2012-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]


#8429

From"Oleksandr Rasputinov" <oleksandr_rasputinov@ymail.com>
Date2012-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]


#8454

FromChristoph Lhotka <christoph.lhotka@fundp.ac.be>
Date2012-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]


#8464

FromLeonid Shifrin <lshifr@gmail.com>
Date2012-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