是否有可能在Haskell中檢測共享？

Question

在Scheme中，原語eq?測試它的參數是否是同一個對象。例如，在下面的列表

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

的

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

的結果爲真，而且它是真實無需窺視(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創建一棵樹，並且我想看看left tree和right tree是否相等，天真地我必須遍歷10億個節點才能發現它們是同一棵樹，這應該是顯而易見的，因爲數據共享。

我不希望有一個簡單的方法來發現Haskell中的數據共享，但我想知道處理這類問題的典型方法是什麼，當爲了效率目的而檢測共享（例如檢測循環數據結構）。

是否有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

在純粹的語言Haskell中是不可能的。

但在其實施GHC，有空子可鑽，比如

• 使用reallyUnsafePtrEquality#或
• 內省庫，例如ghc-heap-view。

在任何情況下，在常規代碼中使用它將是非常單一的;我最多可以想象的是，爲某些東西（memoizatoin，散列表等等）構建一個高度專業化的庫，然後提供一個理智的，純粹的API可能是可以接受的。