Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Why does the order of down values come back?

• To: mathgroup at smc.vnet.net
• Subject: [mg124842] Re: Why does the order of down values come back?
• From: "Oleksandr Rasputinov" <oleksandr_rasputinov at ymail.com>
• Date: Thu, 9 Feb 2012 05:37:39 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• References: <jgo0e9$a2k$1@smc.vnet.net> <jgtj0n$6dc$1@smc.vnet.net>

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 at 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 at ymail.com> wrote:
>
>> On Mon, 06 Feb 2012 07:45:13 -0000, Shizu <slivo.vitz at 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]
>>

• Follow-Ups:
  • Re: Why does the order of down values come back?
    • From: Christoph Lhotka <christoph.lhotka@fundp.ac.be>