ハスケルの大規模なDAG構造の等価性テスト

Question

私はハスケル（数ヶ月）を使い慣れました。私は大きな表現DAG（樹木、DAGではない）、深く潜在的に複数の合流する経路（すなわち、根から葉までの異なる経路の数が巨大である）をアセンブルするHaskellプログラムを持っています。私は、等価のためにこれらのダグをテストするための速い方法が必要です。デフォルトのEqの導出は、同じノードを複数回探検するだけです。現在のところ、私のプログラムは比較的小さな表現では60秒かかり、大きなものでは終了しません。プロファイラは、ほとんどの時間平等をチェックしていることを示しています。私はこの問題がないカスタムEqを実装したいと思います。私はこの問題を解決する方法がありませんが、多くの書き換えを必要としません。だから私はあなたの考えを聞きたい。

私が最初に試みたのは、ツリーを構築するときに、Data.Hashable.hashを使用して、徐々に計算するハッシュを持つツリーノードを計測することでした。このアプローチは、構造を深く見ない限り、2つのものが等しいかどうかをテストする簡単な方法を与えました。しかし、多くの場合、このDAGでは、DAGマージのパスのために、構造は実際には等しいです。だからハッシュは平等で、私は完全な吹き飛ばされた平等テストに戻ります。

もし私が物理的平等を行う方法を持っていたら、ここでの私の多くの問題は消え去ります。物理的に同等であれば、それはそれです。それ以外の場合、ハッシュが異なる場合はそれがそれです。物理的には同じではないが、ハッシュに同意する場合にのみより深く進んでください。

また、gitを模倣し、ノードごとにSHA1を計算して、それらが等しい期間（再帰を必要としない）であるかどうかを判断することもできます。私は、これが助けになるという事実を知っています。ハッシュ平等の観点から平等を完全に決めると、プログラムは最大の表現に対して数十ミリ秒で実行されるからです。このアプローチには、何らかの理由で同じ2つの等しいダグが物理的に等しいのではなく内容が等しい場合、その場合でも高速に検出できるという利点があります。 （Idでは、Idはその時点でまだトラバーサルを行う必要があります）。だから私はセマンティクスがもっと好きです。

しかし、この手法では、Data.Hashable.hash関数を呼び出すよりもはるかに多くの作業が必要になります。これは、ダグノードタイプのすべての変種に対して派生させる必要があるためです。さらに、ノード定義が多少異なる複数のダグ表現があるため、表現を追加する場合は、基本的にこのハッシュトリックを2回以上行う必要があります。

あなたは何をしますか？

Answer 1

ここで問題となるのは、Haskellにはオブジェクトアイデンティティーの概念がないことです。つまり、同じノードを2回参照するDAGがあるとすると、Haskellに関する限り、木。これは、オブジェクトがメモリ内のその位置によって索引付けされるオブジェクト指向の概念とは根本的に異なります。したがって、「同じオブジェクト」と「等しいフィールドを持つ異なるオブジェクト」の区別は意味があります。

問題を解決するには、以前に見たのと同じオブジェクトを訪問したときに検出する必要があります。そのためには、値とは無関係の「同じオブジェクト」の概念が必要です。

• すべてのオブジェクトをベクトル（つまり配列）に格納し、ベクトルインデックスをオブジェクトIDとして使用します。データ構造全体の値をインデックスに置き換えます。

• 各オブジェクトに固有の「ID」フィールドを付けることで、DAGを通過する前にこのオブジェクトを見たことがあるかどうかを知ることができます。

前者は、コンテナパッケージのData.Graphモジュールがそれをしない方法です。利点の1つは、DAGからベクトルへの単一のマッピングがある場合、DAGの等価性はベクトルの等価性になります。

Answer 2

同等性をテストする効率的な方法は、DAG値を構築する方法と絡み合っています。

マップに作成されたすべてのノードを追跡するアイデアがあります。 新しいノードがマップに追加されると、一意のIDが割り当てられます。

ノードの作成は、このマップ （および次に利用可能なID）をスレッド全体に渡って実行するため、モナドになりました。

この例では、ノードは、バラの木として実装され、子供の 順序は重要ではありません - マップにキーを導出に sortへしたがって呼び出し。

import Control.Monad.State 
import Data.List 
import qualified Data.Map as M 

data Node = Node { _eqIdent:: Int  -- equality identifier 
        , _value :: String -- value associated with the node 
        , _children :: [Node] -- children 
        } 
    deriving (Show) 

type BuildState = (Int, M.Map (String,[Int]) Node) 

buildNode :: String -> [Node] -> State BuildState Node 
buildNode value nodes = do 
    (nextid, nodeMap) <- get 
    let key = (value, sort (map _eqIdent nodes)) -- the identity of the node 
    case M.lookup key nodeMap of 
    Nothing -> do let n = Node nextid value nodes 
         nodeMap' = M.insert key n nodeMap 
        put (nextid+1, nodeMap') 
        return n 
    Just node -> return node 

nodeEquality :: Node -> Node -> Bool 
nodeEquality a b = _eqIdent a == _eqIdent b 

このアプローチでは、ノードを構築するときにノードのすべての子を知る必要があります。