ハスケルでの共有を検出することは可能ですか？

Question

Schemeでは、プリミティブeq?は、その引数が同じオブジェクトであるかどうかをテストします。例えば、以下のリスト

(define lst 
    (let (x (list 'a 'b)) 
    (cons x x))) 

に

(eq? (car x) (cdr x)) 

の結果は真であり、しかもそれはが(car x)と(cdr x)にピアすることなく、真です。これにより、多くの共有を持つデータ構造に対して効率的な等価性テストを書くことができます。

ハスケルでも同じことが可能ですか？たとえば、次のバイナリツリーの実装を考えてみましょう。すべてのレベルで共有されているバイナリツリーの実装を考えてみましょう。 let tree = mkTree 30のツリーを作成して、left treeとright treeが等しいかどうかを知りたい場合は、10億ノードを越えてデータを共有する必要があります。

ハスケルでのデータ共有を簡単に発見する方法はないと思いますが、このような問題に対処する典型的な方法は、効率的な目的で共有を検出するのが得策でしょうか？周期的なデータ構造を検出する）。

unsafe共有を検出できるプリミティブがありますか？明示的なポインタを持つデータ構造を構築するためのよく知られた方法があるので、ポインタの等価性を比較できますか？

Answer 1

多くのアプローチがあります。

1. 一意のIDを生成し、すべてを有限マップ（例：IntMap）に貼り付けます。
2. 最終的な選択の洗練されたバージョンは、明示的なグラフを作成することです。 fglを使用してください。
3. stable namesを使用してください。
4. IORefs（see also）です。これは、含まれるタイプに関係なく、EqとOrdの両方のインスタンスを持ちます。
5. observable sharingのライブラリがあります。
6. 上記のとおり、reallyUnsafePtrEquality#がありますが、使用する前に実際には何が安全でないのかを理解する必要があります。

this answer about avoiding equality checks altogetherも参照してください。

Answer 2

reallyUnsafePtrEquality#があります。また参照してくださいhere

Answer 3

純粋な言語ハスケルでは不可能です。

しかし、GHCでの実装では、このような

• として抜け穴、ghc-heap-viewようreallyUnsafePtrEquality#または
• イントロスペクションライブラリの使用があります。

いずれにしても、これを通常のコードで使用すると非常にユニートリマティックです。せいぜい、私は、何か（メモ帳、ハッシュテーブルなど）のための高度に専門化されたライブラリを構築して、純粋で純粋なAPIを提供することが受け入れられるかもしれないと想像することができます。