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 >