12

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

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

結果として

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

は true であり、さらに とを覗き込まなくても trueです。これにより、多くの共有を持つデータ構造の効率的な等価テストを作成できます。(car x)(cdr x)

Haskellで同じことが可能ですか? たとえば、次のバイナリ ツリーの実装を検討してください。

data Tree a = Tip | Bin a (Tree a) (Tree a)

left  (Bin _ l _) = l
right (Bin _ _ r) = r

mkTree n :: Int -> Tree Int
mkTree 0 = Tip
mkTree n = let t = mkTree (n-1) in Bin n t t

あらゆるレベルで共有しています。でツリーを作成し、とが等しいlet tree = mkTree 30かどうかを確認したい場合、10 億を超えるノードを単純に調べて、それらが同じツリーであることを発見する必要があります。これは、データ共有のために明らかなはずです。left treeright tree

Haskell でデータ共有を発見する簡単な方法があるとは思いませんが、このような問題に対処するための典型的なアプローチは何だろうと思いました。構造）。

unsafe共有を検出できるプリミティブはありますか? ポインターの等価性を比較できるように、明示的なポインターを使用してデータ構造を構築するよく知られた方法はありますか?

4

3 に答える 3

16

たくさんのアプローチがあります。

  1. 一意の ID を生成し、すべてを有限マップに貼り付けます (例: IntMap)。
  2. 最後の選択肢の洗練されたバージョンは、たとえばfglを使用して、明示的なグラフを作成することです。
  3. 安定した名前を使用してください。
  4. 含まれているタイプに関係なく、とインスタンスの両方を持つIORefs (も参照)を使用します。EqOrd
  5. 観察可能な共有のためのライブラリがあります。
  6. 上記のように、ありreallyUnsafePtrEquality#ますが、使用する前に本当に安全でないことを理解する必要があります!

等価チェックを完全に回避することについてのこの回答も参照してください。

于 2013-10-14T09:45:18.407 に答える
4

純粋言語である Haskell では不可能です。

しかし、GHC での実装には、次のような抜け穴があります。

いずれにせよ、これを通常のコードで使用するのは非常に単調です。せいぜい、まともな純粋な API を提供する何か (メモイザトイン、ハッシュ テーブルなど) のための高度に専門化されたライブラリを構築することは、受け入れられるかもしれないと想像できました。

于 2013-10-14T08:26:30.680 に答える