12

In Scheme, the primitive eq? tests whether its arguments are the same object. For example, in the following list

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

The result of

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

is true, and moreover it is true without having to peer into (car x) and (cdr x). This allows you to write efficient equality tests for data structures that have a lot of sharing.

Is the same thing ever possible in Haskell? For example, consider the following binary tree implementation

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

which has sharing at every level. If I create a tree with let tree = mkTree 30 and I want to see if left tree and right tree are equal, naively I have to traverse over a billion nodes to discover that they are the same tree, which should be obvious because of data sharing.

I don't expect there is a simple way to discover data sharing in Haskell, but I wondered what the typical approaches to dealing with issues like this are, when it would be good to detect sharing for efficiency purposes (or e.g. to detect cyclic data structures).

Are there unsafe primitives that can detect sharing? Is there a well-known way to build data structures with explicit pointers, so that you can compare pointer equality?

4

3 回答 3

16

有很多办法。

  1. 生成唯一 ID 并将所有内容粘贴在有限映射中（例如IntMap）。
  2. 最后一个选择的改进版本是制作一个显式图，例如使用fgl。
  3. 使用稳定的名称。
  4. 使用IORefs（另见），它同时具有Eq和Ord实例，而不管包含的类型如何。
  5. 有可观察共享的库。
  6. 如上所述，有reallyUnsafePtrEquality#但你应该在使用它之前了解它的真正不安全之处！

另请参阅有关完全避免相等检查的答案。

于 2013-10-14T09:45:18.407 回答
4

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

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

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

于 2013-10-14T08:26:30.680 回答
1

确实存在UnsafePtrEquality#。也见这里

于 2013-10-14T08:24:54.100 回答