Haskell中大DAG結構的Eq測試

我是Haskell的新手（幾個月）。我有一個Haskell程序，它組裝一個大型表達式DAG（不是一棵樹，一個DAG），可能很深並具有多個合併路徑（即從根到葉的不同路徑的數量很大）。我需要一種快速的方法來測試這些dags的平等性。默認的Eq派生只會遞歸，多次探索相同的節點。目前，這會導致我的程序花費60秒來處理相對較小的表達式，甚至無法完成較大的表達式。分析器指示大部分時間都忙於檢查相等性。我想實現一個沒有這個問題的自定義Eq。我沒有辦法解決這個不涉及大量重寫的問題。所以我想聽聽你的想法。Haskell中大DAG結構的Eq測試

我的第一次嘗試是用我在構建樹時使用Data.Hashable.hash遞增計算的散列來「測量」樹節點。這種方法給我一個簡單的方法來測試兩件事情是不平等的，沒有深入研究結構。但通常在這個DAG中，由於DAG合併中的路徑，結構確實是相等的。所以哈希值是平等的，我恢復到全面的平等測試。

如果我有辦法做物理平等，那麼我在這裏的很多問題就會消失：如果他們在物理上是平等的，那就是了。否則，如果哈希是不同的，就是這樣。如果它們在物理上不一樣，只能更深入，但它們的散列同意。

我也可以模仿git，並計算每個節點的SHA1以決定它們是否等於週期（不需要遞歸）。我知道這樣做會有所幫助，因爲如果我通過散列相等來完全決定相等性，那麼程序將在幾十毫秒內運行最大的表達式。這種方法也有很好的優點，如果由於某種原因有兩個相同的dag不是物理上相同的，但是內容相同，那麼我也能夠在這種情況下快速檢測到它。（對於Id，Id仍然必須在該點進行遍歷）。所以我更喜歡語義。

然而，這種方法涉及比調用Data.Hashable.hash函數更多的工作，因爲我必須爲每個dag節點類型的變體推導它。此外，我有多個DAG表示，具有稍微不同的節點定義，所以如果我決定添加更多的表示形式，我需要基本上做兩次或更多的哈希技巧。

你會怎麼做？

來源

2016-06-26 orm

你在問怎麼用自定義函數定義'（==）'，或者什麼自定義函數最適合你的需求？這個問題有點臃腫/混亂，因爲它現在... btw，我不認爲「物理平等」，因爲你知道它存在於haskell中的其他語言，你只需定義你的'class Eq a where（==） ....'就是這樣...... – mb21

@ mb21他要麼是要求如何爲'Eq'定義一個有效的實例，要麼是如何爲他的DAG定義一個數據結構，而'Eq'的默認實例是有效的。 ..不知道這兩個中的哪一個，並且沒有給出我們可以提供一點幫助的代碼。 – Bakuriu

這裏問題的一部分是Haskell沒有對象標識的概念，所以當你說你有一個DAG指向同一個節點兩次時，就Haskell而言它只關心它在不同地方的兩個值一顆樹。這與OO概念有着根本的區別，在這個概念中，一個對象通過它在內存中的位置被索引，所以「同一對象」和「具有相同字段的不同對象」之間的區別是有意義的。

要解決您的問題，您需要檢測何時訪問與您先前看到的相同對象，並且爲了實現該目的，您需要具有與該值無關的「相同對象」的概念。有兩種基本方式來攻擊這一點：

存儲您所有的載體（即數組）對象，並使用矢量指數爲對象的身份。在整個數據結構中用索引替換值。
爲每個對象提供一個唯一的「身份」字段，以便您可以在遍歷DAG時確定是否曾經看過此字段。

前者是如何在容器包中的Data.Graph模塊做到這一點。一個優點是，如果你有一個從DAG到矢量的映射，那麼DAG相等就變成了矢量相等。

來源

2016-06-26 19:34:50

我明白你的意思了。我希望能夠在DAG節點（並且說，它的左邊的孩子）上模式匹配，以便能夠應用變換。如果孩子必須用矢量擡頭看，你會怎麼做？ – orm

@orm如果你想使用「自定義」模式匹配機制，GHC提供[模式同義詞]（https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html#pattern-同義詞）。初學者可能需要一些努力來定義它們，但一旦完成，它們的用法很簡單。如果你碰巧知道Scala的提取器對象，它們是（鬆散）相關的。 – chi

有趣的指針進一步學習。謝謝。 – orm

任何測試平等的有效方法都將與您構建DAG值的方式相互交織。

這是一個想法，它跟蹤有史以來在地圖中創建的所有節點。當新節點添加到地圖時，它們被分配一個唯一的ID。

創建節點現在變成了monadic，因爲您在整個計算過程中都有此線程的地圖（和下一個可用的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

一個警告 - 這種方法要求您在構建節點時瞭解節點的所有子節點。

來源

2016-06-26 20:02:36 ErikR

Haskell中大DAG結構的Eq測試

回答

相關問題