是否有可能在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是相等的,天真的我必须遍历超过十亿节点发现它们是同一棵树上,这应该是因为数据共享明显.

我不认为在Haskell中有一种发现数据共享的简单方法,但我想知道处理这类问题的典型方法是什么,为了效率目的检测共享(或者例如检测循环数据)结构).

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

Answer 1

有很多方法.

1. 生成唯一ID并将所有内容粘贴在有限映射中(例如IntMap).
2. 最后一个选择的精炼版本是制作一个显式图形,例如使用fgl.
3. 使用稳定的名称.
4. 使用IORefs(另请参阅),它包含两个Eq和Ord实例,无论包含的类型如何.
5. 有可观察共享的库.
6. 如上所述,reallyUnsafePtrEquality#你应该在使用之前了解它真正不安全的地方!

另见关于避免完全平等检查的答案.

Answer 2

这在纯语言 Haskell 中是不可能的。

但其在GHC中的实现存在漏洞，比如

• 使用realUnsafePtrEquality#或
• 内省库，例如ghc-heap-view。

无论如何，在常规代码中使用它是非常不惯用的；我最多可以想象，为某些东西（memoizatoin、哈希表等）构建一个高度专业化的库，然后提供一个健全的、纯粹的 API，可能是可以接受的。