haskell - 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 创建一棵树，并且我想看看左树和右树是否相等，我天真地必须遍历超过十亿个节点，发现它们是同一棵树，由于数据共享，这一点应该是显而易见的。

我不希望有一种简单的方法来发现 Haskell 中的数据共享，但我想知道处理此类问题的典型方法是什么，何时出于效率目的检测共享会很好(或者例如为了检测循环数据结构)。

是否存在可以检测共享的不安全原语？是否有一种众所周知的方法来使用显式指针构建数据结构，以便您可以比较指针相等性？

Answer 1

有很多方法。

1. 生成唯一 ID 并将所有内容粘贴在有限 map 中(例如 IntMap )。
2. 最后一个选择的精炼版本是制作一个显式图表，例如使用fgl .
3. 使用stable names .
4. 使用IORefs ( see also )，无论包含的类型如何，都具有 Eq 和 Ord 实例。
5. 有 observable sharing 的库.
6. 如上所述，有 reallyUnsafePtrEquality#，但在使用它之前您应该了解它真正不安全的地方!

另请参阅this answer about avoiding equality checks altogether .