Re: Re: Re: Taking either a sequence or a list
- To: mathgroup at smc.vnet.net
- Subject: [mg63539] Re: [mg63432] Re: Re: Taking either a sequence or a list
- From: "Oyvind Tafjord" <tafjord at wolfram.com>
- Date: Wed, 4 Jan 2006 03:17:17 -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>
- Sender: owner-wri-mathgroup at wolfram.com
----- Original Message -----
From: "Maxim" <m.r at inbox.ru>
To: mathgroup at smc.vnet.net
Subject: [mg63539] [mg63432] Re: Re: Taking either a sequence or a list
> On Thu, 29 Dec 2005 08:06:50 +0000 (UTC), Oyvind Tafjord
> <tafjord at wolfram.com> wrote:
>
>> ----- Original Message -----
>> From: "Maxim" <m.r at inbox.ru>
To: mathgroup at smc.vnet.net
>> Subject: [mg63539] [mg63432] Re: Taking either a sequence or a list
>>
>>
>>>>
>>>> This definitely looks like an inconsistency:
>>>>
>>>> In[1]:= MatchQ[{a}, {__Integer | a}]
>>>>
>>>> Out[1]= True
>>>>
>>>> In[2]:= MatchQ[{a}, {x : __Integer | a}]
>>>>
>>>> Out[2]= False
>>
>> This is a known issue (inconsistent handling of Alternatives) which is
>> fixed
>> in future versions.
>>
>>>>
>>>> It is also unclear exactly what value is assigned to x here:
>>>>
>>>> In[4]:= tmp = {a} /. {x : __} -> x
>>>>
>>>> Out[4]= a
>>>>
>>>> In[5]:= tmp2 = {a} /. {x : __ | __} -> x
>>>>
>>>> Out[5]= Sequence[a]
>>
>> The result should be "a" in both cases (don't wrap Sequence around
>> single-element sequences), fixed in future versions (by the same fix as
>> the
>> above).
>>
>>>>
>>>
>>> Here's another curious inconsistency:
>>>
>>> In[1]:= MatchQ[{a, a}, {s_, s_} /; True /; False]
>>>
>>> Out[1]= False
>>>
>>> In[2]:= MatchQ[{a, a}, {s__, s__} /; True /; False]
>>>
>>> Out[2]= True
>>
>> This is a bug I haven't seen before, involving nested
>> Conditions/PatternTests surrounding "non-unique" patterns. Will be fixed
>> in
>> future versions. Thanks for pointing it out.
>>
>> Oyvind Tafjord
>> Wolfram Research
>>
>
> In fact, I posted a very similar example (with nested Condition`s) on
> MathGroup more than two years ago:
> http://forums.wolfram.com/mathgroup/archive/2003/Oct/msg00429.html .
Thanks, I missed this post when recently trying to do a search for pattern
matcher issues before doing some maintenance work on the pattern matcher
code.
>
> One problem is that if we need to know whether the result should be a or
> Sequence[a], we cannot find the answer in the documentation. So even if we
> know that {a} /. {x : __ | __} -> x will return a, does it mean that
>
> {a, b, c} /. {s__, s2__} -> s
>
> will be 'fixed' too (currently it also returns Sequence[a])? If that it
> also a bug, this time it doesn't involve Alternative.
Yes, I believe the consistent thing to do is to never wrap Sequence around
single element sequences, so that will be the new behavior.
>
> Or if {a} /. {x : __Integer | a} -> 0 is going to be fixed, does it mean
> that
>
> a + b + c /. s : a + b -> 0
>
> will work differently as well (here we also have an example where the
> pattern name changes the outcome)?
This is an unrelated issue, but also one that will be "fixed" in the next
version. Previously, Mathematica didn't look "underneath" pattern elements
to see if the head is Flat. Whether you call it a bug or not, it seems
inconsistent and will be changed.
>
> And these are relatively simple cases, where the inconsistency can be
> pointed out quite unambiguously -- the contradiction between two examples
> is obvious. But sometimes we can't even be sure what the expected
> behaviour is. For example, the following function generates all subsets of
> a list:
>
> 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.
> The general idea behind patterns containing Orderless/Flat functions
> is that the expression is rearranged in all the ways allowed by the
> attributes, and each variant is checked against the pattern. But then f[2,
> 1, 3] is a perfectly legal rearrangement, f being Orderless. Moreover, we
> might expect to get f[1, 2] as one of the possible matches for s as well,
> because f is Flat and so f[1, 2, 3] is identical to f[f[1, 2], f[3]]. So
> exactly what combinations does Mathematica try here? I think that either
> the behaviour of Flat has to be changed, or we have to document quite a
> lot of complicated rules describing how Flat works in combination with
> Orderless, in combination with sequences, etc.
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.
Oyvind Tafjord
Wolfram Research
>
> Maxim Rytin
> m.r at inbox.ru