再帰的な構造のデータの同値性判定はどうしたらいいか - 貳佰伍拾陸夜日記

数日前にTwitterで, JavaScriptのオブジェクトに対する===の挙動が初心者には難しいみたいな話を見かけた. 発端や周辺の議論をちゃんと追いかけてないからとくに出典は貼らない. たぶん元々の話は「へぇ, こういう挙動なんだ, 簡単ではないね」くらいの話だったのかもしれない. 自分のタイムラインの観測範囲では「そうだそうだ, (参照の同一性ではなく)同値性にしとけばいいのに」と思っている人もそれなりにいそうに見えた. 個人的にも同値性が簡単に確認できるとよい気はするものの, 「なんでそうしないんだ, オブジェクトの中身を確認していくだけだろ!」みたいな簡単な話ではないことも知っているため, 以下のようなツイートをしたのだった. JavaScriptのオブジェクトの同値性、再帰的な構造とか作るとぜんぜん自明じゃないんだよなぁ。リンクの構造は違うけどプロパティを辿ったときのパスはど

[tarao]

言語の利用者が循環するオブジェクトを悪とするのは勝手ですが、循環参照を簡単に作れる言語設計で、かつ同値性判定も言語仕様に含むなら、循環する場合も当然うまく同値性判定できる言語設計にすべきと思います。

[valinst]

畑違いのプログラマだけど再帰的な構造のデータの同値判定なんて必要だったことがないので、それが必要な設計がまずいのではと思ってしまう

[strawberryhunter]

公開するAPIだと何が来るかわからないので、そういうものを作るときには設計がまずいとかいう次元の低い言い訳で逃げるわけにいかないはず。

[n_knuu]

再帰的な構造が問題というよりも循環参照が問題なのでは？という感じがする．json を扱ってると辞書の中に辞書があるみたいな再帰構造を持つデータは普通に出てくると思うので．理論的には面白い．

[napsucks]

チューリングマシンの停止性問題っぽい

[turanukimaru]

頭とケツが繋がってる循環した linked list を良く作るのだが Scala ではとてもやりにくい…それはおいとて、△と▽は同値か？みたいな問題もあるので結論は equals を真面目に書け、となる。超絶めんどくさいが。

[morita_non]

昔schemeで見たやつだ。どうやってたかは。。。忘れた。。。

[efcl]

"循環するオブジェクトも考慮した同値性の定義はさまざまなバリエーションが考えられる" 再帰構造の同値について

[yhoriz]

Coqみたいな厳密な再帰構造なら循環しないし、厳密な余再帰構造なら（循環しない無限構造を許す以上）判定不能　なまじアドレス同一性判定ができるせいで最悪O(nm)の比較をすることに…

[komlow]

“Communicating and Mobile Systems: The Pi-Calculus”

[kirakking]

Isabelle とか coq だと同一性の実装どうなっているんだっけな。inductive definition とかの周辺確認しないと。

[tettekete37564]

===ってポインタアドレスの一致みたいなのじゃなかったっけ？複雑な構造のデータ一致はソートルール付きのシリアライズして比較すれば良くね？

[mysql8]

power-assert.deepEqual「同値性判定を実装してないとかお前それ、@t_wadaの前でも同じこと言えんの？」

[syunnchang]

GraphQLで起きがち

[kazuau]

そんなの親が面倒見る必要なくて、equalsとhashCodeをオブジェクト側で定義してやればいいのでは?(Javaだけど) だが現状通り参照の同一性判定の方がシンプルでわかりやすいと思う。

[yujiorama]

双模倣性（bisimulation）

[t-tanaka]

結論：循環参照は悪。同値関係の判断が必要なオブジェクトの中に循環参照が入っているとしたら，設計自体が間違っている。

[ko-ya-ma]

双模倣

[ginpei]

循環する構造をどうdeepEquals判定するか。『x = { a: { a: x } } と x = { a: x } は同じか』『それをちゃんと判定できるか』　双模倣性という概念があるそうだ。

[zu2]

“再帰的な構造があると困ってしまう*1. なぜなら循環している可能性があるから. 同値性を判定できないと主張したいわけではなくて「同値性をどう定義したらいいか自明ではない」という話”

[kkobayashi]

思ったよりややこしい話だった