Re: Re: Re: Re: logical inconsistency in Union
- To: mathgroup at smc.vnet.net
- Subject: [mg13437] Re: [mg13256] Re: [mg13194] Re: [mg13109] Re: [mg13069] logical inconsistency in Union
- From: "Jurgen Tischer" <jtischer at col2.telecom.com.co>
- Date: Thu, 23 Jul 1998 03:33:36 -0400
- Sender: owner-wri-mathgroup at wolfram.com
Hi David,
as you note I was chewing on your message for quite a while. I don't
agree completely with you but I accept I didn't explain my point
enough. So let me try to fill in what I left out.
I think we agree that consistency is one of the most important design
principles of Mathematica.
Now Union is about sets, and sets are defined (I mean in naive set
theory) by the membership relation. So it sounds reasonable for me to
look at MemberQ, and what I see is no comparison function but a
pattern, or as far as I understand those things, the sameness so
defined is an equivalent relation.
Now look how Union is implemented. (I hope I interpreted correctly what
is said at the Wolfram webside.)
In[37]:= Union[{3,1,2,2,2},
SameTest->(With[{test=OrderedQ[{#1,#2}]},Print[{#1,#2,test}];test]&)]
{2,1,False}
{2,2,True}
{2,2,True}
{3,2,False}
Out[37]= {1,2,3}
So what Union (in it's default version) is using is the canonical
ordering to establish sameness and as it is to expected in a clever and
optimized way: first the list is ordered and then an element is
compared with the next ones using the backward order as long as the
answer is True. This last affirmation can be seen with
In[39]:=
Union[{1,2,3},SameTest->(With[{test=Abs[#1-#2]<1.1},Print[{#1,#2,test}];test
]&)]
{2,1,True}
{3,1,False}
Out[39]= {1,3}
This last example also shows that the "innocent" example of Veit Elser
wasn't really so innocent: his SameTest wasn't an equivalence relation.
I doubt Daniel's fix could do anything good with my example. The only
way I can see to press a SameTest like the above in something useful
would be to take transitive hulls, and of course you can not accomplish
this with "a brute-force comparison of every candidate element with all
elements already in the set under construction". But again I doubt that
this should be included into the functionality of a Union function.
Ok, I think that's all. If you now consider my union4, it just defines
an equivalent relation by a definition of a normal form (I shouldn't
have called it crit, but proy), another design principle of Mathematica
(BOOK, 3rd ed, p. 306, below the inset. :-))
Jurgen
P.S. I like it, and speed comparisons are fun.
-----Original Message-----
From: David Withoff <withoff at wolfram.com> To: mathgroup at smc.vnet.net
Subject: [mg13437] [mg13256] Re: [mg13194] Re: [mg13109] Re: [mg13069] logical
inconsistency in Union
>> Hi David,
>>
>> this union1 is so awfully slow, so I tried to speed it up a bit. I
>> suppos~d
>> that two elements are considered equal if they give the same result to a
>> criterion crit. My union4 is quite a bit faster even than union3 of
>> Union.html.
>>
>> union4[p_List,crit_]:= Module[{result,link,new},
>> result = link[];
>> new[_] = True;
>> Table[If[new[crit[p[[n]]]],new[crit[p[[n]]]]= False;
>> result=link[result,p[[n]]]],{n,Length[p]}];
>> List@@Flatten[result,\[Infinity],link]]
>>
>> I hope you like it.
>>
>> J|rgen
>
>This is an interesting definition, but it doesn't implement the same
>functionality as the other functions, speed comparisons aren't very
>meaningful. The test function "crit" in the definition of union4 isn't
>a general comparison function. It takes one argument, not two, and so
>doesn't provide for general comparison of elements as in the value of
>the SameTest option in Union. The comparison test that is effectively
>used here is the comparison that is used inside Mathematica to decide
>whether or not to apply a rule, after applying the value of "crit" to
>each expression.
>
>This program really does illustrate an interesting strategy, but it
>isn't a general Union function.
>
>Dave Withoff
>Wolfram Research
>