Comparison of cyclic objects (was RE: [Python-Dev] trashcan and PR#7)

[Ka-Ping Yee]

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 friend
Mark Miller implemented it in E.

He tells me his algorithm is inspired by the method for
unification of cyclic structures in Prolog III.  It's available
in the E source code (in the file elib/tables/Equalizer.java).

See interesting stuff on equality and cyclic data structures at

    http://www.erights.org/javadoc/org/erights/e/elib/tables/Equalizer.html
    http://www.erights.org/elang/same-ref.html
    http://www.erights.org/elang/blocks/defVar.html
    http://www.eros-os.org/~majordomo/e-lang/0698.html

There is also a thread about equality issues in general at:

    http://www.eros-os.org/~majordomo/e-lang/0000.html

It'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