２つの線形リストが同一か調べる。

Question

前提・実現したいこと

初投稿です。
Pythonで、２つの同一な線形リストを作り、それが同一であるか調べる関数is_sameをつくりました。
returnで再帰を行っているのですが、

if x.val == y.val:
        return is_same(x.next, y.next)

だとTrueになるのですが、

if x == y:
        return is_same(x.next, y.next)

だとFalseになります。
xもyも同じ値が入っていて、ポインターも同じ値を指しているから同一であるはずなのに、なぜ上のコードと下のコートで実行結果が異なるのでしょうか。
（想定していた出力は上のほうです）

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def is_same(x,y) -> bool:
    if x is None and y is None:
        return True
    if x is None and y is not None or x is not None and y is None:
        return False
    if x.val != y.val:
        return False
    if x.val == y.val:
        return is_same(x.next, y.next)

if __name__ =='__main__':
    head = ListNode(0)
    node = head
    
    for n in range(1, 100):
        node.next = ListNode(n)
        node = node.next

    head2 = ListNode(0)
    node2 = head2
    
    for n in range(1, 100):
        node2.next = ListNode(n)
        node2 = node2.next

    print(is_same(head, head2))

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

Pythonで==演算子を使うということは、オブジェクトの__eq__メソッド(特殊メソッドの一種)を呼び出すことです。もう少し噛み砕いて言うと、a == bという式はa.__eq__(b)と原則等価です。

3. データモデル — Python 3.8.2 ドキュメント

さて、この__eq__ですが、すべてのオブジェクトにデフォルトで存在してはいます。すべてのクラスの基底クラスであるobjectクラスですでに実装されているからです。ただし、これは抽象メソッド的に置いてあるだけで、実用的に使える訳ではありません（念の為に：「抽象メソッド的」というのは比喩的な意味です。最低限の実装は以下に述べるように存在しています）。デフォルトではis比較（同一性の比較）と同等の処理のみ行います。

全ての型は (直接的あるいは間接的に) object のサブクラスとなっているので、デフォルトの比較の振る舞いを object から継承しています。 基本的なカスタマイズ で解説されているように、型を使って rich comparison methods である __lt__() などのメソッドを実装することで、 比較の振る舞いをカスタマイズできます。

等価比較 (== および !=) のデフォルトの振る舞いは、オブジェクトの同一性に基づいています。 従って、同一のインスタンスの等価比較の結果は等しいとなり、同一でないインスタンスの等価比較の結果は等しくないとなります。 デフォルトの振る舞いをこのようにしたのは、全てのオブジェクトを反射的 (reflexive つまり x is y ならば x == y) なものにしたかったからです。
6. 式 (expression) — Python 3.8.2 ドキュメント

以上のことを雑に言うと、同一のオブジェクトでなければobject.__eq__に従う==比較はFalseになります。

もう少し踏み込んで説明すると、以下のようになります。

a,bがobjectの異なるインスタンスとして、a == bではまずa.__eq__(b)が試され、これはNotImplementedを返します。こうなると処理系はb.__eq__(a)も試しますが、こちらも同様の結果になります。両方NotImplementedになったときは、結果はFalseとして取り扱われます。

---

同値性の比較というのはけっこう高級な処理です。属性ぜんぶ同値なら同値とすればいい？　本質的ではない属性は無視して取り扱いたいかもしれません。あるいは、異なる型の間でも同値性を確認したいかもしれません（1 == 1.0はTrueです）。numpyなど、配列に==演算子を使うと要素と比較してくれますが（np.array([1, 2, 3]) == 1はarray([True, False, False])になります）、これはnumpyの開発者がそうなるように__eq__などのメソッドをすべて実装しているからです（+演算子に対応する__add__など、ほぼすべての演算子に対して同様のことをしています）。演算子オーバーロードというか演算子に対応するメソッドのオーバーライドなのですが、このあたりを柔軟に書き換えられるのが動的言語の強みです。

逆に言うと、自作オブジェクトで意味のある==を使いたいのなら、自分で書く必要があります。

たとえばこんな感じのメソッドを定義すればいいのではないでしょうか。

    def __eq__(self, other):
        return (self.val is other.val) and (self.next is other.next)

コードのロジックまでは追っていないので、やりたいことと合っているかはわかりません。valとnext属性が同一のListNodeオブジェクトは同値であるとみなすという私の信念にもとづくコードです。気に入らなければ質問者さんの責任で書き換えてください。

やりたいことがx.val == y.valならそれを__eq__に書いておけばいいのですが（引数の名前に変えた上で）、私の感覚ではこれはリストのコンスセルの同値性としては「緩すぎる」と感じます。なので私なら、==演算子には委ねずに素直に外側でx.val == y.valを判定するように実装するでしょう。