Movatterモバイル変換
[0]ホーム
Comparison of cyclic objects (was RE: [Python-Dev] trashcan and PR#7)
Ka-Ping Yeeping@lfw.org
Thu, 13 Apr 2000 17:41:44 -0500 (CDT)
On Thu, 13 Apr 2000, Jeremy Hylton wrote:> >>>>> "TP" == Tim Peters <tim_one@email.msn.com> writes:>> TP> [Jeremy Hylton]>> >> So the real problem is defining some reasonable semantics for> >> comparison of recursive objects.There is a "right" way to do this, i believe, and my friendMark Miller implemented it in E.He tells me his algorithm is inspired by the method forunification of cyclic structures in Prolog III. It's availablein the E source code (in the file elib/tables/Equalizer.java).See interesting stuff on equality and cyclic data structures athttp://www.erights.org/javadoc/org/erights/e/elib/tables/Equalizer.htmlhttp://www.erights.org/elang/same-ref.htmlhttp://www.erights.org/elang/blocks/defVar.htmlhttp://www.eros-os.org/~majordomo/e-lang/0698.htmlThere is also a thread about equality issues in general at:http://www.eros-os.org/~majordomo/e-lang/0000.htmlIt's long, but worth perusing.Here is my rough Python translation of the code in the E Equalizer. Python 1.4 (Mar 25 2000) [C] Copyright 1991-1997 Stichting Mathematisch Centrum, Amsterdam Python Console v1.4 by Ka-Ping Yee <ping@lfw.org> >>> def same(left, right, sofar={}): ... hypothesis = (id(left), id(right)) ... if left is right or sofar.has_key(hypothesis): return 1 ... if type(left) is not type(right): return 0 ... if type(left) is type({}): ... left, right = left.items(), right.items() ... if type(left) is type([]): ... sofar[hypothesis] = 1 ... try: ... for i in range(len(left)): ... if not same(left[i], right[i], sofar): return 0 ... return 1 ... finally: ... del sofar[hypothesis] ... return left == right ... ... >>> same([3],[4]) 0 >>> same([3],[3]) 1 >>> a = [1,2,3] >>> b = [1,2,3] >>> c = [1,2,3] >>> same(a,b) 1 >>> a[1] = a >>> same(a,a) 1 >>> same(a,b) 0 >>> b[1] = b >>> same(a,b) 1 >>> b[1] = c >>> b [1, [1, 2, 3], 3] >>> same(a,b) 0 >>> c[1] = b >>> same(a,b) 1 >>> same(b,c) 1 >>> I would like to see Python's comparisons work this way (i.e."correct" as opposed to "we give up").-- ?!ng
[8]ページ先頭