Re: Re: Re: Re: Taking either a sequence or a list
- To: mathgroup at smc.vnet.net
- Subject: [mg63700] Re: [mg63617] Re: Re: Re: Taking either a sequence or a list
- From: "Oyvind Tafjord" <tafjord at wolfram.com>
- Date: Tue, 10 Jan 2006 01:48:56 -0500 (EST)
- References: <dnm29m$89q$1@smc.vnet.net> <dnopf9$2gp$1@smc.vnet.net> <dnrd16$kqf$1@smc.vnet.net> <200512231008.FAA25950@smc.vnet.net> <dp05eq$g3b$1@smc.vnet.net> <200512311140.GAA28014@smc.vnet.net> <dpg0vi$plt$1@smc.vnet.net> <200601070813.DAA07726@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
----- Original Message -----
From: "Maxim" <m.r at inbox.ru>
To: mathgroup at smc.vnet.net
Subject: [mg63700] [mg63617] Re: Re: Re: Taking either a sequence or a list
> On Wed, 4 Jan 2006 08:28:34 +0000 (UTC), Oyvind Tafjord
> <tafjord at wolfram.com> wrote:
>
>> ----- Original Message -----
>> From: "Maxim" <m.r at inbox.ru>
To: mathgroup at smc.vnet.net
>>> In[1]:= pset = Module[{f},
>>> Attributes[f] = {Flat, Orderless};
>>> ReplaceList[f @@ #, f[s___, s2___] -> {s}]
>>> ]&;
>>>
>>> In[2]:= pset[{1, 2, 3}]
>>>
>>> Out[2]= {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
>>>
>>> But should it work this way? Why doesn't it generate the list {2, 1} as
>>> well?
>>
>> This is yet another issue. The behavior is an important optimization to
>> save testing a lot of redundant possible matches. It does mean that only
>> the
>> sorted version of each sequence will be tried, but this is consistent
>> with
>> the general Orderless nature of the function involved.
>>
>
>>
>> You probably noticed that if you remove the Flat attribute, you'll get
>> many
>> more results. This optimization was for unknown reasons not there for
>> this
>> case (leading to slowness bugs being reported). For the next version,
>> only
>> sorted sequences will be tried in this case as well.
>>
>
>>
>> For a Flat+OneIdentity head f, a _ pattern will try things like 1,
>> f[1,2],
>> f[1,2,3], etc. On the other hand a __ pattern will try things like 1,
>> Sequence[1,2], Sequence[1,2,3]. I agree that writing up a more complete
>> documentation of these subtleties would be a good idea.
>>
>
> That's certainly interesting, thank you for the clarifications. It seems
> to imply that with the optimization which you mentioned the following
> function won't generate all permutations of a given list:
>
> In[1]:= perm = Module[{f},
> Attributes[f] = Orderless;
> ReplaceList[f @@ #, f[s__] -> {s}]
> ]&;
>
> In[2]:= perm[{1, 2, 3}]
>
> Out[2]= {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}}
>
> Mathematica 6 will simply return {{1, 2, 3}}, is that correct?
Correct.
>
> Also I think there are some other vague points related to ReplaceAll:
>
> In[3]:= Block[{f}, Attributes[f] = Flat;
> f[1, 2, 3] /. f[x__, y_] -> {x, y}]
>
> Out[3]= {1, f[2, 3]}
>
> In[4]:= Block[{f}, Attributes[f] = {Flat, Orderless};
> f[1, 2, 3] /. f[x__, y_] -> {x, y}]
>
> Out[4]= f[{1, f[2, 3]}]
>
> If Mathematica tries to regroup or reorder the arguments only at the
> places corresponding to Blank in the pattern, not BlankSequence, that
> explains why x is matched to 1, not f[1]. But where does the outer f in
> the second example come from?
These will both return {1,f[2,3]} in the next version.
>
> Besides, since a replacement such as f[g[a], g[b], 1] /. f[(_g)..] -> 0
> finds a match (when f is Flat), we cannot just say that Flat doesn't try
> substitutions for BlankSequence or Repeated -- ReplaceAll still tries to
> regroup the arguments even if there isn't a Blank pattern present, so I'm
> not sure how to formulate the general rule that would cover both cases.
The combinations with Repeated are a bit more complicated, although also
improved in the next version, although I'm not sure if this particular issue
will be addressed.
Oyvind Tafjord
Wolfram Research
>
> Maxim Rytin
> m.r at inbox.ru
- References:
- Re: Re: Re: Taking either a sequence or a list
- From: Maxim <m.r@inbox.ru>
- Re: Re: Re: Taking either a sequence or a list